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:
-
For K=1 replacement is possible only for N=1 and that would be “0”.
-
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. -
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:
-
For K=1 replacement is possible only for N=1.
-
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. -
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).
