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)