API tools faq
paste
Advertisement
Fastrail08

Number of ways to partition into k subsets(IMPORANTANT)

Fastrail08
Jun 30th, 2025 (edited)
333
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.92 KB | None | 0 0
raw download clone embed print report
  1. // IMPORTANT SEE THIS DISCUSSION
  2. // https://chatgpt.com/share/6862b81c-7a7c-8012-983f-5e2aa76d97c0
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. long long getKPartitions(int level, int partitionsFormed, int &k, int &n, vector<vector<long long> > &memo){
  7.     if(level > n){
  8.         if(partitionsFormed == k){
  9.             return 1;
  10.         }
  11.         return 0;
  12.     }
  13.     //memo check
  14.     if(memo[level][partitionsFormed] != -1){
  15.         return memo[level][partitionsFormed];
  16.     }
  17.     long long newPartition = 0, exisitingPartition = 0;
  18.     // create a new partition if capability to create a new partition
  19.     if(partitionsFormed < k){
  20.         newPartition = getKPartitions(level + 1, partitionsFormed + 1, k, n, memo);
  21.     }
  22.    
  23.     //don't create a new partition, become part of each exisiting partition one by one
  24.     // for(int i = 0; i < partitionsFormed; i++){
  25.     //     exisitingPartition += getKPartitions(level + 1, partitionsFormed, k, n, memo);
  26.     // }
  27.     //You can actually replace the call with the following ------
  28.     exisitingPartition = getKPartitions(level + 1, partitionsFormed, k, n, memo);
  29.     exisitingPartition *= partitionsFormed;
  30.    
  31.     // WHY??
  32.     // What are we doing here? we are calling the same function exactly equal to the number of partitions present at the current level. If the number is not creating a new partition it can become a part of every partition present at that level, giving a new way to partition each time.
  33.     // Also the loop is doing the same thing -
  34.     /*
  35.     for(0 -> partitionsFormed - 1){
  36.         call Kpartition [partitionsFormed] number of times.
  37.     }
  38.    
  39.     Basically doing ------
  40.     count = Kpartition() * partitionsFormed
  41.     */
  42.    
  43.     /*
  44.     Now if you see the recursive function, the params that are changing are (level, k). so memo(level, key).
  45.     Also what does that mean ------
  46.    
  47.     memo(level/i, k/x) = After processing upto ith index, if number of partitions formed till now is x, any subproblem falling under this category will have the same count of ways to distribute (n - i) elements into (k - x) partitions . What this means is we are memoising number of ways to disribute if the number of elements remaining to be partitioned is (n - i), and the number of partitions left is (k - x).
  48.    
  49.     SO IT DOESN'T MATTER WHAT THE ACTUAL ELEMENTS ARE IN THE PARTITION, just the number of elements that are already processed and the number of partitions that are already used in processing them.
  50.    
  51.     Actually the memo defintion contains (i, x), but the value that is memoised is (n - i, k - x)... just imagine what part of tree we are avoiding to recalculate.
  52.     The part that we are avoiding to recalculate is how to distribute (n - i) elements into (k - x) partitions. This is actually what DP is. AVOID RECALCULATION OF SMALLER SUBPROBLEMS.
  53.    
  54.     WHY??
  55.     Because partition doesn't depend on the ELEMENTS or PARTITIONS itself
  56.     for eg - (n - i) = 5, (k - x) = 2
  57.     ******Number of ways to DISTRIBUTE 5 elements into 2 partitions will always have the same REGARDLESS of the what the value of the elements are.
  58.    
  59.    
  60.     THIS IS WHERE IT DIFFERS WITH THE QUESTION - partition n elements into k equal sum partitions.
  61.    
  62.     Imagine how would you achieve this recursively?
  63.     Keep track of (level, k, partitionSumVector). We need to maintain a partitionSum vector of size k, so that in base case we can actually compare the sum of all k partitions, in whatever case, there are k partitions all with equal sum will contribute to answer.
  64.    
  65.     Now in the recursive code, 3 params are changing...
  66.     (number of indices processed, number of partitions left to form, sum of every partition formed).
  67.     so MEMO(level, k, partitionSum)
  68.     so memo key = [level + "|" k + "|" + serializeIntoString(partitionSum)]
  69.    
  70.     Alternatively you can think as -
  71.     WHAT ALL PARAMS ARE NEEDED TO MAKE VALID/INVALID DECISIONS IN THE BASE CASE??
  72.    
  73.     1) we need a level > n check to see if all elements are processed
  74.     2) we need a k == 0 check to see if exactly k partitions are formed
  75.     3) If both of the above are met, compare the sum of all k partitions and see if they are equal.
  76.    
  77.     If all 3 condns are met, return 1 else 0
  78.    
  79.     So we needed these 3 variables to make decision, that's why all 3 are to be memoised.
  80.    
  81.     so if you try to memoise with key as (level, k) it would insufficient, as the partitionSum vector might have different value.
  82.     And if it differs, the decision making in base case may also differ.
  83.     FOR EG ------ consider array of 7 elements and 4 partitions, now if in the base case we have the params as -
  84.     level = 7(all indices processed), 0 partitions left to form(all 4 partitions formed),sum of each partition  
  85.     (7, 0, [8, 8, 8, 8]) & (7, 0, [4, 6, 4, 2])
  86.    
  87.     But the first case is a VALID ANSWER (all 4 partitions equal) which will return 1 and the second case is INVALID (sum not equal) which will return 0.
  88.    
  89.     But if you had memoised based on (level, k) both had the same key (7, 0) ...which makes essentially an OVERLAPPING IDENTICAL SUBPROBLEM but they are not as the answers returned from both the cases are different. They are OVERLAPPING NON IDENTICAL SUBPROBLEMS, misclassified...
  90.    
  91.     When this happens, when you MISCLASSIFY two different subproblems under 1 key,
  92.     YOU ARE MEMOISING WITH AN INCOMPLETE KEY!!!
  93.     OR
  94.     MEMO KEY DOES NOT REPRESENT THE COMPLETE STATE OF THE SUBPROBLEM
  95.     OR
  96.     STATE UNDER SPECIFICATION (USING LESS VARIABLES TO DEFINE THE PROBLEM)
  97.    
  98.     ******Need more uniqueness in the key to differentiate subproblems correctly
  99.    
  100.     */
  101.    
  102.     return memo[level][partitionsFormed] = newPartition + exisitingPartition;
  103. }
  104.  
  105. int main() {
  106.     // your code goes here
  107.     int n, k;
  108.     cin >> n >> k;
  109.     vector<vector<long long> > memo(n + 1, vector<long long>(k + 1, -1));
  110.     cout << getKPartitions(1, 0, k, n, memo) << '\n';
  111.    
  112. }
  113.  
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!