WakeUpToReality's blog

Wrongly Hacked !! Justice on problem B, Codeforces Round #883 (Div. 3)
By WakeUpToReality, history, 18 months ago, In English

I am being wrongly hacked in the 1846B - Rudolph and Tic-Tac-Toe of the Codeforces Round 883 (Div. 3). The problem statement says that "It has classic rules of tic-tac-toe except for the third player who plays with pluses." This means that all the rules of the game are followed, except that one more player is introduced in the game (the only rule that is changed is the number of players). Hence, in a tic-tac-toe game, players play their moves ony-by-one, therefore it is not possible for a game to end in a win and have more than two empty cells ('.').

Proof:
Any player needs 3 moves to win the game, if we consider that the first player wins, which is the worst case, in that period the other players would have played 2 moves, the total moves being, 3+2+2=7, which leaves only 2 grid cells with empty cells.
The hack is made on the assumption that there is a win condition and the empty cells are more than 2, possibly 3 and the code's answer is being updated to an empty cell. But this is not possible and hence this is not a valid test-case.
My solution link : 212583249
The test- case which hacked my solution:
1
...
XXX
...
This is a win condition, with more than 2 empty cells. This should not be a valid test case.

Note:
I understand that the fifth sample also violates the classic rules, but if that was intended, it should have been mentioned clearly in the question, sample test cases are not an explanation of what a question is asking, and also the question was easy enough to not go through samples to understand a missing clarification in the question. I don't think this is what the problem setter wanted to tested in this problem, hence it also got accepted in the defaults testcases.

I don't exactly know who to tag, hence I am tagging MikeMirzayanov and the problem writers — natalina, Sasha0738, and vladmart.

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

Comments Comments (8)
| Write comment?
»
18 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The condition does not say that they must take turns. Moreover, Example 5 looks like a countertest. It also says game over. So it doesn't matter if it already is or isn't?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    are you aware of classic tic tac toe rules? if so you know they must take turns, the problem setters being lazy is not an excuse. Also wrong sample is just worse, its not helping your point

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

same here ...

due to the mentioned tic tac toe logic, i did not expect a case where a single player could play multiple winning lines that are not intersecting, however, the following case got my solution down on test 13 after the contest ended.

1

+++

+++

...

which is obviously an impossible case of a classic tic tac toe game, where players take turns ... i don't know if there something to be done about this, but i'm just stating what happended in case it is an actual issue.

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

    +++++ also in this case my code print two "+". I thing the authors should add this type of tests during contest or show something like this in condition or just don't add this as valid taste case. But anyway.

    → Reply
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

imagine becoming sucessfully green and throwing a house party and at the end becoming newbie again bro -103 what's going on?

→ Reply
»
18 months ago, # |
  Vote: I like it +21 Vote: I do not like it

username checks out moment

→ Reply
»
18 months ago, # |
  Vote: I like it +7 Vote: I do not like it

The problem describes the game "Tic-Tac-Toe" and explains player win conditions, all like the "real" game rules. Configurations like below wouldn't be possible in "real" 3-person Tic-Tac-Toe games during which 3 players {X, O, +} would play in turns. Example 5 is more like a contradiction to the problem description in a quiet and non-intrusive (to both problem writer and testers) manner. Hacking test cases added later are more like invalid tests.

XO.  OOO
XXX  OOO
X+O  +.X
→ Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

It was a weird statement tbh. I even got hacked on this problem due to such dots ( != '.' ) :33. At least, those 3 dots tests should have been in pretests. I think B's pretests were shit, but overall it was a nice contest .

→ Reply