codechef aug12

Other problems:
why my segment tree got WA?
some 10^8 solution got TLE, which is strange.

block game: why I didn't realize it is the stable marriage problem, and my idea is very close on the last day?
Just found a very stupid bug in my code, I am implementing exactly the algorithm but confused in two indexing arrays. Easily ACed after that.

OK, now I can describe my approach. The problem looks a bit confusing, and in fact the statement has to be rewritten to clean up some ambiguity. Quite a few coders got AC before rewritten and I guess they are good at guessing what the problem setter has in mind because great coders think alike. The confusion mostly comes from the intent that the setter is trying to hide the trick in the problem. Or he does not want people to realize what the constraint really meant. shangjingbo is a top coder, that is no question, just the way the problem was phrased make me a bit disappointed, although I did read the problem correctly. Another evil part of the statement was that you output -1 if there is no solution. In fact, this can never happen, as the existence of a solution can be proved.

Let's read the problem first. Each boy visits each house at a different time, also a house can never have two boys at the same time. Now we need to find a mapping from boys to houses, such that after boy B locked at house H, nobody can visit house H later. The implication is that, for any boy, they cannot visit H, and any house on his schedule after H. For example, if a boy B1 visits H1, H2, ..., Hn in order of time, and H = H3. then after another boy B2 was locked to H3, boy B1 can only visit H1 and H2, houses from H3 to Hn are not available to B1 now.

At this point, it is clear that we can simulate the game. Let all boys pick up their first choice of house in their schedule. As long as there is a conflict, that is, a house is shared by two or more boys, we find such a house, then find the boy in that house with minimum time. This boy must be able to visit that house before all conflicting boys, so we move this boy to his next house. In the end, if we end up in a state that all boys get a different house, then we have a solution, otherwise there is no solution.

Now we show that there is always a solution. The reason is, the only case when there is no solution is that a boy was moved beyond his last, the n-th house. But this can happen only after all the n houses were taken. Since a boy can take only one house, the other n-1 boys cannot take all n houses. So there is always a solution.

Clearly if our algorithm stops, then it finds a solution. On the other hand, if there is a solution, then the algorithm always finds one. Intuitively it is clear, but I do not have a good proof than the one based on stable marriage problem. A high level argument is that we started with all boys take their first choice and keep them as happy as possible, any time we were forced to move a boy, we move the boy that has to do so, because it is the one that is able to visit the house before its peers hence was able to advance to its next choice.

Lessons learned:
In the final output code, I should wrote myindex[i] instead of location[i]. Two ways could possibly avoid this mistak:
1. do not use location[i] as global, then it will not be visible in the final output code part.
2. keep some note of key data structure, or be careful and take note of variable renaming.
3. have a proof of what I am trying to do, as I am not convinced about my algorithm which is a bad thing.


machine gun: I know it is bipartite matching, just my hopcroft-karp implementation keeps getting TLE. The author (ktuan) and tester (laycurse) use the same Hopcroft-Karp algorithm but they must be running within 15s limit. Also ACrush's code runs within 8s. I heard severkplus mentioned that other people have graphs twice as big as his yet they had a better max-flow implementation and passed, while his failed.

Actually there is one simple but crucial observation, the graph has 4 disconnected components, based on parity of cell index, (odd, odd), (odd, even), (even, odd), (even, even), they cannot be connected. So we are dealing with 4 graphs each with size (700/2)^2 < 130000. This will run in time.

stunning difference:
laycurse solution runs 300x300 all F graph in 0.02s
my solution runs the same graph in 23s

A stupid bug, when running multiple testcases,forgot to initialize globals, in particular, ans is not reset so it accumulates previous counts!

optimizations:
1. the graph is of 4 parts based on (odd/even, odd/even) also essential
2. each component is bipartite with (x+4, y+2) vs (x+2, y+2) also essential
3. when reset visited[][], only reset those entries that you actually set, this requires remember all nodes visited in the current DFS augment
4. map (i,j) into N1++, N2++, this one is essential
5. use +1, -1 to find neighbors, eliminate +2 then /2
6. check bounds with if expr instead of inbound() call, there are too many calls