MasterMind's blog

[Confirmed] Weak test data of Problem B: Tinkoff Challenge — Elimination Round
By MasterMind, history, 4 years ago, In English

Hi there,

I solved the following Problem using $$$0-1$$$ bfs.

In the first submission 95671950 I got WA on test 7. I only changed the initial placement in the deque and got Accepted on this submission 95669200

Here is a picture that shows the comparison between the two submissions.

I suspect that the test data is weak (because both submission should get Wrong Answer Or both submission should get Accepted) or I am missing something about $$$0-1$$$ bfs.

possible

If you can shed some light into this, I would be thankful.

UPD: dorijanlendvaj has found a case that breaks my accepted solution, which means that the test data of the problem is weak or there is a problem with model solution. Thanks dorijanlendvaj

Test Case that should be added to test data

TestCase

I hope someone would add this test case using the uphacking feature

  • Vote: I like it
  • +7
  • Vote: I do not like it

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

If you do emplace_front, you're starting deque will look something like {start, 3}, {start, 2}, {start, 1}, {start, 0}, which is incorrect ordering, considering you are removing elements from the start.

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

    I'm not sure what you mean by "incorrect ordering", the problem is in weak test cases. Here's an example of the accepted solution incorrectly printing "NO":

    2 4
....
S.*T
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for providing a test case where the accepted solution breaks. I do not know if you can add this test case to the actual test data using the uphacking feature.

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

        Uphacking can only be done within 7 days of the contest ending. This contest ended more than 7 days ago so it's impossible to uphack.

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

    I am not sure how will that affect the answer, can you please elaborate more! The order here does not matter, or does it? if yes how?

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

Auto comment: topic has been updated by MasterMind (previous revision, new revision, compare).

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

Auto comment: topic has been updated by MasterMind (previous revision, new revision, compare).

→ Reply