[JOISC 2016] Sandwich

Difficulty Ratings

Idea Creativity: 3/5
Techniques Used: 3/5
Implementation : 2/5

Link

Simplified Chinese, Japanese

Statement

There is an $N \times M$ grid, each cell is a square. We draw a diagonal line (can be in one of both directions) in each cell and split it , and now we put a sandwich in each of the $2NM$ isosceles right angled triangles. We can eat a sandwich $X$ if
1) There are no sandwiches $Y$ adjacent to $X$ on both of the two shorter sides or
2) THere are no sandwiches $Y$ adjacent to $X$ on the longer side.
Find out for each sandwich, the minimum number of sandwiches that you need to eat so that you can eat it, or output -1 if impossible. $N,M \le 400$.

Solution

It is hard to make use of the grid property, so lets first model this problem into a graph problem. Consider we make two nodes for each square, one for each sandwich out of the two being eaten first. Obviously if you have eaten one sandwich in the square, you would eat the other immediately as well. We then draw dependency directed edges in this graph, meaning that if i want to eat this sandwich in this way, i must each that sandwich in that way. It is similar to the concept of solving 2-sat. Then, to find out the answer, you basically have to find out the number of nodes $X$ can reach for each $X$, and whether it would reach a cycle. If you do a dfs from each node then you can have a complexity of $O(N^2M^2)$. You can optimize with bitset but it is not what i want to talk about.

Let's go back to the grid. Look at each row seperately. You can realise that it forms two chains. In turns out that we can compute answer to a chain in $O(NM)$. You start computing answer from the last member of the chain. Then when you go up, we realise that no nodes will turn from unreachable to reachable. Therefore, we can keep the results in our dfs. As each node is visted in the dfs at most once, the complexity is $O(NM)$. Therefore, we can solve for each row and the answer is $O(N^2M)$.

Comemnts

I went for the wrong direction in this problem. Usually in these kind of problems you either focus on the grid or focus on the graph, but this time it is sort of in the middle. It is also tricky that we answer the queries in amortized complexity, instead of something like $O(N)$ for each sandwich.