cyfra wins the Wildcard round!
Discuss this match
Thursday, November 1, 2007
Introduction by Olexiy
moh_taha_eg has provided yet another excellent play-by-play. Be sure to check out the action from the Wildcard round.
by misof
RandomWalks
Each time we want to make a new move, at least one of four directions is available. Thus the expected number of random attempts necessary to find a good direction is at most four. As we have to simulate at most 200,000 steps, this tells us that we'll need to check roughly 800,000 attempts to make a step.
The first possible approach is to use some balanced data structure to store the segments of the generated path so far. The simplest way how to implement this is to represent each segment by four integers -- the coordinates of both endpoints. Now, to check whether our next step is allowed, we simply check whether our data structure already contains the segment that corresponds to the move we want to make.
A relevant part of C++ code:
typedef pair<int,int> PII; typedef pair<PII,PII> edge; set<edge> used; // ... while (1) { int d = nextDir(); int nx = x + dx[d]; int ny = y + dy[d]; edge E( PII(x,y), PII(nx,ny) ); if (used.find(E) == used.end()) { used.insert( edge( PII(x,y), PII(nx,ny)) ); used.insert( edge( PII(nx,ny), PII(x,y)) ); x=nx; y=ny; path += directions[d]; if (path.size() > 200000) break; if (x==0 && y==0) break; } }
The second possible approach was to allocate a large two-dimensional array, and to "draw" the path right into the array. Should the path leave the array, return an empty string.
At the first sight, such a solution should not work. It would seem that we would need an array that is 100,000 long in each dimension, and that goes far above the memory limit. However, there is one important issue -- our path is random. It is extremely improbable that a closed path of less than 200,000 steps should leave very far from the origin.
In fact, for our problem an array reaching from -600 to 600 in each direction was sufficient. Of course, in a contest one should allocate as much as fits the memory limit, just to be on the safe side.
Overhang
How to pick the beam where it is best to attach the load? We will try all possibilities and pick the best one.
Once we decided which beam carries the weight, we have to distribute the remaining ones so that our beam is as far to the right as possible. We will show that this can be done in a greedy fashion.
First, consider the beams above our beam. The only two things that matter: First, they have to form a stable configuration. Second, their total center of mass must be above our beam, but we want it to be as far to the left as possible.
We will simply place these beams so that their centers are exactly above the left end of our beam. This configuration is obviously stable, and its center of mass is exactly at the left end of the beam that carries the load. (Thus counterbalancing the load as much as possible.)
Now we include our beam and the load into the configuration. We can compute its current center of mass, and treat it just like a beam with the total weight of all current beams and center at that position.
What remains is to add the beams below our beam. We will add these beams one at a time, each time computing their optimal placement. The point is that in each step we want to move the total center of mass as far to the left as possible -- we gain nothing by making a suboptimal choice at some point, it won't help us later. Thus each time we are adding a new beam, we want to place it as far to the left as possible. The leftmost valid position is when the right end of the beam coincides with the current center of mass.
After we placed all the beams, we have to place the entire structure on the rooftop so that its current center of mass will be exactly on the edge of the roof.
Polygon
Coordinate compression is probably the easiest way how to solve this task.
Take the X coordinates of all vertices, sort them and remove duplicates. Let the resulting sequence be x1, x2, ..., xk.
Now, these are the only X coordinates where something interesting happens. If, say, x2=47 and x3=59, we can be sure that the columns 48 to 58 are all exactly equal.
We can now split all the lattice points inside the polygon into 2k-1 groups: one for each x coordinate where some vertices lie, and one for each group of columns in between these coordinates. For each group, we can easily compute how many lattice points does each column of the group contain.
(For columns that don't contain a vertex we just take all horizontal edges that pass through the given group of columns, sort them according to their Y coordinate, and sum the lengths of intervals between edges at even and odd positions. For columns with vertices one has to take vertical edges into account, but the idea remains the same)
Now, given K, we can use a simple linear search to find the exact X coordinate where the K-th point is. Moreover, we can compute its order in this column as (K minus (total number of points in previous columns)).
We are left with a one-dimensional version of the original problem, and that can easily be solved in a similar way.