(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Vasyl Antoniuk
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
CAKEWALK
PREREQUISITES:
none
PROBLEM:
Two players are breaking a chocolate bar of size N \times M into pieces. A player’s turn consists of choosing one piece and breaking it in two. Which player wins the game?
QUICK EXPLANATION:
This is a classic mathematical exercise. Notice that the number of pieces of chocolate increases by 1 in each player’s turn; initially, there’s only 1 piece and when the game ends, there have to be NM pieces (otherwise, there’s still some piece that can be broken). So the outcome of the game only depends on who makes the NM-th move - or equivalently, on the parity of NM. If NM is odd, the first player has to make the NM-th move and loses; otherwise, the second player has to make it and loses. Of course, this works in constant time.
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.