UBC/SFU Qualifiers I 2011 + CCC 2013 Day 1 — solutions

Post date: Feb 10, 2015 9:42:21 AM

Problem set and code. It is assumed that the reader is familiar with the problem statements, and at least somewhat familiar with basic algorithms and graph theory and number theory and whatnot — basically lower-level university computer science, which is what I presume the main audience here is familiar with.

Problem A - Blocks Get

There are variants of this problem that are more difficult, but this is not one of them. We make the following observations:

• The blocks can be retrieved in any order; if we encounter a block at any time, we'll immediately take it back to the start location.
• The distance between the start and a block depends only on the difference between their Cartesian coordinates (details here).
• For every block, the distance added to the total is twice the Manhattan distance between the block and the start position, since we move from the start to the block, pick up the block, and drop it off back at the start.

So all we need to do is find the start position, then sum double the distance from the start to a block, for every block.

Problem B - Array Balancing

Keeping in mind the array limit of 400000, we would be able to figure out the answer if we found the balance of every subarray, iterated through every possible splice point, and found the smallest maximum balance of the resulting two subarrays. This would run in linear time.

Note that when I say “every subarray”, I don't actually mean every single one; that would require O(N²) memory usage, which clearly is too much. Rather, note that every relevant subarray will either contain element 1, or element N. We can thus maintain two arrays:

• b1[x], which stores the balance of the subarray A[1..x]; and
• b2[x], which stores the balance of the subarray A[x+1..N].

And to populate these, we can iterate through the array from element 1 to N, keeping track of the maximum and minimum and putting the difference in the appropriate element of b1[], then iterate through the array from N to 1 and do the same thing for b2[]. Finally we run through the array and pick the minimum value of max(b1[x],b2[x]) for 1 ≤ x ≤ N.

In all, we need three linear-time traversals of the array, which is fine as the array size is 400000 at most.

Problem C - Missing Number

Firstly, the infinite sum of all natural numbers is -1/12 (really!)…but we'll stick with the more well known formula of n(n+1)/2 for this problem. Basically, we set up the equation S ≤ n(n+1)/2 and find the smallest integer n that satisfies this. If this turns out to be an equality, i.e. S = n(n+1)/2, then no number was missing. Otherwise, we output n(n+1)/2-S.

This leaves the task of solving for n; we can either use the quadratic formula, or approximate n(n+1) as n² and take the square root of both sides. Both methods work.

Problem D - Fixing the Bridges of Königsberg

The question basically asks for the minimum number of edges to add to an undirected graph such that an Eulerian cycle exists. I won't go into a detailed proof, but whether a graph having an Eulerian cycle is equivalent to whether all its vertices have even degree (i.e. an even number of edges adjacent to every vertex). For some more rigour, read the Wikipedia page.

So you might think “well that's easy, all we need to do is count the number of odd-degree vertices (of which we are guaranteed there will be an even number¹), divide by 2, and output the result as the answer”. And so you would code this super simple answer up and submit and get a wrong answer.

Well that's not good. Why would this happen? Consider this graph:

The easy solution would add an edge between 3 and 4, making all vertices even degree, but there is no Eulerian cycle here, because the graph is disconnected. So our solution needs to account for disconnected graphs.

Thus, before counting up all the odd-degree vertices and dividing by 2, we have to ensure the graph is fully connected…but there is a slight caveat here. Recall that a graph is connected if a path exists between every pair of vertices. But we aren't looking to satisfy this; we want to create an Eulerian cycle, which only requires traversing every edge. Ergo, if there are any degrees with degree 0, we can ignore them completely.

Our procedure, then, will look something like the following:

1. Separate the (non-zero-degree) vertices into separate components.
2. If there is one component, we're done, and can do what we did before (i.e. count odd-degree vertices and divide by 2). Otherwise…
3. If there are two odd-degree vertices in different components, connect them with an edge, and go to 2.
4. At this point, if there are any odd-degree vertices, they are all in the same component. So pick a random vertex in a different component, connect it to an odd-degree vertex, and go to 2.
5. At this point, there are no odd-degree vertices. So pick two random vertices in different components, connect them, and go to 2.

The general idea is to connect all the components together while trying to reduce the number of odd-degree vertices, since those add to the total of required edges.

Once this is done, we can, as before, count the number of odd-degree vertices, divide by 2, and add this to the answer.

Problem E - Tank Fight

This probably looks like a boring tedious implementation problem at first glance and you would be correct. However, I happen to be quite good at boring tedious implementation problems. Or at least, I'm the only one willing to do them.

The first thing to note is that hit points aren't really useful here, since the damage each tank does is only dependent on which side it's on. Considering that you can't overkill a tank (i.e. an enemy's tank can't ever be at or below -12.3 HP, and your tanks can never be at or below -32.1 HP), some quick math shows that your tanks can take 4 hits from the enemy, and enemy tanks 27 from yours. To make things easier, we'll use EHP (effective HP) from this point; your tanks start at 4/4 EHP, and enemy tanks start at 27/27 EHP.

Next, we want to figure out is how your tanks fire, and how the enemy tanks fire. The hint is useful, and intuitively makes sense; your tanks' strategy, then, is to focus fire the enemy tanks in succession. The opposing strategy, which the enemy tanks use, is therefore to spread their fire. That is, they'll first hit all your tanks to put them all at 3/4 EHP, then at 2/4 EHP, and so on.

We note that the tank projectile time, 0.000987 seconds, is really really small compared to the attack speeds, and so this is negligible. The only important takeaway is that it's nonzero, so that if both armies fire at the same time, a tank that would take lethal damage is still capable of firing and doing damage before it dies.

Now, we can finally get around to figuring out the winner. We store two variables: the next time your tanks will fire (t_y), and the next time the enemy tanks will fire (t_e). They both start at 0. Then, we can increment the time until one or both armies have been completely destroyed. This (in my code) takes the form of an infinite loop, which is only broken out of if an army is at 0 tanks. Within this loop:

1. If t_y < t_e, then your tanks fire, and t_y is incremented by 1.23.
2. Otherwise, if t_e < t_y, then the enemy tanks fire, and t_e is incremented by 3.21.
3. Otherwise, at this point we know t_y equals t_e. Thus, both yours and the enemy's tanks fire, t_y is incremented by 1.23, and t_e is incremented by 3.21.

So the last thing we need to do is determine what actually happens when tanks fire, and how much damage they actually do, since presumably armies will start becoming weaker and deal less damage as the battle wears on. Define “firepower” as the number of tanks on a side capable of firing, so we'll have P_y as the firepower of your army, and P_e as that of the enemy army. Clearly, their initial values are N and M, respectively.

Note that firepower only depends on how many times the opposing army has fired. So if we keep track of how many times your tanks have fired total (f_y), and how many times the enemy tanks have fired total (f_e), we can calculate firepower. It's important to note that one tank firing results in one tank on the other side losing 1 EHP, regardless of which army's tank is firing at which.

For your firepower: it's unaffected until the enemy has put all your tanks at 1/4 EHP (which requires the enemy's tanks to have fired a cumulative sum of 3N times, i.e. f_e = 3N). Once the enemy has fired more than 3N times, then your tanks start dying, and your firepower is decreased by f_e – 3N.

For the enemy's firepower: every time f_y hits a multiple of 27, a tank dies, and P_e is decremented by 1.

To summarize, in fancy LaTeX:

Finally, we have everything we need to solve the problem. We can now run the infinite loop described above until either f_y ≥ 27M (you win) or f_e ≥ 4N (you lose) or both (it's a draw, which I don't think can actually happen…?).

Problem F - Paperboy

Intuitively, if the paperboy starts somewhere in the middle of the row of houses, it would make sense to deliver to nearby houses as often as possible, since the time is proportional to the number of papers being carried.

Formally, we can prove that there is an invariant: in the optimal case, there will never be an occurrence of passing a house that needs delivering without actually delivering a paper to it. To see this (wall of text ahead, you can probably skip this), consider a violation of this invariant, where we pass a house we need to deliver to, without actually delivering to it. If we start with X papers, travel distance d₁ to the house we skip, and continue on to the next house we actually deliver at, travelling an additional d₂ units, we'll take a total time of X×(d1+d2)+1. Keep in mind that we still need to deliver to the house we skipped, so we'd need to add another 1 at least, and our lower bound on delivering to both houses is X×(d1+d2)+2. But if we had delivered at that house, we would take a time of X×d1+1, and if we delivered at the house afterward, we would take an additional time of (X-1)×d2+1. This is a total of X×d1+(X-1)×d2+2, which clearly is less than X×d1+X×d2+2 = X×(d1+d2)+2, which is the lower bound on delivery time if we had originally skipped a house.

We can then use DP to solve this problem, where the states are:

• The house we're currently at.
• The number of houses we've delivered to that are located to the left, including the house we're currently at.
• The number of houses we've delivered to that are located to the right.

We can think of the path we take as a sort of zig-zag; at any given house, we can either go left to the first undelivered house we need to deliver to, or to the corresponding house on the right. So we find the time required to deliver the rest of the papers if we go to the left, then the same for the right, and pick the smaller of the two.

A few closing notes: the transitions of the latter two states are a bit odd (e.g. if they have respective values of L and R, going to the left means they would change to 1 and L+R, and to the right L+R+1 and 0). The house numbers in the input may not be necessarily sorted, so a preliminary sort is required. Since each house has a constant delivery time of 1, we can simply ignore it, and consider the starting house as a house to deliver to; then at the very end, when we have our final value, we add n. And in the case where we start at a house we need to deliver to, we would have a duplicate of that house, but when running our DP we would simply travel zero distance between the duplicates, so nothing goes wrong.

Problem G - All Your Base Belong to Palindromes

We first observe that to convert a number x to base b, we can repeatedly append x mod b to a list, and divide x by b (letting x become the floor of the quotient). I'm too lazy to prove this.

Because X can be up to a billion, converting X to every single base in the range [2,X) is infeasible. However, for all bases larger than the square root of X, X must be represented in two “digits” (where a “digit” can range from 0 to [base]-1). This can be seen by noting that if X is a perfect square, then X in base X^1/2 is 100. Thus, if a two-digit number is to be a palindrome, both its digits must be equivalent to each other. In other words, X = D×B+D, where D is the digit, and B is the base. Note D×B+D = (B+1)×D, and as D and B must both be integers, they can be determined by factoring X into pairs of factors (which can be done in O(X^1/2) time²).

For every base smaller than X^1/2, we can do brute-force conversion to the base and check if the resulting number is a palindrome. In the worst case, converting 1 billion to base 2 will result in a 30 digit number, so our runtime in that case is O(30×10^9/2), which is fine.

This is kind of a hacky solution, as we really only considered one special case that happened to save a lot of time, as opposed to generalizing and actually learning neat mathematical facts. But that's ACM for you.

Problem H - Tourney

This problem is pretty much an advertisement for the range tree. In fact, the tourney tree described is actually just a range tree, with max as the operation. Implementation details are left to the reader, but note that to run within time, all commands must be O(log N).

Yes, this “solution” is a total cop out, but that's because this is a rare occurrence of a range tree problem that requires minimal effort — usually there needs to be some more manipulation.

Problem I - LHC

The “length of the longest possible collider” is equivalent to the diameter of the tree. Finding the diameter for a general graph is an NP-complete problem, but for a tree it is significantly easier:

1. Run BFS from a random vertex (call this v).
2. Run BFS from the last vertex visited in the previous BFS (call this x). The diameter is then the distance from x to the last vertex visited in the second BFS.

To see why this works, we need to prove that x is an endpoint of the diameter. I'll outline a proof here: assume that this is false, which means there is a path between two vertices (call these a and b) that is longer than the longest path beginning at x. There are two cases: the path between a and b intersects the path between v and x, and it doesn't. In both cases, it's not too difficult to show that replacing part of the path between a and b with part (or all) of the path between v and x results in a new path of equal or longer length, which is a contradiction of the original assumption.

So finding the diameter is easy, but this is only half of the problem; we need to find the number of possible paths that can form the diameter.

We'll first solve a related problem: if we have a tree rooted at a vertex that we are absolutely sure is part of any diameter (call this r), how many possible diameters are there?

Any diameter must go through two of the edges adjacent to r; this implies that r is not a leaf, which should be obvious. So for each vertex adjacent to r, we consider each of the subtrees rooted at the vertex, specifically a) how deep the subtree is, and b) how many leaves are in the subtree, at the lowest depth.

We then consider the two deepest subtrees. A path from one leaf in one of the subtrees to one leaf in the other subtree will be a diameter.

If the two depths (call these d₁ and d₂) are equal, then there may be more subtrees that can be part of a diameter; namely, any subtree with depth equal to d₁. Then we create an array containing the number of leaves in every subtree that satisfies this constraint. Now we can sum together, at every array element, the product of the element and the sum of all the elements to the right. This gives the total number of diameters. (It's probably a good exercise to see why this works.)

If d₁ ≠ d₂, then there may be more subtrees that can be part of a diameter; namely, any subtree with depth equal to d₂. We then sum together the number of leaves of subtrees satisfying this constraint, and multiply this with the number of leaves of the subtree with depth d₁ to get the total number of diameters. (Again, figuring out why this works is an exercise left to the reader. Also it's 1 AM and I'm sleepy.)

The final thing to do is to relate this to the original diameter problem. It's quite easy to show that the middle vertex in the diameter that was found with the two BFS runs must be part of any diameter, if the diameter has an odd number of vertices in it. Then we can run what I just described, with the middle vertex as the root. If the diameter length is even, then the thing guaranteed to be in any diameter is an edge, rather than a vertex, but this is less annoying than you'd think: we can simply replace the edge with a new vertex, and connect it to the two vertices on either end of the edge we just removed. Now this vertex has to be on any diameter, and we can proceed as normal.

¹See the handshaking lemma.

²Testing if every number in the range [1,X^1/2] is divisible by X is sufficient, as anything larger will be double-counting.