The September 19 - September 25 week contained the first stage of Open Cup 2016-17: Grand Prix of Japan (
results, top 5 on the left). Some teams have competed on this problemset earlier during the Petrozavodsk camp, and two of those teams remained in first two places after everybody else joined - congratulations to Moscow SU Trinity and KTH Omogen Heap!
Problem I in this round possessed the right mix of simple statement and interesting solution, while not being very hard: you are given a connected undirected graph with at most 2000 vertices and 2000 edges, where each edge needs to be colored either red or blue. You need to do the coloring using a single alternating walk: you start in some vertex, then keep moving along the edges, coloring the first edge you pass red, the second blue, the third red again, and so on. You are allowed to pass the same vertex and even the same edge twice, and when you pass the same edge multiple times, the last color used stays. Is it possible to obtain the required coloring?
In
my previous summary, I've mentioned a super hard SRM problem: you're given a 50x50 grid, with each cell either free or blocked. You're also given at most 100 (potentially overlapping) 3x3 subgrids of this grid, and are looking to draw an L-shape or a C-shape in each of those subgrids in such a way that those shapes do not overlap, and use only free cells. An L-shape or a C-shape consists of 5 consecutive border cells of a 3x3 subgrid. There are 4 possible different L-shapes in each 3x3 subgrid, and 4 possible different C-shapes. You need to check if such drawing is possible, and if yes, find for each 3x3 subgrid whether it can have a C-shape as part of a valid drawing, and whether it can have an L-shape as part of a valid drawing.
The last part, which asks to see which shape each particular subgrid can have, does not really change the problem a lot - if we can solve the "is it possible" version fast enough, then we can just try placing each shape in each subgrid, and solve the same problem for the rest. So in the rest of this explanation I will concentrate on the "is it possible" part.
The key that opens this problem is: let's replace the 5-cell shape into four dominoes: a C-shape or an L-shape consisting of cells A,B,C,D,E in this order, can be viewed as a union of four dominoes: AB, BC, CD and DE. The eight possible dominoes along the border of a 3x3 subgrid can be split into four pairs of opposite dominoes (see an example on the left). Each 5-cell shape then corresponds to picking one domino in each pair of opposite dominoes.
One might say that this transformation is not accurate: not every way of picking one domino in each pair of opposites yields a valid 5-cell shape. However, it turns out that every way of picking one domino in each pair of opposites yields a set of cells that
contains a valid 5-cell shape inside (see an example on the right).
Because of this, the following reformulation always has the same answer as the original problem: can we pick four border dominoes in each 3x3 subgrid, one from each pair of opposites, in such a way that dominoes from different subgrids do not overlap?
Finally, now it's not that hard that we have an instance of
the 2-SAT problem: we have a few boolean variables (which domino to pick for each pair of opposites), and a few restrictions on pairs of values (stemming from the intersections). We can solve this problem in linear time.
Thanks for reading, and check back soon for the next week's summary!
