PROBLEM LINK:
Author: Pankaj Jindal, Piyush Kumar
Tester: Sergey Kulik
Editorialist: Aman jain
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 0-based indexing.
L^{th} lexicographically smallest dish would be (L-1)^{th} number in base K.
EXPLANATION:
Firstly, one should know what is lexicographic ordering,
Lexicographical order is alphabetical order preceded by a length comparison. That is to say, ‘a’ string a is lexicographically smaller than a string ‘b’, if the length of ‘a’ is smaller than the length of ‘b’, or else they are of the same length and ‘a’ is alphabetically smaller than ‘b’.
Similarly, two array of numbers of equal size can be lexicographically compared as, let
arr1 = a1,a2,....,an
arr2 = b1,b2,....,bn
then find the first position i from left, such arr1[i]!=arr2[i], then if arr1[i] > arr2[i] arr1 is lexicographically greater else arr2.
Before jumping to final solution, let’s see how each sub-task can be solved:
First subtask has N <= 3, each position can be filled with K possibilities leading to O(N^{K}) solution. We can use three nested loops to assign value at each position and count each assignment, once total number of iterations reaches L we can print current assigned values.
Second subtask, we start from smallest lexicographic ordering i.e. 0,0...,0. We can find next ordering by adding 1 at the Least significant position, this addition is in (mod K) space. Keep adding 1 to LSB for (L-1) times and we will get L^{th} smallest lexicographically ordering. Complexity will be O(N*L)
Final solution
When we write series of numbers 0,1,2,....m in base K we will find that they are lexciographically sorted. For ex:
0(base 10) = 000(base 2)
1 = 001
2 = 010
3 = 011
4 = 100
5 = 101
6 = 110
7 = 111
Series in base 2 is lexicographically sorted. This works for all bases.
Now our problem wants us to find L^{th} lexicographically smallest position, such that each position is filled by numbers from 0 to K-1 i.e. base K. So our answer should be (L-1) expressed in base K. [NOTE: (L-1) not L because its 0 based indexing.]
Pseudocode:
ans[n] = {0}; // initialize an array of size n to 0
co = n-1;
while(L > 0){
ingredient = L%K;
ans[co] = ingredient;
--co;
L /= K;
}
// we assumed 0 based indexing but final answer expects 1 based
for i from 0 to n-1: ans[i] += 1;
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:
