Блог пользователя TheLethalCode

Автор TheLethalCode, история, 4 года назад, По-английски

In my hundreds of submissions, this is my first time encountering this Singular Iterator Runtime Error. In my submission 86437246, after passing the first few cases and when it encounters a relatively bigger input, the program exits with a RE. After looking at the diagnostic hints, I think it has something to do with singular iterators ( which is sort of equivalent to uninitialized pointers ), though I couldn't pinpoint where. But if I were to make a guess, I would say vector< pair< int, int > > which[1050] should be the source of the problem as after using some alternatives for it, I managed to get my solution accepted (86437933).

It would be very helpful if someone can throw some light on where I went wrong, so that I could avoid this in my future submissions.

**UPD:- ** It is a normal out of bounds error. Increasing the size of vis array takes care of it. Corrected submission — 86473660. Thanks WAontest2

Thanks a lot!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор TheLethalCode, история, 4 года назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • -44
  • Проголосовать: не нравится