Practice 2016-09-10: Solutions for GCPC 2012

Post date: Sep 16, 2016 4:32:04 AM

This week's contest is mostly "read problem carefully and implement". Problem D was quite unusual, problems CFGK were very standard algorithms, and relatively little insight required for problems ABEHJI.

Thanks to Andy and Angus for alternate (easier) solutions.

Problem A

Problem Statement

Simulate battleships game and determine who wins.

Solution

The problem statement is very confusing and long, so read it carefully. In particular, key points are:

1. Despite the "you don't know who shot what" part, the first player did make the first shot

2. The player continues to make shots until he misses or he sinks all enemy ship

3. If player 1 sinks all of player 2's ship, then player 2 gets one last turn immediately after

4. You stop simulating when the game ends (i.e. when one guy has no ships, but take #3 into account)

Complexity

Time complexity: O(n)

Problem B

Problem Statement

Execute a brainfuck program. If it does not terminate in 50mil steps, then assume it's in an infinite loop, and that this loop has been executed completely once, and figure out what loop it is.

Solution

The brainfuck language is easy to write an interpreter for, just follow the instructions and make sure you create a map of [ to ] and vice versa for the code so that each simulation step is O(1). The hard part is determining what loop is infinite. What I did was to simulate the 50mil steps, create the list of (nested) loops it's currently in. Then, we simulate another 50mil steps, each time a loop is exited we remove it from the list, and then output the inner most loop that is not removed yet.

Complexity

Time complexity: around 100mil operations

Alternate Solution

According Angus, you only need to simulate 50mil steps, keeping track of these states:

1) has not been processed

2) has been processed

3) corresponding ] has been processed and the loop exited - there are no transitions out of this state

After hitting 50mil steps, you just need to find the one [ that's in state 2, because it's one end of the only loop that hasn't exited at some point.

Problem C

Problem Statement

Solve for Y: -KX + CY = 1 and if there's a solution in [1, 1 billion] output it.

Solution

Just use canon_egcd (Extended Euclidean Algorithm) from code archive.

Complexity

Time complexity: O(log n)

Problem D

Problem Statement

Determine if 2 DFAs accept the same strings. The DFAs have 1 starting state (= 0th state) and 1 accepting state (= (n-1)th state), and have <= 250 states, <= 250 letters in the alphabet.

DFS Solution by Andy Shih

Treating all transfer stations as nodes and assembly stations as edges:

1. Store graph original factory as a vector of nodes, each with a vector of edges

2. Store graph of foreign factory as vector of nodes, each with a map of edges (key is operation, value is destination). Receiving operation for each node is unique.

3. Remove all assembly stations that cannot reach final node with DFS (or BFS)

4. DFS through the original factory and foreign factory at the same time starting at (0,0) (lets denote this as (A,B)). At each node of A check all remaining edges. For each edge, let dest be D and operation be Op. Check if Op exists in B's map of edges. If so, perform DFS on (D, B[Op]). If not, then return false immediately. Furthermore, if D is the final node, B[Op] MUST be the final node or else we also return false. If all DFS returns true then foreign factory can replace original factory.

5. Swap original factory and foreign factory and re-run steps 1-4.

Complexity

Time complexity: seems like O(N^2)

Alternate Solution

My solution was considerably more complex but probably handles more cases:

1. Reduce each DFA to its minimal form, which is guaranteed to be unique

1a. BFS to erase nodes not on path from start to accept

1b. Initialize a partition of nodes: {{accept}, {other states}}

1c. Until no more changes, for each set in partition, partition the set so that nodes in the same set have equivalent edges (i.e. edges of the same letter that goes to states in the same set in the partition)

2. Compare if the 2 minimal DFAs are exactly the same by performing simultaneous BFS starting from the starting node, and go through the edges in the same order as the alphabet. Keep track of a mapping between the two DFAs, update it on visit, and return false if at any point two nodes have different edges going out.

Time complexity: O(N^3)

Problem E

Problem Statement

Given two sets of words, A and B, and two lists of equal size <= 60, LA and LB, of subsets of A and B, for every (a, b), a in A, b in B, output (a, b) if a and b appear in subsets of the same indices in LA and LB.

Solution

Keep a map of word => bitmask of elements of the list it's in, then brute force every pair to see if the bitmasks are equal.

Complexity

Time complexity: O((NM)^2)

Problem F

Problem Statement

Perform knapsack where the value of using the i-th item for the k-th time is ai - (k-1)^2 * bi. There are k = 1000 items and you have budget of up to n = 25000.

Solution

The thing to notice is that if bi = 0, then cost of all uses of the item are the same, and if bi > 0 then you never use each item more than cuberoot(n) = 30 times. If we optimize our knapsack based on those observations, we will run in time.

Define V[i][k] = sum_{j <= k} [ ai - (j-1)^2 * bi ] then

dp[n][i] =

if bi > 0: min(dp[n-1][i], dp[n-j*C[i]][i-1] + V[i][j])

if bi = 0: min(dp[n-1][i], dp[n-C[i]][i] + V[i][1])

Complexity

Time complexity: O(k * n^(4/3))

Problem G

Problem Statement

The problem statement is complicated and long, but basically boils down to intersecting a parabola with a curve made by connecting parabolas and horizontal/vertical lines, and calculate a bunch of things.

Solution

You can binary search for the intersection. To calculate velocity you use v = sqrt(2gh). To calculate angle, you first get direction vectors using derivative, then do dot product: theta = acos(a dot b / |a| / |b|)

Complexity

Time complexity: O(log n)

Problem H

Problem Statement

Given a list of suffixes of the same string, with their starting position in the original string, and each suffix has possibly one contiguous substring replaced by a '*', reconstruct the original string.

Solution

The '*' divides the suffix into 2 parts whose positions are known. Just initialize a string, for each suffix copy the characters except the '*' into the correct positions, and check for conflicts / positions that were never writen to.

Complexity

Time complexity: O(n + input)

Problem I

Problem Statement

Sort strings by distance to some original string. Distance defined by sum of Manhattan distance of corresponding letters on qwerty keyboard.

Solution

Simply follow the instructions, no tricks.

Complexity

Time complexity: O(LS)

Problem J

Problem Statement

Given convex polygon, find the scale such that if we shrink it by that much then the shape that is distance r outwards will have same perimeter as the original polygon.

Solution

The minimal perimeter is 2*pi*r, so make sure you check if the original polygon already has smaller perimeter, in which case it's impossible.

Imagine walking along the polygon with a stick of length r pointing outwards. We will sweep out the length of each side, and then sweep out an arc of some angle at each corner. Well, if we go all the way around, then those arcs add up to a full circle because we've rotated our stick the full way. Hence, if original perimeter is P, scale is S, then the resulting perimeter is P*S+2*pi*R. Hence S = (P - 2*pi*R)/P. Easy!

Complexity

Time complexity: O(n)

Problem K

Problem Statement

Given graph and starting node. Each node has some number of >= 0 items. Total number of items I <= 8. Each edge has a cost. Find the maximum number of items you can collect with a circuit from starting node with cost <= C (given).

Solution

The initial graph is big, so use Dijkstras to reduce it to a graph with I+1 nodes: starting node and all nodes with >= 1 items. The edges are the cost of shortest path between those nodes. Then, perform a Traveling salesman dp: dp[S][i] = the minimum cost to visit nodes in S and end at node i. Finally, for all S such that dp[S][0] <= C, compute the number of items collected when visiting nodes in S, and take the maximum.

Complexity

Time complexity: O(I^2 * 2^I + (V+E) log E)