API tools faq
paste
Advertisement
Fastrail08

Count the ways of friends pairing

Fastrail08
Jun 30th, 2025
369
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.50 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int pairFriends(int level, int &n, vector<bool> &visited, unordered_map<string, int> &memo){
  6.    
  7.     if(level > n){
  8.         return 1;
  9.     }
  10.     string friendsBlocked = "";
  11.     for(int i = 1; i < visited.size(); i++){
  12.         if(visited[i]){
  13.             friendsBlocked += to_string(i);
  14.         }
  15.     }
  16.     string memoKey = to_string(level) + "|" + friendsBlocked;
  17.    
  18.     if(memo.count(memoKey) > 0){
  19.         return memo[memoKey];
  20.     }
  21.    
  22.     int single = 0, paired = 0, occupied = 0;
  23.     // YOU can only take decisions if you are not already paired by some other friend.
  24.     // such as we processed 1 and 2 and at level of 3.... if we are on some path where {1, 3},{2} which means 1 at their own level decided to pair up with 3, which will block up 3 and in that path 3 will be marked visited before we even reach 3. So we just move to the next level.
  25.     if(!visited[level]){
  26.         //either go alone/don't pair
  27.         visited[level] = true;
  28.         single = pairFriends(level + 1, n, visited, memo);
  29.         visited[level] = false;
  30.        
  31.         //form pairs with every friend that is AVAILABLE and not already paired up, and to make this decision too, you also need to be free,i.e. that you should NOT ALSO BELONG to some pair
  32.    
  33.         //start the loop from level + 1 and not 1 just to avoid permutation... {1, 2} making this pair at level 1, but making this pair {2, 1} at level 2.
  34.         visited[level] = true;
  35.         for(int i = level + 1; i <= n; i++){
  36.             if(!visited[i]){
  37.                 visited[i] = true;
  38.                 paired += pairFriends(level + 1, n, visited, memo);
  39.                 visited[i] = false;
  40.             }
  41.         }
  42.         visited[level] = false;
  43.     }
  44.     else{
  45.         occupied = pairFriends(level + 1, n, visited, memo);
  46.     }
  47.    
  48.     return memo[memoKey] = single + paired + occupied;
  49.   // return memo[level][] = single + paired + occupied;
  50. }
  51.  
  52.  
  53. int pairFriendsOptimised(int n, vector<int> &memo){
  54.     if(n == -1){
  55.         return 0;
  56.     }
  57.     if(n == 0){
  58.         return 1;
  59.     }
  60.    
  61.     //memo check
  62.     if(memo[n] != -1){
  63.         return memo[n];
  64.     }
  65.    
  66.     int single = 0, paired = 0;
  67.     //go single
  68.     single = pairFriendsOptimised(n - 1, memo);
  69.    
  70.     //go pair
  71.     // for(int i = 0; i < n - 1; i++){
  72.     //     paired += pairFriendsOptimised(n - 2, memo);
  73.     // }
  74.     paired += pairFriendsOptimised(n - 2, memo);
  75.     paired *= (n - 1);
  76.     //IMPORTANT
  77.     //It can be further replaced with simple multiplication though..
  78.     //As the loop runs from (0 -> n - 2)...a total (n - 1) times, which immitates the pairing of for a single person,..if there are total n persons... 1 single person can form (n - 1)pairs
  79.    
  80.     //ALWAYS BE ON THE LOOKOUT FOR SUCH PATTERNS in counting questions, WHERE FOR LOOP IS JUST MAKING THE SAME CALLS FOR A SET NUMBER OF TIMES, as it is the same call without any change, it will always return a same value. Just call it once and multiply the number of times it was called.
  81.     return memo[n] = single + paired;
  82. }
  83.  
  84. int main() {
  85.     // your code goes here
  86.     int n;
  87.     cin >> n;
  88.     /*
  89.     MEMO Call
  90.     vector<bool> visited(n + 1, false);
  91.     unordered_map<string, int> memo;
  92.     cout << pairFriends(1, n, visited, memo) << '\n';
  93.     */
  94.    
  95.     /*
  96.     MEMO CALL (Self Thought) Could be optimised when solved the OG MEMO CODE.
  97.    
  98.     */
  99.     vector<int> memo(n + 1, -1);
  100.     cout << pairFriendsOptimised(n, memo) << '\n';
  101.    
  102. }
  103.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!