PROBLEM LINK: Author: Pankaj Jindal, Piyush Kumar DIFFICULTY:Cakewalk PREREQUISITES:Maths, conversion of number from base 10 to some another base PROBLEM:Given an array of size $N$, each element in the array can take values $1$ to $K$, find the lexicographically smallest Lth string. QUICK EXPLANATION:In rest of the solution, will assume 0based indexing. EXPLANATION:Firstly, one should know what is lexicographic ordering, Before jumping to final solution, let's see how each subtask can be solved: Final solution Pseudocode: COMPLEXITY:$L$ can have max value of $K^{n}$, so complexity of solution would be $O(log_K(L))$ i.e. $O(n)$ AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:
This question is marked "community wiki".
asked 25 Mar '15, 20:26

My Idea: In the problem, we have to find lexicographically $L$th way of filling digits. So we go from left to right filling the digits in order. At current position $i$, we will try each value from $1$ to $K$, then we filling the remaining positions in $K^{(N  i)}$ ways. So for this position, we can determine which value should be filled at this position. Basically we will pick the value for this position which does not let exceed total number of ways from $L$. Subtract the total number of ways from $L$ and similarly go for deciding digit for next position i.e. $i + 1$. Btw this strategy of going from left to right and deciding for current digit is common way of dealing with many problems involving lexicographic ordering :) answered 29 Mar '15, 02:19
Have used same concept as yours. However I am getting WA in subtask 3. http://www.codechef.com/viewsolution/6595735. I have used unsigned long long to avoid errors due to overflow.
(29 Mar '15, 15:31)
Hi mjnovice: For checking whether a * b > MAX, when a * b can overflow from its data type (eg. long long), then you can write this as a > MAX / b. So if you do this change in your code, it will be accepeted
(29 Mar '15, 15:58)

I did it in a very lame way but i am getting a division by zero error for last two constraints!Can anyone figure it out plz? Code: http://www.codechef.com/viewsolution/6604752 answered 02 Apr '15, 15:29

Can anyone please explain what this is asking.? I don't get this problem Thanks answered 12 Apr '15, 18:58
