2009 Pacific Northwest Regionals - solutions
Post date: Jul 29, 2013 8:22:51 AM
This is the first (hopefully not last) of a series in which I describe solutions1 for a problem set and provide code2 implementing said solutions. I'll try not to assume that the reader is already familiar with all the general algorithms, although in those cases I will probably just provide a link instead of boring everyone who already knows about what, say, BFS is with a very lengthy explanation of it.
This problem set is from the 2009 Pacific Northwest Regionals. It's not a terribly difficult set (which goes to show how good I am - a couple of the solutions aren't even mine), but hopefully you the reader can get something out of all this.
Problem A - The Navi-Computer is Down!
The preamble has some great dialogue, none of which is actually relevant to the actual problem3. The only formula you need to solve the thing is already given to you! So this is a pretty easy problem, since all the numbers are given in the input: read the numbers, calculate the distance, and output it. There is one annoying thing, though; that's the names of the systems that could be more than one word. Using getline() is fine; just remember that in conjunction with cin, you'll have to call it more than once to get the data you need.
Problem B - Blenjeel Sand Worms and Color Wriggles
This is really hard for a problem that is actually just BFS. The worm could wriggle in eight different directions from a given position; either end could move up, down, left, or right. So coding this is a pain, even though ultimately it's just a BFS in the end. One small caveat is the fact that the worm could do something like this (excuse the bad drawing):
i.e. move onto a square that it's leaving.
Problem C - This Can't Go On Forever
Not much to say here - a fancy number theory solution may exist4 but it's definitely not required here. Looking at the given series examples makes it clear that the series cycles at the values 0, 1, so we just have to iterate until we find those two values again. Also since the mod value is less than 224, we don't need to worry about using anything larger than 32-bit ints as long as we keep using mod.
Problem D - Rescue Beacon (Thanks to Karlming Chen)
The first thing to note here is that we can take the three points specifying a face and get its normal vector out of it:
Now if we consider the incident light as a vector pointing from the interior of the crystal out, a face will reflect the light if and only if the dot product between the incident vector and the face's normal vector is above zero (or equal to zero, if the vectors are perpendicular to each other, although the problem states this doesn't matter). The problem can then be restated: given any incident vector, what is the maximum number size of the set of normal vectors such that the dot product of the incident vector with any vector in the set is positive?
If we try to solve this new problem, we'll get stuck because the incident vector is completely arbitrary; it could be anything and we'd have to do some sort of brute force thing5. Instead of fixing the position of the normal vectors and selecting a incident vector, let's do the opposite: fix the incident vector (WLOG we'll set it to point upward, i.e. in the positive z direction) and rotate the normal vectors. Also, we can replace the normal vectors with points on a sphere (the unit sphere, so we normalize all the normal vectors). Now, the number of faces that reflect light is equivalent to the number of points in the upper hemisphere. The problem then is: what rotation of the sphere gives the maximum number of points in the hemisphere? (picture not provided because I definitely don't trust myself with drawing a sphere properly)
A naive solution would be to take two points, calculate the great circle defined by the points, and find the number of points in each hemisphere. But this is O(n3) runtime - with n = 2000, this would almost certainly not run in three seconds6. Alternatively, we can, for each point:
- Orient the sphere such that the point is at the north pole. (O(n) runtime)
- Sort the remaining points by longitude. (O(n log n) runtime)
- Sweep across the longitude to find the greatest number of points that lie within a range of pi radians. (O(n) runtime)
The total runtime is O(n2 log n), which will safely run in time. The only spot of bother is the first step of rotating the sphere. The smart way would be to use projections and such; the easy dumb way (my way of course) would be just to rotate the given point about the x- and y-axes to the point (0,0,1), then rotate the other points using the same angles. As it turns out, it wasn't actually that easy and it involved using some rather shady code in the code archive...apparently the code labelled "UNTESTED, USE AND PRAY" worked correctly though.
Problem E - Let the Wookiee Win!
This is another simple brute force problem. There really isn't a lot to this one - there's guaranteed to be one and only one move that is not a winning move for either X or O. Though it's probably better to write a function that takes a general move of either X or O, instead of just copying the code twice - in general, if you have a bug somewhere, it's easier to fix it once in a general function instead of needing to remember where to fix it in many copies of not quite identical code, and it could quickly get messy.
Problem F - Laser Turret Maintenance
Yet another brute force problem. Everything is given to you - you just have to do what it says. I did have some fun with coding this up though. Note that every one of the transformations can be represented by a combination of only two basic transformations: rotation of the matrix by 90 degrees clockwise, and flipping the matrix vertically. Thus, using these two operations in conjunction with copying matrices (they can't be done in place), everything can be done with a few simple letters. So the code here is sort of obfuscated...more reason for you to code up your own solution.
Problem G - George Lucas and 1138
After some thought, an elegant solution seems to be out of reach. This is suggested by the rather low bounds on n (1-7 inclusive) and the fact that it's...really hard to figure out whether you can get a specific number from the given string without just resorting to brute force. My solution resembles a sort of bottom-up DP.
The subproblem is: given a subset of numbers from the input string, what are the numbers that can be obtained from combining (all of) the numbers in the subset? For the base case, where the subset is of size 1, you can only get the number in the subset itself, since you can't combine it with anything else. For size 2, you can combine the results you previously got from size 1, as long as the two subsets you are combining do not overlap (i.e. the combined indices of the index string you select for both subsets must all be distinct). For size 3, you can combine results of sizes 2 and 1. For size 4, you can combine results of sizes 2 and 2, and sizes 3 and 1. And so on.
I probably didn't explain that very well. Let R(s) be the range of numbers you can get from combining numbers in s together, where s is a subset of the input string (e.g. for a 3-digit input string, s could be {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, or {0,1,2}). When s is of size 1, R(s) = {t[s]}, where t is the input string. Now if you had two distinct subsets s1 and s2, where s1 ∩ s2 = ∅, you can calculate R(s3) = R(s1) × R(s2), where s3 = s1 ∪ s2 and × denotes the Cartesian product. And that's it, really. Since n ≤ 7, the maximum number of subsets is 2n - 1, so there's no worry of time/memory limit there. And as it turns out, |R({0,1,...n-1})|, the size of the set of numbers you get from combining all the numbers together, only goes up to about 17000 in the test cases, so that's fine too.
Once you have the final set, R({0,1,...n-1}), we're set (pun intended): just go through each integer starting at 1 and output the first one that is not in the set.
Problem H - Spare the Ewoks! (Thanks to Paul Liu)
This is another DP, although it's quite a bit more involved than the previous problem.
Some thought reveals that there are a small number of cases to consider pertaining to the positions of the areas chosen:
and it's obvious that the red cases are all rotations of each other (same with the blue cases) so there are really only two general cases we need to consider. Also, note that the regions dictate where a chosen area could be located. So in other words, the two cases are a) where the areas are separated by a horizontal and vertical line and b) where the areas are separated by either two horizontal or two vertical lines.
We now consider two separate arrays, whose values can both be determined with DP:
- dp1_ul[i][j]: the maximum area that can fit in the rectangle with corners (0,0) and (i,j)
- dp2[i][j]: the maximum area that can fit between the vertical lines x = i and x = j
Note that I used the name dp1_ul instead of dp1; this is because we can actually create four arrays pertaining to dp1:
- dp1_ul[i][j]: the maximum area that can fit in the rectangle with corners (0,0) and (i,j)
- dp1_ur[i][j]: the maximum area that can fit in the rectangle with corners (0,n-1) and (i,j)
- dp1_ll[i][j]: the maximum area that can fit in the rectangle with corners (m-1,0) and (i,j)
- dp1_lr[i][j]: the maximum area that can fit in the rectangle with corners (m-1,n-1) and (i,j)
Now, the first case (the red cases in the above picture) can be solved with three of the dp1_* arrays, and selecting every possible intersection of the horizontal and vertical separators. And the second cases (the blue cases) can be solved with two of the dp1_* arrays, and using the dp2 array for the middle area.
If we know how to generate the five DP arrays, then we can solve the problem; the only thing is, how do we generate them?
For dp1_*, we will only consider dp1_ul, as the other arrays are very similarly generated, with the only difference being the orders of iteration for the variables. Our equation is:
dp1_ul[i][j] = max(dp1_ul[i-1][j],
dp1_ul[i][j-1],
largest allowable area with corner at (i,j))
where we just define dp1_ul[i][j] = 0 if i < 0 or j < 0. The first two terms seem simple enough, but how do we find that last term? We need a new matrix (call it p[i][j]) that holds the number of consecutive values of 1 (1 is an empty space, 0 is an Ewok home) to the left of (i,j) in the original map, including the point (i,j) itself. For example, if we had a map like:
0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 then p (p for profile) looks like:
0 1 2 3 0 0 0 1 2 0 1 0 1 0 1 Now we can calculate the largest allowable area as:
In other words, we iterate from (i,j) to (0,j) (i.e. from the point (i,j) upwards), keeping track of the minimum value of p[i][j]. This is the width of the maximum allowable area. Then we multiply by the length: if we are at (k,j), then the length is i-k+1. If we keep track of the maximum value of this, then we will end up with our desired maximum allowable area with bottom right corner (i,j). Note this iteration is in linear time, and there are n2 values of dp1_ul to fill; thus, we can fill dp1_ul in O(n3) time, which is acceptable.
For dp2, we want to reduce the problem to the one-dimensional maximum subarray problem, which can be solved in linear time. We consider Ewok homes to have values of negative infinity, while free space remains at 1. Now, we build a partial sum (named ps) matrix, which obeys the equation:
ps[i][j] = m[i][0] + ... + m[i][j] where m is the original map.
Now to find the maximum subarray between columns c1 and c2 (c1 < c2), build a 1-D array (a) where:
a[i] = ps[i][c2] - ps[i][c1] where, depending on how you defined c1 and c2, you would modify those values in the equation to avoid off by one errors (e.g. in my code I use c2-1 and c1-1). Then run Kadane's algorithm (described in the Wikipedia link above) on the array a to find the value dp2[c1][c2].
To understand why this works, observe that ps[i][c2] - ps[i][c1] is equivalent to the sum of the values between m[i][c1] and m[i][c2]. If one of these squares is occupied by an Ewok home, then the sum will be equivalent to negative infinity. The sum wil be positive if and only if all squares on the map, in that row, are free space. This takes care of one dimension; running Kadane's algorithm across the length of the map takes care of the other.
Note that as with dp1, we could duplicate dp2 into dp2_hor and dp2_ver for the two separate cases in which the lines separating the areas are horizontal and vertical, respectively; I'm too lazy to rectify what I've already written though so I'll just say it's an exercise left to the reader.
So we're finally done! We just need to go through all the points mentioned earlier to find all the candidate values, across the six different cases, and output the largest one we get.
To make things a bit easier to code (sacrificing execution runtime in order to do so), we don't actually need to calculate four dp1_* values, and throw three of them together four separate times for four cases. Instead, we can calculate three (namely dp1_ul, dp1_ur, and dp1_lr), calculate dp1 and dp2, then rotate the matrix, calculate new values for the three dp1_* arrays and dp2, and so on for four rotations. (Note we only need to calculate dp2 for two separate rotations.) This slows down the solution significantly (you're calculating 12 dp1_* arrays instead of 4), but you might have a chance at maintaining your sanity since you really only need to write one function to generate the arrays and calculate a max value from them. Also, if you already wrote rotation code for problem F, like I did, you can reuse that code (making sure to extend the given map in one dimension so it becomes square, if necessary).
Problem I - The History of the Sith Rulers
Another simple implementation do-what-you-are-told problem where the limits are again very small so you can afford to be a bit sloppy with your algorithm. I used a vector of a long double/string pair, which I populated with the end dates and names of the rulers for the given year, then sorted it and printed the names. Of course, there are a myriad of other methods of doing this problem.
I have a habit of making geometry problems unnecessarily complicated in both mathematical calculations and code implementation. So you probably don't want to know how exactly I did this problem...but here goes:
The standard trick for dealing with reflection, instead of finding intersections of lines and reflecting angles and accumulating floating point errors that build up and all that icky stuff is just to use the projection of the image, e.g.:
When you draw a line from the droid in the original square to a Jedi in a different projected square, you'll intersect some number of horizontal and vertical lines that separate the projected squares. Quite conveniently, this happens to equal the number of reflections. So you can generate a diamond of projected squares, where there's an image of a Jedi in each of them, and the distance from the droid in the original square to the Jedi image is easily calculated. Since the distance is equivalent to the time (based on the given units), we just need to find the valid distances and get the smallest interval between separate ones.
There are a couple of hitches though. Firstly, the line drawn from the droid to a Jedi image could go across another Jedi image. In other words, if you wanted to hit the Jedi with some number of reflections n, your shot might hit the Jedi before the shot has reflected n times. And secondly, you might have two shots that hit the Jedi from the exact same angle, which is invalid.
I offer no advice for how to unhitch these hitches7; if you're really interested in seeing how I did it, then look at my code.
The last problem is a question of finding the number of spanning trees of a graph, where the nodes are either . or P. Coincidentally (really though, not a coincidence at all), this number can be found by Kirchhoff's theorem, which appears to have absolutely nothing to do with circuits.
Following the instructions laid out in the Wikipedia page (generate Laplacian matrix, remove a row and column, find the determinant) seems simple enough, but the requirement that you output the answer mod one billion is a bit worrisome. Sure enough, the answer is really big, larger than what C++ can deal with in 64 bits. So you either have to a) suck it up and use Java8, or b) find or write some arbitary precision integer library in C++. I have code for both options; other than the fact that they are written in different languages, they do exactly the same thing. Credit goes to Paul Liu for the C++ library (and apparently on to some guy on Codeforces that Paul got the library off of).
Note on the footnotes: can you tell I've been reading a lot of David Foster Wallace recently?
1None of my solutions are "the" solution to a problem - a la Perl's "there's more than one way to do it". If you submit code for a problem that runs in the specified time and memory limits and outputs the correct answer, that's a solution. I am simply describing the solutions I came up with, which may be completely different than the solutions you come up with if you study the problems. In any case, however bad my solutions are, they are still solutions. So if you're stuck you at least know what I did can be done.
2Similarly, my code should not be taken as canon. It should simply be viewed as code that happens to work for the given problem. The code is commented simply to outline my thoughts behind my code. You probably won't like it anyway, since it's my code and not yours so it very likely doesn't follow your specific Coding Style. But that's fine. You should be coding solutions yourself for practice (since an accepted answer is composed of not only figuring out the solution on paper, but actually coding it up as well). Looking at my code should really only be a last resort.
3Scanning a problem quickly to find the relevant information can earn you a couple minutes in a contest situation, but it's quite dangerous: if you make a silly mistake you've added 20 minutes to your time penalty, while if you just took a few extra minutes to read the whole thing and double- and triple-check your code you'd be better off. I am definitely guilty of doing the former.
4There may be times when a fancy number theory solution is in fact necessary, e.g. the bounds are too large or the time limit too small or both. It's good practice to look at the bounds, try to figure out whether an easy brute force solution would run in time, and if so do it. And for this problem, brute force is definitely good enough.
5Actually, brute force does work for this problem - see Daniel Lu's solution which finds increasingly precise ranges of the optimal normal vector. So again, there is almost always more than one way to solve a problem; we'll continue with the slightly more elegant solution.
6Here, the rough estimate of the total number of calculations is 20003 = 8000000000. Modern computers have a clock frequency of 2-3 GHz, so eight billion is probably too large (and we don't take into account the actual number of instructions being executed, which will add a constant multiplicative factor). Generally, one billion is about as high as you can go without hitting the time limit (if the time limit is three seconds). Given the bounds and the time limit, you can usually figure out the maximum allowable complexity of the algorithm you need to create, e.g. if n = 1000000 you'll need something that runs in O(n log n) time or better.
7Okay, here's Paul Liu's code where he does something like searching with BFS such that all the slopes are only considered once. Much more elegant than what I did.
8Definitely not biased here. While we're here, I might as well say that it's my belief that Java is only useful for its arbitrary length integers, and if there's a problem that requires it but also has tons of input such that BufferedWhatever is required, I'm writing my own arbitrary length integer C++ library during the contest.