Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
MOG Round #35 by otero1991 4 years, 11 months ago
Dear MOG users,
We are glad to announce the next rated round
MOG Round #35
which will take place on the
31st
of October at
9 a.m.
(Cuban local time) to celebrate Halloween
(in advance)
! It will have a duration of
2.5 hours
for solving
5-6 problems
.
UPD1: For technical reasons, we have to postpone the round to Oct. 31, 2019, 9 a.m. We are very sorry for the inconveniences this may cause.
UPD2: The problems are prepared by me ( otero1991 ) with the help of jc .
UPD3: The contest is over. Congratulations to dmga for winning this round!
UPD4: The contest has been rated.
UPD5: These are examples of solutions for each problem:
A:
https://matcomgrader.com/submission/140725/
B:
https://matcomgrader.com/submission/140857/
C:
https://matcomgrader.com/submission/140719/
D:
https://matcomgrader.com/submission/140718/
E:
https://matcomgrader.com/submission/140717/
We can discuss the solutions here if you like. The Editorial is not ready yet.
KhozmoS the idea behind the matching in this problem is the following. Let's focus on the positions with pumpkins at the end of the game. If it is the end of the game, there can't be two positions with pumpkins that share the row or the column (otherwise there are still possible moves). Therefore, in the end, the positions with pumpkins all have different rows and columns and are a subset of the original positions with pumpkins (since one can only move a pumpkin to a position that already has one).
We can see the positions in a grid as edges in a bipartite graph where the left side has the columns and the right side has the rows. In this case, we create a similar graph but only add an edge between a column and a row if there is a pumpkin at their intersection at the beginning of the game. An upper-bound to the maximum number of final positions with pumpkins is the maximum size of a subset of edges, where each column or row appears only once, i.e. the maximum size of a matching.
This is an upper bound but is easy to check that is attainable. If we have such a maximal set S of positions (where each position has a different row and column), any other position with pumpkins shares a column or row with them, otherwise it could be added to S and S wouldn't have maximal size. That means we can easily move any other pumpkin in positions not in S to positions in S.
This idea of seeing positions in a grid as edges in the mentioned bipartite graphs is helpful for other problems.
ale@smartware the problem from the link is the classic game, ....but in this case it was modified. The solution uses similar reasoning, without understanding the reasoning for the standard NIM I think is not possible to solve this problem (B).
I mean problem A.
I can't figure out how bitartite matching work in this problem, where can I find other problems solved with this approach, and with Max Flow Min Cut too.
@ale this game behave as usual NIM but with position with XOR sum equal to 0 banned. In this case winning positions are those where the XOR sum equals to 1. Why? If the XOR sum is greater than 1 there is always a move that takes it to 1 (with the same justification as in standard NIM), if the XOR is already equal to 1 you can't make the XOR sum equal to 0 since it is banned, but any move will change the XOR sum, though it will increase.
However positions with XOR sum equal to 0 can occur in the beginning of the game. In such situations, you should only check if you can make in your first move the XOR sum equal to 1 which is equivalent to find if there is any heap with odd numbers of candies.
In problem B ... why???
This time I didn't have time to prepare an Editorial. We can discuss the solutions here.
otero1991 Thanks , very clear.