You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFANUP - editorial

3
1

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

This question is marked "community wiki".

asked 25 Mar '15, 20:26

amanjain110893's gravatar image

4★amanjain110893
561412
accept rate: 0%

edited 16 Jun '15, 12:00

vicky002's gravatar image

1★vicky002 ♦♦
2561314


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

link

answered 29 Mar '15, 02:19

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53136170
accept rate: 20%

edited 29 Mar '15, 02:24

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) mjnovice3★

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) dpraveen ♦♦4★

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

link

answered 02 Apr '15, 15:29

piyush%20asutkar's gravatar image

3★piyush asutkar
114
accept rate: 0%

edited 02 Apr '15, 15:30

Can anyone please explain what this is asking.?

I don't get this problem

Thanks

link

answered 12 Apr '15, 18:58

rogersands123's gravatar image

1★rogersands123
-1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,643
×1,184
×70

question asked: 25 Mar '15, 20:26

question was seen: 2,868 times

last updated: 22 Feb '18, 10:23