4942 - Zombie Blast!

A problem from south cal regional, slightly harder.

At first I thought it might require something like voronoi diagram since the straightforward solution is to find the nearest mine for each zombie. However I have never implemented voronoi diagram and the O(nlogn) time algorithm to construct voronoi diagram seems tricky. Looking at the contest, several teams solved it so there has to be other ways as not many people have implemented voronoi diagram.

Looking at the grid column by column, we know that for each cell in a given column j, for each row i we need only remember the nearest M from left, if our nearest M at row k is from left. We can also find the nearest M from the right. The better of the two is our nearest M for cell(i,j) at row k. So for each column j=0 to w-1, we can compute an array of near[0..h-1] such that near[k] is dist from the nearest M at row k. We can compute this for all columns j, so we have a matrix near[0..h-1][0..w-1],

near[i][j] is the column difference from nearest M at row i to column j.
It takes only O(n^2) time to compute near[][] so we are good so far.

Now we binary search the smallest radius that covers all zombies. The max is w+h, min is 0. And since w<=2000 and h<=2000, for a relative error of 1.0e-6, we need only iterate 30 times since 2^30=10^9. Now we deal with each radius. Given a radius, we need to check whether it is enough to cover all zombies. Again we look at each column. If some M is to cover anything in this column, it has to be a near[i][j]. So for each near[k][j], k=0 to h-1, we calculate the interval that near[k][j] covers at column[j], and we can use a vector to keep track of nonoverlapping intervals. Once we got all intervals for column[j], we can scan each cell in column[j] to see if every zombie in this column is covered. This way we spend only O(n) time on each column.

In the end we have a decision to make, more iteration gives better precision but might TLE. Tried 20 and 25, both got WA, so 30 is the next thing to try and got AC finally.

In the original problem number of zombie and mines are limited to 10^5 so might be slightly easier to deal with.

TC SRM 521

p500

n<=40 points on xy-plane, find number of subsets that fit in nxn square, where nlow <= n <= nhigh.

Both nlow and nhigh can be 10^8, as well as x[i] and y[i]. But notice that any subset of points has xmin, xmax, ymin, ymax, and that's only n^4 choices of them. For each choice we have a rectangle and we need to test if it can be fit into a square of size between nlow and nhigh. If it does, we then test each point and collect all points inside this square. We can record all subsets using long long bitmask since n<64. To fit a rectangle into a square, we need to limit rectangle never go off the limit of prev of min and next of max, and putting xval and yval into a set<int> helps.

However, I keep forgetting that the rectangle needs to fit into a square and then the sides of a square is equal. So if x2-x1 and y2-y1 are different, the side is at least max of the two.

kd tree

Seems kd-tree is one way to solve this problem
2010/2011 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST
Problem 7
Zombie Blast!

http://socalcontest.org/history/2010/socal2010.pdf

http://homes.ieu.edu.tr/~hakcan/projects/kdtree/kdTree.html

More info about kd-trees can be found in book :

M. de Berg, M.van Kreveld, M. Overmars, O.Schwarzkopf, "Computational Geometry (Algorithms and Applications) ", Springer, 1998.

CF #90

Being lucky that this one is unrated due to author's solution wrong in problem B.

This time I used an unusual strategy and started with problem C. A and B turned out to be trivial enough later so my estimate is correct. B is still tricky in a case when all cards are present in the q cards.

C is a DP problem. Work from day 0 to day n-1, try each hw between a[i] and b[i], and update next state. A state is (hw,day,last), means at that day, use a[last] and b[last], select hw as assignment. Then next state is (hw+k,day+1,l) or (hw*k,day+1,l) for l=last+1 to m-1, assume we sort assignments by increasing c[i]. The problem is made more complicated because we need to return the actual path, so for each state, we need to remember not only total hw so far, but also prev subject, and prev hw. My solution contained 3 mistakes:
1. when declare subject, should use long long for a and b, instead I used int.
2. day is off-by-one when reconstruct path, this should be easy to caught from the testcase, but I simply could not see it.
3. when try nexthw, we have only two options, hw+k and hw*k. I was instead looping over all a[next] to b[next], thinking that the constraints are small enough. However, they are just big enough to make 10^9 which gives a TLE.

After fixing these 3, got AC for problem C.

problem A and B can be done in 10min.

SCC in linear time

This is about computing strongly connected components in a directed graph. It is well-known that two DFS can do it in linear time.

The idea is to look at the DAG with each SCC collapsed into one node. Now if we do a DFS and if somehow we can start with a component with no outgoing edge, then we are good because all reachable nodes are in the same component. To this end we can do a DFS and we know that components finished last has no incoming edges. Why, an incoming edge cannot come from its ancestor because ancestors always finish after their descendants. This excludes tree edges and forward edges. The incoming edge cannot be a back edge because then the ancestor and descendant will be in the same component. So it can only be a cross edge from right to left. But then a component in the left always finishes before a right one so this cannot happen.

To conclude, a component finished last cannot have incoming edges. In particular, the component containing the root of the DFS tree finished last. Now if we reverse all the edges, then the component finished last does NOT have outgoing edges and every node in the same component is still reachable from each other. Put it another way, G and G(rev) has the same SCC. Now we just go through each node in reverse order of finish time and do a DFS to collect all nodes in the same component.

SRM 520 div2

Haven't been coding for a while so I picked SRM 520 div2 for a warm up. It seems topcoder's div2 problem is becoming easier, while I still haven't had a p500 in div1 yet.

p250 and p500 have very small instances so you can brute-force by enumerating all possible solutions.

p1000 is a very straightforward DP, just observe that you can work row by row and only need to remember previous row's pass and challenged counts. However, my solution simply won't pass the last testcase, and it is not for integer overflow. The real issue? I created DP array dp[55][4][4], which ought to be enough, but I made the first recursive call with (0,10,0), which index something dp[0][10][0]. And this is a disaster. After staring at the code for quite some time and printed some intermediate results, still no idea where went wrong. Looking at a few submitted solution and they have implemented the same thing. And finally, I realized that the first call recurse(0,10,0) is the culprit, and it passed.

OK, in the end I am happy to see all three problems passed.