CAKEDOOM - Editorial

editorial
greedy
june12
simple

#1

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy Algorithms

PROBLEM:

The problem requires you to output the lexicographically smallest possibility from the given “partial” arrangement which adheres to the constraints given. For details for

QUICK EXPLANATION:

  1. For K=1 replacement is possible only for N=1 and that would be “0”.

  2. For K=2 and N%2=0, we have only two possible arrangements for this.
    String with all the 1’s at odd places and all the 0’s at even places and vice versa. Thus we have to match both of these arrangements with given arrangement and print out the one which matches and is lexicographically smaller.
    For K=2 and N%2=1, print “NO” straight away because any arrangement of alternate 1’s and 0’s will lead to the matching of 1st and last character.

  3. For K>=3 and a valid partial arrangement, we will always have a solution as each ‘?’ has exactly two neighbours and we have at least 3 available options for that ‘?’. So we can choose the smallest satisfying digit for each ‘?’ starting from the left most ‘?’.

DETAILED EXPLANATION:

First of all, perform a check if the partial arrangement itself is valid.

For example, the arrangement 0??110?3?4 is invalid because you can see two cherries of the same color (1) adjacent to each other. The arrangement ??0??1??2 is a valid partial arrangement as there are no same colored adjacent cherries so far. Note that till now we have only checked for validity of partial arrangements. A valid partial arrangement MIGHT NOT give you a valid complete arrangement. But, an invalid partial arrangement will NEVER give a valid complete arrangement. Hence, if the partial arrangement is invalid, you can print the answer to be “NO”.

If we have a partial valid arrangement, we try to get the lexicographically smallest arrangement. Let’s take an example and try to find an optimal answer:
120??0 with K=3
To keep the configuration valid, the first ‘?’ can be filled using any color except ‘0’. You might wonder if we should bother about what we are going to replace the second ‘?’ with. To find the answer for the above question, let’s revisit the definition of lexicographically smaller arrangement:

"One arrangement is called lexicographically smaller than the
other arrangement if at the FIRST
position where they differ the first
one has smaller digit.”

Thus, the first ‘?’ will decide the lexicographical order of the possible answers and if the color at this position is the same, only then we will come to the second ‘?’. In other words, the arrangement 1201?0 will always be lexicographically smaller than 1202?0 no matter what the ‘?’ is replaced with. Now, we have 1201?0 as our current arrangement. Hence, we decide the color using the exact same strategy. We can fill the ‘?’ using any color apart from 1 and 0. Hence, the smallest color left now is ‘2’.
Thus we arrive at our final answer 120120.

It is clear from the above example that the optimal choice at any ‘?’ is the greedy choice. This means that the optimal choice is always the smallest available color that will keep the arrangement valid. (Note here that we move from left to right while selecting our greedy choices. This is because the strings are compared lexicographically from left to right.)

Now that we have the approach with us, we can break the problem into different cases:

  1. For K=1 replacement is possible only for N=1.

  2. K=2 is the important case which your solution must handle. A lot of solutions failed this case. Let’s look at it carefully.
    The only possible valid combination for K=2 is when we place the colors ‘0’ and ‘1’ alternatively on the cake i.e. the configuration must look something like 010101… or 101010… . Also to keep in mind is that the first and last cherries are adjacent to each other. Hence, K=2 can give a valid answer only when the length of the arrangement is even, else the first and last cherries will be of the same color if we choose alternative colors. So, print “NO” if the length of the arrangement is odd.
    Clearly, N should be even and we have only two different arrangements as mentioned above. So we simply check which one of them matches our partially filled arrangement.

  3. Finally if K>=3 then replacement is always possible for a valid partial arrangement. Indeed, we can use the above mentioned greedy strategy. Each question mark can be replaced by some digit without conflicts since we always can choose a digit different from both of the neighbors as we have at least 3 colors.

SETTER'S SOLUTION:

Can be found [here][4].

APPROACH:

The problem setter used the above approach to solve the problem.

TESTER'S SOLUTION:

Can be found here.

APPROACH:

This solution does not divide the problem into different cases. It handles all the cases as one.
Given a partial arrangement, we check if the first position is a ?. If yes, we try and replace it with every colour from 0 to K-1. Then we move on to the next ?'s and replace each with the appropriate greedy choice. As soon as we get a valid arrangement, we know that we have the final answer with us. This we need to check for atmost K arrangements.
If the first character is not a ?, we just make greedy choices for all the ?'s in the partial arrangement (moving from left to right).

OTHER SIMILAR PROBLEMS:


#2

Can I please know for, which test-case was my solution failing ?
My solution: http://www.codechef.com/viewsolution/1109365
Thanks :wink:


#3

Without any complex case examination you can do this: -If the first char is ‘?’, try every digit less than k here. Then just greedily on every next ‘?’ put the lowest valid digit. From these 10 at most strings return the lexicographically lowest.


#4

@lazzrov A solution will need to replace any ‘?’ by either 0, 1 or 2… so no need to check for all values <k, but just these three values!
@admins… could you please give a hint as to why my submission fails : http://www.codechef.com/viewsolution/1091856
Thanks so much! :slight_smile:


#5

Hi, can anyone pls help me in finding the test case for which my solution is failing?
http://www.codechef.com/viewsolution/1124287 is my solution. Thanks in advance.


#6

admin plz provide ur test cases


#7

There’s a trivial mistake in the editorial:

“K=2 can give a valid answer only when the length of the arrangement is even, else the first and last cherries will be of the same color if we choose alternative colors. So, print “NO” if the length of the arrangement is odd.”

N=1 is valid, even though it is odd.


#8

can sme1 tell why my code is giving wrong ans i m still unable to find test case for which it fails:(:frowning:
http://www.codechef.com/viewsolution/1117745


#9

I used recursive backtrack to get to the final solution if the initial lexicographically smallest solution is proved invalid. Doesn’t need to consider any cases. My Solution


#10

Hi, can anyone pls help me in finding the test case for which my solution is failing? http://www.codechef.com/viewsolution/1128186 is my solution. Thanks in advance.


#11

Finally I managed to solve it! Thanks to the editorial team :smiley:
My test case was failing only for: n=1

Here’s my solution if anyone’s interested:

http://www.codechef.com/viewsolution/1128650


#12

Code-http://ideone.com/h6wzu

@probsetter-can u tell me which cases of test file my code fails?..:?
thnx in adv…


#13

Please Someone Help me and find a testcase for which my code will not work.

http://www.codechef.com/viewsolution/1130018


#14

Can someone please explain why this is failing http://www.codechef.com/viewsolution/2660229


#15

https://www.codechef.com/viewsolution/17554426

where am i wrong pls help


#16

I am getting wrong answer. can anyone please tell me, which test case does my code fail?
I have tried all aforementioned test cases.

https://www.codechef.com/viewsolution/19006754


#17

Any idea why this is not working?

https://www.codechef.com/viewsolution/22104718


#18

Just a query : for the test case where K=1 and S=“5” , the output must be “NO”, right?
But I just observed that few solutions that got AC , have the output as “0” for the above test case.
Please explain?
P.S : Correct me if I am wrong :slight_smile:


#19

I am a little late to the party, but can someone please help me with what is wrong with my solution. I have read the editorial and fail to see what am I doing differently, which is causing WA for my solution. Please help :slight_smile:
https://www.codechef.com/viewsolution/23607275


#20

You deal with the case K=2 in a wrong way. Try this test: 2 ??1?.