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

×

CAKEDOOM - Editorial

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.

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:

This question is marked "community wiki".

asked 12 Jun '12, 01:09

vamsi_kavala's gravatar image

3★vamsi_kavala ♦♦
76131818
accept rate: 0%

edited 25 Dec '12, 15:05

admin's gravatar image

0★admin ♦♦
15.9k347484508

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

(15 Jun '12, 07:58) rahuldubey74742★

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

(15 Jun '12, 08:01) rahuldubey74742★

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.

link

answered 12 Jun '12, 22:59

shubh09's gravatar image

4★shubh09
11617
accept rate: 0%

I think this was giving me a few wrong answers initially :)

(15 Jun '12, 15:57) pragrame ♦♦6★

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.

link

answered 12 Jun '12, 04:50

lazzrov's gravatar image

4★lazzrov
136118
accept rate: 0%

2

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.

(12 Jun '12, 04:54) anton_lunyov ♦6★

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

link

answered 12 Jun '12, 02:19

bilbo_dhawal's gravatar image

1★bilbo_dhawal
161
accept rate: 0%

7

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

(12 Jun '12, 02:39) anton_adm ♦♦2★

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

(12 Jun '12, 03:26) bilbo_dhawal1★

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

link

answered 12 Jun '12, 07:24

shubhamgupta30's gravatar image

2★shubhamgupta30
1
accept rate: 0%

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

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.

link

answered 12 Jun '12, 12:14

rgaberina's gravatar image

2★rgaberina
1
accept rate: 0%

1

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?

(12 Jun '12, 13:52) anton_lunyov ♦6★

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

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) anton_lunyov ♦6★

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

(12 Jun '12, 21:23) kaush_adm0★

admin plz provide ur test cases

link

answered 12 Jun '12, 14:51

rijin's gravatar image

2★rijin
15112
accept rate: 0%

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

link

answered 14 Jun '12, 23:18

franky's gravatar image

1★franky
7123
accept rate: 20%

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

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

link

answered 15 Jun '12, 14:55

ankitdbst's gravatar image

2★ankitdbst
12
accept rate: 0%

edited 15 Jun '12, 14:56

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.

link

answered 15 Jun '12, 15:58

sudeep123's gravatar image

2★sudeep123
1
accept rate: 0%

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

Here's my solution if anyone's interested:

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

link

answered 16 Jun '12, 00:32

arnab_das's gravatar image

3★arnab_das
11
accept rate: 0%

Code-http://ideone.com/h6wzu

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

link

answered 16 Jun '12, 14:18

kapish_04's gravatar image

3★kapish_04
11
accept rate: 0%

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

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

link

answered 17 Jun '12, 14:57

neeraj_nitd's gravatar image

3★neeraj_nitd
11
accept rate: 0%

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

link

answered 13 Sep '13, 14:41

crg91's gravatar image

3★crg91
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:

×11,590
×780
×716
×15

question asked: 12 Jun '12, 01:09

question was seen: 3,933 times

last updated: 06 Jul, 19:03