Transcript meeting slides - Lynbrook Computer Science

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?