# CAKEDOOM - Editorial

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.

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

9 Likes

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

1 Like

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

7 Likes

ah yes! My solution gave NO where answer is 1010. Thanks a lot

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.

2 Likes

This is exactly how TESTER’S SOLUTION proceeds. But it is clear that once we find good fit for first question mark we don’t need to consider any further possibilities for it.

2 Likes

@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!

Your solution fails for the following case, number of colors = 2, arrangement = “1”. The answer should be “1”, where as your solution outputs “0”.

1 Like

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.

This test is incorrect. A real failing test is

``````1
0
``````

But this is easy bug. Another much more important bug you can catch on the following test

``````2
??1?
``````
1 Like

1
0
gives 0
and
2
??1?
gives 1010
Is this wrong??

admin plz provide ur test cases

1 Like

At first sight your solution should fail on these tests. So if not you can take any AC solution and compare its output with yours for random tests.

@rgaberina sorry abt that… my mistake. The test anton has provided is the one.

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.

3 Likes

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

http://www.codechef.com/viewsolution/1120092
@admin can you please tell on which test case my solution failed

http://www.codechef.com/viewsolution/1120092
@admin. please provide me with test case on which my solution failed