Practice 2016-08-13: Solutions for Asia Tokyo 2014

Post date: Sep 5, 2016 10:54:05 PM

The problem set for this practice had a wide range of difficulty.

I solved problems A-H and implemented solutions found online for I and J.

I could not decipher solutions I found for problem K unfortunately

My code: https://www.dropbox.com/sh/q3ydw30o8z6yzoj/AACZGISc2fzYvcmf0ZfcBRJAa?dl=0

My solutions are as below.

Problem A - Bit String Reordering

Problem Summary

You want to find the minimum number of moves to get from bitstring A to bitstring B (or ~B). Each move is swapping adjacent bits.

Solution

This problem can be solved by greedy simulation: from left to right, for each bit that is wrong, find the next bit that is opposite and swap it left to the current position.

Complexity

Time complexity: O(n^2)

Problem B - Miscalculation

Problem Summary

Given an arithmetic expression with + and *, compute the answer two different ways: left-to-right and multiplication-before-addition.

Solution

Follow the instructions and implement. For the * before + case, you can do 2 passes - first scan left to right and greedily do consecutive multiplications, pushing the result into a vector, then do additions later.

Complexity

Time complexity: O(n)

Problem C - Shopping

Problem Summary

You have a bunch of stores on a line at distances 1, 2, 3, ... n. You start at 0 and want to end at n+1, and you want to visit every store. You are also given a list of restrictions that you must visit store x_i before y_i where x_i > y_i. Find the minimum distance you have to travel.

Solution

The key observation is that if [y1, x1] overlaps [y2, x2] then you want to do one "backward" trip max(x1, x2) => min(y1, y2) to satisfy both restrictions, and if they don't overlap you want to do two separate backward trips.

More specifically, each restriction forces your path to include the interval [y_i, x_i] in the "backward" parts, so the optimal solution is to union all of these intervals together and for each resulting interval [a, b] you travel to b, then to a, then to b again. This can be done with an interval sweep.

For those who have never done it before, we do interval sweep to union all intervals like this: get a sorted list of events which are left and right end points of the intervals, and as you sweep from left to right, you +1 to a counter if you hit a "left end point event" and -1 if you hit a "right end point event". If you go from 0 to +1 you record the point as 'start', and when you go from +1 to 0 you record this as 'end' and push [start, end] as a new combined interval.

Complexity

Time complexity: O(n)

Problem D - Space Golf

Problem Summary

See picture in problem. You shoot a ball and you want to bounce it at most a number of times (perfectly) and then land on a target. There are some vertical obstacles along the way that your ball has to clear. The ball follows regular rules of physics with elastic collisions. You want to find the minimum initial velocity.

Solution

We brute force over the number of bounces. Given the number of bounces, we can compute how far each bounce has to go. Then, we can binary search for the minimum initial velocity that will clear all obstacles, as higher initial velocity means we can aim higher above 45 degree. The binary search range is [velocity at 45 degrees, infinity) because for any velocity the farthest you go is at 45 degrees so for given distance the minimum velocity is at 45 degrees.

The problem helpfully gives equations for us:

2 * vx * vy = L

vx^2 + vy^2 = V^2

We solve this to get:

(vx + vy)^2 = V^2 + L

vy = sqrt(V^2 + L) - vx

2 * vx * vy = 2 * vx * sqrt(V^2 + L) - 2 * vx^2 = L

vx^2 - sqrt(V^2 + L) * vx + L/2 = 0

vx = (sqrt(V^2 + L) +/- sqrt(V^2 - L))/2

vy = (sqrt(V^2 + L) -/+ sqrt(V^2 - L))/2 (by symmetry)

For vx we choose - and for vy we choose + because we want to shoot higher.

Complexity

Time complexity: O(b^2 n log eps)

Problem E - Automotive Navigation

Problem Summary

Your car starts at (0, 0) and moves along a network of orthogonal streets. At each time step you have the distance traveled after previous time step, and the current direction (can be before or after turning if the car is at an intersection). Find all possible locations of the car now.

Solution

The solution is simulation. Simulate the car moving one distance step at a time. When it enters an intersection, spawn multiple cars representing the multiple possibilities from there. Make sure to delete invalid possibilities: neither entering nor exiting at the correct direction at each time step. Also make sure to check each movement carefully: each street is an interval, we check the interval [start, end] is completely contained in the street we are on.

Implementation tricks: we can keep a map of x => set of vertical streets on this x coordinate, and similarly for y, and use lower_bound() to look up what street we are on based on coordinates.

Complexity

Time complexity: O(n^2 * t * d * log n)

Problem F - There is No Alternative

Problem Summary

You want to find sum of the cost of edges that are part of all minimum spanning trees.

Solution

The idea is to think about this using Kruskal's algorithm, where we sort edges from small to large and greedily choose edges that connect disjoint components. Consider edges with minimum weight. We know that some of them must be part of the MST because otherwise we can add any of them to a purported MST, forming a cycle, delete a larger edge, and get a spanning tree with smaller weight.

Furthermore, we can use the same argument to show that any MST must contain some spanning forest of the subgraph with minimum weight edges. What edges are shared by all spanning forests? Bridges (i.e. edges that if removed, will cut a connected component into multiple ones).

Algorithm: maintain a union-find data structure; for each possible edge weight from small to large, add edges of this weight that connect different components, perform bridge detection and add all bridges to the solution, then perform union on all the edges of this weight.

Complexity

Time complexity: O(m log m)

Alternate Solution

Because the input size is so small, this alternate easy algorithm also works: find MST, for each edge in MST, remove it and re-run MST to see if MST weight has increased; an edge is in all MSTs if and only if it is in some MST and removing it causes weight of MST to increase. This is O(mn log m).

Notes

The code archive's bridge detection thing has a slow init() function costing O(n) each time, so my implementation is not optimal.

Problem G - Flipping Parentheses

Problem Summary

You are given an initial string of balanced parentheses. You are given a bunch of operations. Each operation involves flipping one of the parentheses, and you have to then find the left most parenthesis to flip to restore balancedness and perform both flips on the string (and output which one you flipped to restore balancedness).

Solution

Consider the depth function, where you scan from left to right, +1 if you get a '(' and -1 if you get a ')'. A string is balanced if and only if the depth function starts and ends at 0 and is non-negative.

If we flip from '(' to ')' then we need to find a ')' to flip to '('. In this case any ')' at or before our first flip will do because ')' => '(' *increases* the depth function and will thus restore balance. Thus we use the left most ')'.

If we flip from ')' to '(' then we need to find a '(' to flip to ')'. Flipping '(' to ')' decreases depth function by 2 onwards. Thus our goal is to find the left most '(' such that the depth function *after* is >= 2. One idea is to use a range tree to represent the depth function, where we do range increment/decrement of [i, end] for a ( or ) at position i, and do range query to find the minimum value of depth function in [proposed next flip, queried flip]. Because the min function is monotonic, we can use binary search to find the left most possible position.

Complexity

Time complexity: O(q log^2 n)

Better Solution

In fact we didn't need the binary search; we can modify our range tree to output the solution directly. Since each node stores the minimum of its responsible interval, we simply move to right node if minimum < 2, and left if >= 2, and return the index of leaf node. This reduces to O(q log n).

Problem H - Cornering at Poles

Problem Summary

You have a circle, you want to find shortest path from A to B such that the circle avoids point obstacles.

Solution

This is equivalent to moving a point with circle obstacles. To solve this we construct a "visibility graph" and run Dijkstras on it.

Construction of visibility graph with circle obstacles

Essentially we find all the important points as vertices and draw edges between them. The observation is that you only want to move to the "extremes" of an obstacle from your point of view, hence it's called a visibility graph. We only have circles so we care about paths between and inside one circle. On one circle, the path is around circumference. Between circles, the path must be tangent to both circles (there are 4 of them if the circles do not intersect, 2 if they do).

Sounds hard to implement? Copy black magic from code archive and you are done.

Complexity

Time complexity: O(n^3 log n) because we have graph with O(n^2) vertices and O(n^3) edges (around 4n vertices and 4n edges per circle obstacle) and we run dijkstra.

Problem I - Sweet War

Problem Summary

Alice and Bob are playing a game. There's a stack of chocolate, each gives energy and value. Alice and Bob start with energy A and B and they want to maximize the value they got from chocolate. They play optimally. Any player can "pass" a turn by spending one energy, or eat the chocolate on top of the stack. Find the total value each player gets.

Solution

I will translate this solution:

http://natsugiri.hatenablog.com/entry/2014/10/25/224354

tl;dr: dp[v][i] = minimum energy difference required for Alice to get value v in the end with i chocolates left on the stack.

Naively we could do dp[a][b][i] = value Alice gets when there are i chocolates left on the stack and the energy of Alice and Bob are a and b. However, we notice that the energy values can be huuuge so we have to somehow get around this.

First we notice that it is never optimal for both players to pass consecutively, so the optimal strategy can involve passing only if the current player has higher energy, and in which case the opponent will be forced to eat. Thus, the thing that matters is the difference in energy. Notice that we don't need to keep track of the absolute amount of energy because we only pass if we have more which means we have at least one energy.

The above gives dp[a-b][i] = value Alice gets when i chocolates left on stack and difference in energy is a-b.

We can see that when the energy difference is higher, Alice has more power to "force" Bob to eat bad ones, so the value Alice can get increases monotonically with energy difference. We notice that the values are small, so we can flip the dp and try: dp[v][i] = minimum energy difference required for Alice to gain value v in the end when there are i chocolates left on the stack. The recursion involves a case with dp[v][i-1] and dp[v - values[i]][i-1], depending on whether Alice eats the chocolate on top of the stack or not.

Complexity

Time complexity: O(N^2)

Problem J - Exhibition

Problem Summary

Given set of n <= 50 triplets (xi, yi, zi) and 1 <= k <= n, you want to change the first triplet (x1, y1, z1) such that it is part of some subset S of size k that minimizes (sum_S xi)(sum_S yi)(sum_S zi) out of all possible subsets of size k. The cost of changing (x1, y1, z1) to ((1-a)x1, (1-b)y1, (1-c)z1) is aA + bB + cC where ABC are constants and 0 <= (a, b, c) <= 1. You output the minimum cost for changing (x1, y1, z1) satisfy the previously described criteria.

Solution

I will translate the second solution from here:

http://natsugiri.hatenablog.com/entry/2014/10/25/225156

First let's use DP to figure out what's the optimal product before we change anything. The key to notice is that only the sums of xi, yi, and zi matter - we don't actually need to iterate through all subsets of size k. Fortunately their sums are all <= 5000 so we can try some sort of subset-sum like strategy. Let dp[i][j][X] = all pairs (sum y, sum z) of possible subsets of size j using up to the ith triplet such that the sum of x is X.

Now because we are looking for minimum, we don't actually need to store all (sum y, sum z) - if y <= y' and z <= z' then xyz <= xy'z' so we can discard (y', z'). Hence our dp is actually dp[i][j][X] = pareto front of (sum y, sum z) possible subsets of size j using up to i-th triplet where sum x = X. We can do insertion to pareto front in amortized O(log n) time using a set. The dp recursion for dp[i][j][X] involves dp[i-1][j][X] and dp[i-1][j-1][X - x[i]] (i.e. whether to use the i-th triplet or not).

To find the initial optimal product, we run this dp, and then iterate through all x and for all (y, z) in dp[n][k][x] calculate xyz and take the minimum. Call this number M.

From the dp you we can get dp[n-1][k-1][X], which is the possible sums (X', Y', Z') for subsets of size k-1 using possibly everything except our special one (x1, y1, z1) (preprocessing step: swap first triplet with last triplet when reading in input). For each of these possibilities, we try to minimize aA + bB + cC while making (X' + (1-a)x1)(Y' + (1-b)y1)(Z' + (1-c)z1) = M and keeping (a, b, c) in the unit cube.

In other words, we solve the following constrained optimization problem:

min aA + bB + cC

s.t.

(a, b, c) in [0, 1]^3

(X - ax)(Y - by)(Z - cz) = M

I used a weird combination of ternary search and Lagrange multipliers that somehow worked. However there is a much easier solution. Notice that our objective function is linear and our equality constraint forms an almost plane-like slice through the unit cube. This leads to the intuitive guess that optimal solutions lie on the extrema of the cube, i.e. on the edges, so we try all combinations of setting two of (a, b, c) to 0 or 1 and solve for the remaining one and we are done.

Complexity

Time complexity: O(knm^2 log m) where m = 5000 = maximum sum of any coordinate, because the 2D pareto front is at most size m. This is about 375 billion but in practice you won't get so unlucky it seems.

Problem K - ∞ Jumps

Unfortunately I did not solve this problem and could not understand any of the solutions I found online.