2010 UBC Tryouts #1 - solutions

Post date: Sep 15, 2014 1:13:44 AM

Problem set and code. Original here. It is assumed the reader has at least read the problems.

Problem A - Paperboy

Since the paperboy can carry as many papers as he wants, we can rule out any kind of path that zig-zags between the houses in relation to the starting position. To see this, observe that if we start between two houses and go to the left (where we assume the houses to be on a left-right line), we need to visit the houses further to the left eventually, and so there's no reason to not do it immediately instead of going back to the house to the right.

Also, note that as the delivery time is 1 is constant for all houses, we can instead assign an instantaneous delivery time and just add n to our answer at the end. So we have two scenarios:

1. From the starting position, go to the leftmost house, then go to the rightmost house.
2. From the starting position, go to the rightmost house, then go to the leftmost house.

Note that we could potentially start off left of the leftmost house, or right of the rightmost house, so the absolute difference should be taken.

Problem B - Repechage

The winner of the tournament must have won N times; the second place finisher must have won N-1 times. If we keep track of who beats whom, using a map of a name of a person to names of the contestants beaten by that person, then we can combine the two sets of beaten contestants, one for each finalist, and sort that alphabetically to get the repechage.

Problem C - Happy Separation

If we make separate triangles out of the happy people and unhappy people, and the triangles don't intersect, we have a line that can fit in between the triangles and separate the two sets successfully. If they do intersect, we can't draw this line. Now, all we need to do is see if the triangles intersect - which might be harder than you think since apparently the polygon intersection code in the code archive is broken...

Alternatively, you could do what I did and create trial lines composed of two points from the same set. Take this to be the wall. (We are guaranteed no three points are colinear, so it's okay for the line to be directly on the two points, since we can move the line just off the points without messing anything up.) Now, the third point that isn't part of the wall must be on the opposite side of the three points of the other set, so we extend the wall to be a super long line segment, create a second line segment from the third point and a point from the other set, and see if those line segments intersect. If we get three line segment intersections out of three points, the wall is valid.

Problem D - Coin Stacks

Note that the sum of the pile sizes must be a power of 2, so if there are any piles with size congruent to 1 (mod 2), then there must be an even number of them. If we run the difference operation on all of these, we'll end up with a bunch of new piles, where all their sizes are 0 mod 2. Now if there are any piles with size 2 mod 4, there must be an even number of them, so we can run the difference operation on those, and so on for each increasing power of 2. We'd also want to combine similar piles whenever possible, since multiplying a pile size by 2 won't destroy any previous progress. In the worst case, we'd require 100 difference operations for 31 different bits, and 199 combine operations, which is well under the 10000 operation limit.

This is the "good", deterministic, consistent solution; I will now describe mine (which, mind you, got accepted) which is nothing of the sort. Potentially, this is more illuminating since I'll describe my thought process of actually solving the problem, but you can safely skip ahead to the next problem if you don't want to read my rambling.

So we start off with N piles, and our objective is to reduce them all to one. Clearly, the combine operation is ideal, as it permanently reduces the number of piles. If we can't do a combine, we'd want to somehow be able to run a difference operation, possibly many times, to get two equal pile sizes. The easy way would just be to randomly pick two indices to perform a difference operation on, but we might run into problems with time and the number of moves made; can we do better?

It turns out that if we have two unequal numbers that happen to sum to a power of 2, and we run the difference operation on them repeatedly, we'll eventually get two equal numbers. Why does this happen? I have no idea, and in a contest environment, I won't really care about a hard formal mathematical proof¹; all I did was try this for every pair of numbers summing to 64, notice it worked with a maximum of 6 moves (note 2⁶ = 64), then said it was good enough.

If this doesn't work, then we resort to picking two random numbers and running difference on them. So the control flow looks something like:

1. If we have one pile remaining, exit.
2. Check all distinct pairs of piles to see if their sizes are equal. If so, combine them, and go to 0.
3. Check all distinct pairs of piles to see if their sizes sum to a power of 2. If so, run difference on them until they are equal, combine them, and go to 0.
4. Choose two piles randomly and run difference on them, and go to 0.

The rationale behind this is that checking distinct pairs is quite fast (200 choose 2 = 19900), and running difference randomly is bound to eventually satisfy one of the two previous checks. In practice, this runs very quickly (all test cases are done in <0.8 seconds), and the maximum number of moves done for a test case is somewhere around 4-5 thousand. Obviously, randomization doesn't usually work, so take all this with a grain of salt, but in this case it happened to work and (maybe?) was the faster solution to figure out and code.

Problem E - Blind Maze

One extremely important subtle fact is that you don't actually have to find the minimum length solution, across all possible solutions. You only have to supply any one solution that gets out of the maze for every possible entry and exit and boulder configuration, that fails to get out of the maze for every possibility if the last character is removed. So if we had a valid string, we could run through every possibility and note the index at which we finish the maze, then take the maximum index and trim the string to that point.

Here is the deterministic solution, courtesy of Kent and Jason. Consider a maze as a graph, where tiles without boulders on them are nodes and valid paths between them are edges. Now, for every possible boulder configuration²:

1. Flood fill to separate the empty spaces into connected subgraphs.
2. For every connected subgraph, do a BFS simultaneously from all points, to find a sequence of steps such that no matter where you start, you end at the same point.
3. Starting from that point, BFS again to find a path that visits every other part in the connected subgraph.
4. Insert the sequences from 2. and 3. into a set to remove duplicates.
5. Concatenate all the strings from the set together.
6. Trim the string, as described above.

However, even though this seems all nice laid out in a list, as Jason's code demonstrates, it's really not that nice.

Here is an alternative, a non-deterministic solution courtesy of Paul, which (as most non-deterministic solutions are in programming contests) is probably not the intended solution, but is (at least in this case) much simpler. We can simply generate a string of 1000 random moves, and then trim the string to obtain a solution.

The key observation is that 1000, the string length limit, is a very large number compared to 9 and 12, the number of nodes and edges in the 0 boulder maze. For actual theory, it is known that the expected number of moves before a random walk hits all vertices of a connected graph is 2|E|(|V|-1), which is basically the "Paul discovered this when learning about randomized 2-SAT algorithms" theorem. In any case, it makes some intuitive sense; if we do a lot of random moves in a small maze, we'll be able to reach any point from any other point, regardless of boulder configuration. And since we can make up to 1000 moves, we'll be almost certain to satisfy the required condition, so we're already almost done: all we need to do is trim the string (and if we're really paranoid, keep creating random strings until the condition is satisfied).

Problem F - Monkey's Revenge

This is "just" a DP, courtesy of Paul. The goal is to match the given substring to the randomly typed string, and there are two states:

1. The length of the string used (n).
2. The length of the longest substring that currently matches (k).

If we match all of the substring, then any characters past that point can be anything, so that's 36 to the power of the number of letters remaining. If there aren't enough letters remaining in the random string, we can't match anything and return 0. Otherwise, we can brute force all the possible characters (a-z, 0-9) to attempt matching the next character in the substring:

• If there's a match, we can go to the state (n+1, k+1).
• If there's no match, we want to find the longest suffix of the substring (with the added extra character) that is a prefix of the substring. This can be done in a brute force manner. For example, if we have the total substring "abaab", we've currently matched "aba", and we add the character "b", we go to the state (n+1,2), since the longest currently matched substring is "ab". If the character is "x", we go to (n+1,0), since there's no suffix that matches any prefix.

Then the answer is the value at the state (0,0).

I haven't mentioned the mod 100003 requirement, because it's not that big of a deal; since 100003 is prime, we can mod all intermediate values with it without any trouble.

Obviously, this is a bit more difficult than I make it out to be, so if you're stuck at this problem hopefully you're inspired to code up a solution, which (big secret here) is actually how to improve at programming competitions, since you actually have to implement solutions that you think of.

¹Some discussion with Karlming reveals that one could probably do an inductive proof on increasing powers of 2, where the trivial base case is 1 and 3, and in the inductive step if your numbers are both even you can divide everything by 2 and if they're both odd you can run the difference operation once to get two even numbers. Or something like that. Details left to reader.

²This can be represented as a 9-bit bitmask.