PROBLEM LINK:DIFFICULTY:SIMPLE PREREQUISITES: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:
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:
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:
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 K1. 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:
This question is marked "community wiki".
asked 12 Jun '12, 01:09

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. answered 12 Jun '12, 22:59

Can I please know for, which testcase was my solution failing ? My solution: http://www.codechef.com/viewsolution/1109365 Thanks ;) answered 12 Jun '12, 02:19
7
You deal with the case K=2 in a wrong way. Try this test: 2 ??1?.
(12 Jun '12, 02:39)
ah yes! My solution gave NO where answer is 1010. Thanks a lot ;)
(12 Jun '12, 03:26)

@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! :) answered 12 Jun '12, 07:24
1
Your solution fails for the following case, number of colors = 2, arrangement = "1". The answer should be "1", where as your solution outputs "0".
(12 Jun '12, 09:55)

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. answered 12 Jun '12, 12:14
1
This test is incorrect. A real failing test is
But this is easy bug. Another much more important bug you can catch on the following test
(12 Jun '12, 13:52)
1 0 gives 0 and 2 ??1? gives 1010 Is this wrong?? @kaush_adm: k=1 s=1 does not follow the input constraints.
(12 Jun '12, 13:58)
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.
(12 Jun '12, 19:55)
@rgaberina sorry abt that.. my mistake. The test anton has provided is the one.
(12 Jun '12, 21:23)

Answer is hidden as author is suspended. Click here to view.
answered 14 Jun '12, 09:14

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 answered 14 Jun '12, 23:18
1
Hey, your test fails on this : 1 2 ??1 This should give "NO" but yours gives 021 which is incorrect. You are missing out on using the k in the question properly.
(15 Jun '12, 14:51)

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 answered 15 Jun '12, 14:55

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. answered 15 Jun '12, 15:58

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 thanks in advance :)