2016-09-14 Practice: Solutions for GNYR 2012

Post date: Sep 16, 2016 5:45:52 AM

Greater New York Regionals is usually considered to have easier problems compared to other regions. This set in particular is math heavy but the math used is fairly elementary and code is quite short! If you are new to ACM, here is the chance to practice many of the standard techniques.

Problem F was quite nice and thanks to David and Paul for solutions.

Problem A

Problem Summary

Output sum_{i=1..n} i, 2i-1, 2i

Solution

You can precompute the answer by brute force or use formula:

sum i = n(n+1)/2

sum 2i-1 = n^2

sum 2i = n(n+1)

Complexity

Time complexity: O(1)

Problem B

Problem Summary

Compute the number of sequences of 2's and 1's such that

1. number of 2's in odd positions equal number of 2's in even position

2. same for 1's

3. sum of all numbers in odd positions = n (given)

4. there are at least as many 2's as 1's

Solution

The main idea behind solution is to divide the problem in half and consider only e.g. the subsequence in the odd positions.

We can compute the answer for odd positions with a dp, then square it (sort of).

Let dp[i][j] = the number of sequences that sum to i with j 2's then

dp[i][j] = dp[i-1][j] + dp[i-2][j-1]

The idea is that we can count sequences that end in a 2 separately from sequences that end in a 1.

The total answer for a given n is then

sum_j dp[n/2][j]^2 where j >= n/2-2j and j <= n/2

This is because once we have a set of sequences satisfying rule 3 and 4, we can choose any pair and interleave them to form the original sequence.

There is a closed formula (namely, dp[i][j] = (i+j)!/i!/j!) but it requires big integer to compute efficiently.

Complexity

Time complexity: O(n^2)

Problem C

Problem Summary

Compute the n-th fibonacci number mod 10^9, n is up to 2^48.

Solution

We can represent the transition for fibonacci number by matrix multiplication:

[ 0 1 ] [ t_{n-2} ] = [ t_{n-1} ]

[ 1 1 ] [ t_{n-1} ] = [ t_n ]

Let the left matrix be M, then we simply compute M^(n-2) * [1, 1]. To compute a large power of a matrix in log time, we use the "square and multiply" method, where we repeatedly square M, and multiply it to our vector when the current exponent corresponds to a set bit in (n-2).

Complexity

Time complexity: O(log n)

Problem D

Problem Summary

Given n, find the sum of the Euler totient function (phi(n) = # numbers < n that are coprime with n) for 1, ..., n

Solution

With the generous time limit we can simply GCD every pair of number <= 10000 and it will run around less than 5 seconds.

To compute the Euler totient function efficiently, we use the Sieve of Erasthocene to find prime numbers and find a single prime factor for composite numbers. Then we can take advantage of phi(mn) = phi(m)phi(n) if m, n are coprime, and also for prime powers phi(p^k) = p^{k-1}(p-1).

Complexity

Time complexity: O(n^2 log n) or O(n log log n + n log n)

Problem E

Problem Summary

You have a tree of fractions where the root is 1/1, and if you move to left child you add numerator to denominator (i.e. p/q => p/(p+q)), and if you move to right child you add denominator to numerator (i.e. p/q => (p+q)/q). Given a fraction p/q find its BFS index in the tree.

Solution

Notice that if we move left, denominator is bigger, and if we move right, numerator is bigger. Thus, whether p > q or p < q gives us whether we are left or right child of parent. We can trace back the path to the root this way, and with a path, we can compute the index. Basically you just need to start at idx = 1, and move to 2*idx for left child, and 2*idx+1 for right child. This is fast enough to pass.

Now we observe that repeatedly subtracting the smaller number is equivalent to the Euclidean algorithm. A long sequence of p -= q is just p % q. We can compress sequences of the same move by computing number of layers = p/q and use that to move down the tree quickly. This gives log time.

Complexity

Time complexity: O(p+q) or O(log p + log q)

Problem F

Problem Summary

Given 2 directed graphs (red and green) out-degree on the same n <= 500 nodes, each graph has exactly n directed edges. Placing a robot at each node initially, and armed with green button (moves all along the outgoing green edge) and red button, is it possible to merge all?

Solution (by David and Paul)

The key observation is that this is possible iff we can merge every pair independently. Clearly if we can merge all of them, we can merge an arbitrary pair. However, if we cannot merge all, then we must always end up with >= 2 that cannot be merged, which means we cannot merge every pair.

Hence, the solution is just to BFS / DFS on all pairs of node, starting from pairs of the same node.

Complexity

Time complexity: O(n^2)

Problem G

Problem Summary

Compute number of ways to write n as a sum of integers (order matters) such that none of them are of the form m + ki, with m and k given and i >= 0.

Solution

Given m and k, we simply compute this N^2 dp: dp[n] = 1 + sum_i dp[n-j] where j are not of form m+kj. If n itself is of form m+km, then we have dp[n] = sum_i dp[n-j].

The idea behind the dp is to try all possible ways of choosing the last number in the sum, and then recurse on a smaller subproblem.

Complexity

Time complexity: O(n^2)

Problem H

Problem Summary

Find a point in a triangle that makes the same angle to all 3 vertices.

Solution

Binary search on the angle, for each angle find the point that makes the angle to two of the vertices, and compute the obtained angle for the 3rd. As the angle for the first 2 vertices increase, angle for the 3rd vertex decreases, so they eventually meet and this crossing point is found by binary search.

Complexity

Time complexity: O(log eps)

Problem I

Problem Summary

Follow instructions: given a number, repeated the RATS operation (at itself with its reverse, and then sort the digits and remove leading zeros) some number of times while detecting if it loops or if it fits specific patterns (regex 1233+4444 or 5566+7777).

Solution

Follow instructions and implement. The only gotcha is that the number can be really big so use big integer or implement your own addition. Converting the number to string is useful for sorting and reversing.

Complexity

Time complexity: O(m)