WakeUpToReality's blog

By WakeUpToReality, history, 10 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.

Full text and comments »

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