CHEFANUP - editorial

PROBLEM LINK:

Practice

Contest

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:

author

tester

editorialist

3 Likes

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 :slight_smile:

1 Like

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.

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

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

Can anyone please explain what this is asking.?

I don’t get this problem

Thanks