Report

USACO (())()(()) ((())()(())()(())) (())()(()) USACO November Contest • The first USACO competition was last week. • Lynbrook had a very strong performance as a whole o Congratulations to Andy Wang (1000), Raphael Chang (933), and Edward Lee (867) for promoting to Silver o Kudos to Johnny Ho (875) for scoring highest out of the US seniors on Gold o Congratz to Steven Hao (938) for proving that he can O(n^2) bash problems o Good job to the random 5th grader who got a perfect on Silver • Full results and problems are at usaco.org Bronze Contest: "Typo" • Input: an arbitrary string of parentheses of length n, n < 100,000 • Output: the number of ways you can flip exactly one of the parentheses to make the string balanced (not necessarily positive) • Example: (((()) o answer = 3 o change either the 2nd, 3rd, or 4th parens • Solution: o Prefix sums o The stuff we covered on the Halloween PotW Bronze Contest: "Typo" • Figure out which type of parentheses is in excess (kind of like a limiting reaction) o (((()): 4 ('s, 2 )'s o You should convert one of the ('s • Orient it so that there are too many )'s instead of ('s o Reversing/flipping the string does not change answer o (((()) turns into (()))) o Now you should convert one of the )'s • Convert parentheses into numbers o (()))) turns into {+1, +1, -1, -1, -1, -1} • Take prefix sums o {1, 2, 1, 0, -1, -2} • A ) can be converted if and only if it lands at or before the first negative prefix sum Silver/Gold Contest: "Balanced Cow Breeds" • Input: an arbitrary string of parentheses of length n, n < 1000 • Output: the number of ways you can color each parenthesis such that each color forms its own balanced string of parentheses • Example: (()) o o o o (()) (()) (()) (()) • Solution: o Dynamic programming o The stuff we were just about to cover :( Silver/Gold Contest: "Balanced Cow Breeds" • Use recursion. • int recurse(int index, int nestA, int nestB) o If nextA or nestB become negative, quit immediately o If index reaches the end of the string, return 1 if and only if nestA == 0 and nestB == 0 o Otherwise, you can color index in 2 ways. • You can change this to a 2D DP state o nestB can be calculated from index and nestA o This makes your algorithm use O(N^2) memory • The algorithm visits O(N^2) states, each in constant time, for overall O(N^2) "Concurrently Balanced Strings" • K strings of parentheses, each of length N. • Count the number of ranges (a, b) satisfying: o For any of the K strings, the substring from a to b is a balanced string of parentheses. • K <= 10, N <= 50 000 • Example o K = 3, N = 14, o Answer: 3 s_1 = )()((())))(()) s_2 = ()(()()()((()) s_3 = )))(()()))(()) • N is large, need faster than quadratic. o N is only 50 000 • A good N^2 may pass 60 - 90% of the test cases • Similar for Gold Problem 3. "Concurrently Balanced Strings" • Consider a single string. (Let K = 1) • Compute for each prefix of the string its "sum" o Sum of a string is # left parens - # right parens. o sums[i] is the score of the prefix ending at index i. • We can check if a substring from A to B is balanced. o Sum of this substring is sums[B] - sums[A] • This must be 0, so sums[A] == sums[B] • For all A < C < B, sums[C] >= sums[A] o Iterate over B • Count the number of possible A. o Also keep track of the negative condition. • Use a map for O(n log n) • Store K sums instead of 1 for original problem • Steven's Code (Expertly uses map<int, int>) o http://pastebin.com/rLSJwN9Y In summary • Getting partial credit by O(n^2) bashing O(nlogn) problems is a highly effective strategy • Silver/bronze problems are all fairly standard o o o o Dynamic programming Graph theory (Dijkstra’s, BFS, DFS) Greedy Sorting • Silver/bronze contestants have to be very careful to pass o Test on both small and large test cases • Now just pray that we don’t have any more problems about parentheses PotW • Last week's PotW is extended o The one about Karen's sleeping habits o The problem remains largely unsolved • Hints for Subtask 3, where N <= 100000 o Try all possible rooms as centers o Try the rooms in a specific order • depth-first search o Avoid recomputing the sum of distances to other rooms o Imagine moving the center from one room to an adjacent room o What needs to be precomputed?