Partitions Solution

This problem is about representing partitions of the set f0; 1; 2; : : : ; n 1g. A partition of a set is a collection of disjoint non-empty subsets of the set, whose union is the whole set. In other words, every element in the set belongs to exactly one of the subsets, and each subset is non-empty. Such a partition can be represented uniquely by what is called a restricted growth sequence p0; p1; : : : ; pn 1, that satis es p0 = 0 and 0 pi 1 + max0 j<i pj for i > 0. Here, pi denotes the ‘part number’ of the subset containing i. The parts are numbered in increasing order of their smallest elements. The part containing 0 is always 0. If element i is in the same part as some smaller element j, pi = pj, but if it is the smallest element in its part then i will be in a new part with number 1 + max0 j<i pj. Thus the partition ff0; 3g; f1; 2gg would be represented by the sequence 0; 1; 1; 0. Given this representation, we can de ne an ordering on the partitions based on the lexicographic ordering of the sequences. A partition p0; p1; : : : ; pn 1 is less than q0; : : : ; qn 1 if there exists an index i such that pi < qi and pj = qj for all 0 j < i. The rank of a partition is the number of partitions that are less than it. The partition 0; 0; : : : ; 0 will have rank 0, and the partition 0; 1; 2; : : : ; n 1 will have the highest rank. The rank of 0; 1; 1; 0 is 8.

You have to write a function that will take a restricted growth sequence as input, and output its rank. You have to also write a function that will take the rank and output the corresponding sequence. Such functions are useful because we can work with just numbers instead of partitions.

Input/Output. The rst line of input will specify n and the number of test cases t. The next t lines will contain one test case each. Each test case will be of the form R p0 p1 : : : pn 1 or U r. Here p0; p1; : : : ; pn 1 is a restricted growth sequence whose rank is to be computed, and r is the rank for which the corresponding sequence is to be found. R and U indicate the type of operation to be performed. n will be at most 20 and t will be at most 106.

The output should print out the answer for each test case in the same order as given, one case per line. For an R operation, a single number must be output, while for a U operation a sequence p0 : : : pn 1 must be output on a single line, the numbers separated by a space. Note that the ranks may be large so use long long int for calculations. Time required should not be more than few seconds. You can reduce the time required for I/O by setting the ag ios base::sync with stdio(false).


Hint. To know how many sequences are less than a given sequence, we need to know for any given partial sequence, how many sequences of length n start with that sequence. For example, if a sequence starts with 0; 1 any sequence starting with 0; 0 will be less than it. If we can count this easily, we can nd the rank. The crucial observation is that the number of sequences starting with a given sequence depends only on the length and maximum value of the sequence. If we can compute this number for each possible value of the maximum and length and store it, we can use it whenever needed, without recomputing it. This is a technique called dynamic programming that is used heavily in designing e cient alogorithms. Can you compute these numbers easily using induction? Submission. Submit a single le named RollNo 3.cpp .



1