TheLethalCode's blog

Problem 1114D (Flood Fill) — Incorrect Jury's Solution
By TheLethalCode, history, 5 years ago, In English

Edit:- I misunderstood the problem statement, my bad. There is no problem with the Jury.

So, while solving random problems from the problemset I came across the problem 1114D - Flood Fill. After wracking my brain for so long I couldn't come up with any solution within the given constraints.

But when I looked at all the submissions, almost everyone approached it in the same incorrect way. It is wrong, as I have a counter test cases for these solutions, which are almost the same as the editorial.

For example, let's take the editorial submission — 49738289 . For the test case

5
1 2 1 3 1

Actual Answer

It's obvious the answer is 2. Change the 2nd and 4th cell into 1, and bingo you have the same color everywhere in 2 moves.

Program's Output

If you run it locally and check, you will find it outputting 3. This, I believe , is also the Jury's Solution,

Actual Solution

I believe the actual solution is a DP which runs in cubic time, somewhat similar to the problem 1132F - Clear the String. But given the constraints, unless the test cases are weak, I highly doubt a cubic solution can pass. So the constraints as well as the Jury's solution needs to be changed.

  • Vote: I like it
  • -44
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

MikeMirzayanov neko_nyaaaaaaaaaaaaaaaaa can you look into this?

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Note that you have to choose a starting square and change its component each turn

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah, Initially I choose the 2nd cell as the starting square of the component and change its color to 1. After that I choose the 4th cell as the starting square and change that to 1 as well. I am not sure how the answer is going to differ.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      The starting square cannot be changed in each operation. It will be same for all the operations you do.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      You have misunderstood the problem statement, The starting square has to be chosen only once at the beginning of the game. And then each move will be changing the color of the connected component containing the sauare to any color of your choice.

      The 1 sequence of valid moves for your testcase will be :

      Initially, choose square 2.

      1) Change color of C.C of chosen sqaure to be 1. [ 1 1 1 3 1 ]

      2) Change the color of the C.C of square to be 3. [ 3 3 3 3 1 ]

      3) Change the color of the C.C of sqaure to be 1. [ 1 1 1 1 1 ]

      So, the answer is 3.

      Initially the C.C is just square {2}, but after first move it changes to { 1, 2, 3 } and after second moves it changes to { 1, 2, 3, 4 } and finally to { 1, 2, 3, 4, 5 }

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Ok, it is my mistake. I misunderstood the problem statement

      → Reply