JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook General TopCoder Cookbook Discussion question about "Finding Lexicographically Kth string in a set" recipe
 question about "Finding Lexicographically Kth string in a set" recipe | Reply Hi I would like to post this post in this topic : http://apps.topcoder.com/forums/?module=Thread&threadID=643516&start=0 but that are closed. So I have to open a new thread, for my question (sry)..Thanks for this article!I don't understand this part:- Sometimes the problem goes a step ahead and defines the set all of strings of length <= n and you are asked to find the lexicographically Kth string ieS = { S(1), S(2) .... S(n) }In that case if t[len] denote the total number of strings of length len, iterate over len subtracting from K as long as K > t[len]. After this K denotes the ordinal number in the set S(len). Ie We found the target strings length and ordinal number. We proceed as given in solution, call recurse(len, K)```For(len,1,n) For(j,0,m-1) t[len] += d[len,j] For(len,1,n) { if(K > t[len]) K -= t[len]; else break; } recurse(len,K); ```I think if I follow your pseudocode then I think "b" is lexicographivcally less than "ab"?So I would solve it in this way (try to follow your style):```For(j,0,m-1) For(len,1,n) { if(len>1) t[len,j]=t[len-1,j]; else t[1,j]=1; } //t[len,j] contains the number that words start with j and no longer than len   while(K && len) { for(j,0,m-1) { if(K>=t[len,j]) K-=t[len,j]; else break; } answer += (char)('a'+j); --len; }   ```Maybe I misunderstand the example, could you help me what?
 Forums TopCoder Cookbook General TopCoder Cookbook Discussion question about "Finding Lexicographically Kth string in a set" recipe Previous Thread  |  Next Thread