
Name Finding the Lexicographically Kth Combinatorial Object
Problem From all combinatorial objects of length n generated by specified rules you need to find the lexicographically kth one.
Solution Let k be 0based. Then let’s suppose a_{m,p} to be a number of combinatorial objects of length m satisfying certain condition marked as p. A totality of all p’s for some m describes a condition which suffixes of length m of any our combinatorial objects of length n must satisfy (and every such suffix must satisfy exactly one of those p’s).
So the general solution is like this pseudocode:
class CombinatorialObject {
void getMthSymbol (int m, int p, int k, vector<symbol> &ans) {
if (m==0) return;
ans.push_back(symbol(m,p,k));
getMthSymbol(m1,newP(m,p,k),newK(m,p,k),ans);
}
};
Where function symbol(m,p,k) returns an appropriate symbol, function newP(m,p,k) returns new condition for a suffix of length m1, and function newK(m,p,k) returns a number of appropriate suffix under this condition. These two functions may rely on a_{m,p}. To obtain the answer, we should call getMthSymbol with arguments n, condition p that actually means no condition in addition to problem description, k, and an empty array ans.
But there are three important questions: how we should calculate a(m,p), newP(m,p,k), and newK(m,p,k). If only there was a universal method, we would describe it here, but modes of calculating these vary too much for different problems, so we explain them on examples.
Discussion If k is small enough, you may use brute force algorithm generating combinatorial objects in lexicographical order and simply take the kth one. Our sophisticated approach is for cases when there are too many objects to iterate throw for passing time limit.
I couldn’t find any SRM problems requiring this algorithm easier than Division One – Level Three, so I suppose it will be more understandable if I give some other examples.
In simple cases you can calculate a_{m,p} directly and find k using a formula. Let’s suppose we need to find kth lexicographically array of n integers from 0 to n1, inclusive. This is basically the task of writing down number k in nbased notation, and can be solved easier, but we'll handle it in a manner that illustrates our idea. In this simple case there are no constraints p on suffixes depending on previously set symbols, and a_{m,p} (actually simply a_{m}) is just a number of arrays of length m where each element is an integer between 0 and n1, inclusive. a_{m}=m^{n}, so we precompute it in array pow[m] before calling recursion.
#include <vector>
using namespace std;
class Arrays {
private:
vector<int> pow;
void getMthSymbol(int m, int k, vector<int> &ans) {
if (m==0) return;
ans.push_back(k/pow[m1]);
getMthSymbol(m1,k%pow[m1],ans);
}
public:
vector<int> getKth(int n, int k) {
pow.resize(n);
int i;
pow[0]=1;
for (i=1; i<n; ++i) pow[i]=pow[i1]*n;
vector<int> ans(0);
getMthSymbol(n,k,ans);
return ans;
}
};
