Practice 2016-08-07: Solutions for ECNA 2015

Post date: Sep 5, 2016 10:24:57 PM

My code: https://www.dropbox.com/sh/xy51kgvcyijg0xf/AABKI2ZJvyROt5RMmqtbzFxIa?dl=0

Below I will describe solutions of the entire problem set, by Andrew and myself.

Problem A - Being Solarly Systematic

Problem Summary

You are given a bunch of planets (points in 3D) with integer coordinates and velocities, lying inside a rectangular box [0, nx) x [0, ny) x [0, nz). When the planet hits the boundary, it appears on the other side (i.e. x coord is mod nx, etc). Whenever planets collide (they can only collide on integer time steps) you add the mass and average the velocity. You want to output the position and velocity of the planets at the time of the last collision.

Solution

Notice that there are 100 planets so at most 100 collisions as each collision deletes one planet. Thus, naive simulation will work: at every iteration, calculate collisions of all pairs of planets and process the ones colliding the earliest.

The hard part is of course, computing collisions. WLOG we try collision of 2 planets. Notice that the constraints are x1 + vx1*t = x2 + vx2*t (mod nx), and similarly for y and z.

Thus we simply have to find the integer solution for the following system that minimizes t such that t >= 0:

nx * k1 + (vx1 - vx2)t = x2-x1

ny * k2 + (vy1 - vy2)t = y2-y1

nz * k3 + (vz1 - vz2)t = z2-z1

where the variables are k1, k2, k3, t.

Each of the 3 equations above is a linear Diphantine Equation. We can solve each of them separately using Extended GCD. The canon_egcd() function in the code archive will give the minimum non-negative solution for t.

Each equation gives a solution space* for t, of the form t = a + bx where a, b are constants and x is any integer. We can rewrite this solution space as t == a (mod b).

After solving the 3 equations separately, we see that t must satisfy 3 congruences simultaneously: t == a (mod b) == c (mod d) == e (mod f). Finding the solution for t in this case simply requires application of Chinese Remainder Theorem. We can recursively use the Chinese Remainder Theorem solver in code archive as follows

chin_rem(a, b, c, d, A, B);

chin_rem(A, B, e, f, A2, B2);

A2 will be our solution.

Remember to always check if the equations are feasible!

Pitfalls:

1. Box size can be 1 (i.e. coordinate always = 0)

2. There can be more than 2 planets colliding at the same place

3. There can be 2 or more sets of planets colliding at different locations at the same time.

Complexity

Time complexity: O(log something)

Notes

* This is because if ax + by = c then for any integer k

a(x - k * b/gcd(a, b)) + b(y + k * a/gcd(a, b)) = c

Problem B - Delete This!

Problem Summary

You have black and white points in a 2D box. You want to move a minimum number of points such that the rectangle containing all black points don't contain any white points. You can move some white points slightly outside the 2D box but all black points have to be inside.

Solution

The key insight is to decide on the rectangle we draw and then move the points in and out as necessary. WLOG we can assume that either the rectangle has black points that were never moved on all 4 sides, or that no black points were inside the box so we have to move all black points.

We brute force the left and right side of the rectangle and then figure out how to pick the top and bottom side. This involves selecting a range of y value that minimizes # white - # black inside the rectangle. This is because suppose there are n black points, then the total number of moves is # white-inside + (n - # black-inside).

We can create a sorted list of y coordinates with points between the left/right side we chose and for each y coordinate we compute the # whites - # blacks. We then find the minimum subarray sum.

To find the minimum subarray sum we basically compute min_i(prefixSum(i) - max_{j<i} prefixSum(j)). This can be done by scanning the array and keeping track of the current prefix sum and the maximum prefix sum seen so far.

Complexity

Time complexity: O(n^3)

Problem C - KenKen You Do It?

Problem Summary

You have up to 10 grid cells that are connected (two cells are connected if they share a side). Given integer 2<= n <= 9 you want to find the number of ways to fill in the grid cells with integers [1, n] such that they add/subtract/multiply/divide (the operation is given) to a certain number, with every row and every column containing no duplicates.

Solution

Given the small input size, backtracking brute force search is an ideal choice. However, the worst case may involve going through lots of dead ends as a stair-case shaped grid could involve 8^9 combinations, most of them wrong, so we need to stop our brute force early from going to too many dead ends.

The following optimizations are sufficient to pass:

1. Before filling the cell with a number, check that the row and column does not have that number already. This can be done in O(1) by keeping a seen array and set/unsetting it as we go in the recursion.

2. Before filling the cell with a number, we also do a simple check to see if we have a chance at achieving the remaining sum/product (the lower bound is filling with all 1's, and upper bound is filling with all n's).

Complexity

Time complexity: ??????

Problem D - Rings

Problem Summary

Given grid with marked and unmarked cells, for every marked cell find the shortest distance to an unmarked cell.

Solution

You can run a BFS with adding all unmarked cells with distance 0 to the queue initially. You can also run dp from top left to bottom right, then bottom right to top left.

Complexity

Time complexity: O(mn)

Problem E - Squawk Virus

Problem Summary

You are given graph. Initially one node has 1 virus. At each time step, every node will receive a copy of every virus in its neighbors.

Solution

Simply simulate this as the input size is very small: count[v][t+1] = sum count[u][t] where u neighbor of v.

If there were a lot of time steps but graph is small, we could have also computed M^t (1 0 ... 0), where M is the adjacency matrix, as that matrix is exactly the transition matrix of this process.

Complexity

Time complexity: O((|V| + |E|) * t)

Problem F - Transportation Delegation

Problem Summary

There are a bunch of states. Each state has either raw material, factory, or none. Each raw material site produces 1 unit, and each factory consumes 1 unit. There are a bunch of transportation companies. Each company can move 1 unit between states in a set of specified states. You want to move as much raw materials to factories as possible.

Solution

F is for flow!

Connect source to raw material states with capacity 1. Connect factory states to sink with capacity 1. For each transportation company, make vertex with capacity 1 and connect bidirectional edges to each state the company works in.

That's it!

Complexity

Time complexity: uhhhh don't ask, because flow is magical

Problem G - Tray Bien

Problem Summary

You want to place 1x1, 1x2, 2x1 rectangles to fill a 3xm grid with some holes.

Solution

This is standard dp, but kind of annoying implementation.

dp[i][j] = number of ways to fill the first i columns such that the i+1 th column has bitmask j cells filled with 1x2 rectangles.

Compute the transitions carefully using a backtracking brute force, be sure to take care of dead cells as well.

Complexity

Time complexity: O(m)

Problem H - Trick Shot

Problem Summary

Uh please see the picture in the problem. You want to place Q ball and shoot it such that it hits B1, which then hits B3 which goes to top right hole, and then Q hits B2 which goes into top left hole. You want to solve this with the following simplified rules and physics:

1. there are no walls (so no bouncing off walls)

2. when moving ball collides stationary ball, the moving ball follows angle of incidence = angle of reflection, and the stationary ball moves perpendicular to plane of collision

3. ball hits hole iff center of ball hits center of hole

Solution

The solution is to "back trace" the balls to start. In other words, you do the following:

1. Find where B1 has to be hit B3 for B3 to go to top-right corner (this involves drawing a line from top right corner to B3, and then extending it by 2*radius)

2. Find where Q has to be to hit B1 to get B1 to hit B3 correctly (call this position C1)

3. Find where Q has to be to hit B2 to get B2 to go into top left corner (call this position C2)

4. Find initial position of Q by "reflecting" the path of C2-C1 according to the line C1-B1.

Pitfalls:

1. Check if any of the path intersect any stationary balls.

2. It's possible that B1 = C1, and C1 = C2, make sure you don't divide by zero, and handle them specially.

3. The Q ball has to start completely inside the rectangle, not just the center inside.

4. Use epsilons.

Complexity

Time complexity: O(1)

Problem I - What's on the Grille?

Solution

Uh follow instructions in the problem. There are a few ways of rotating a matrix by 90 degrees - something like (r, c) => (c, n-1-r) would probably work. Also note that no two rotations can share same hole locations otherwise you output impossible.

Complexity

Time complexity: O(n^2)