Wednesday, May 31, 2006 Match summary An unusually tricky Division 2 Medium/Division 1 Easy kept scores generally low. At the end of the coding phase, rem led by 60 points over Petr and ploh, who were neck and neck. However, three successful challenges for ploh and two for Petr reversed this order, giving ploh the victory. In Division 2, the only three coders to solve the Hard took the top three spots, with preyas_p holding off EverettKings in an active challenge phase, and newcomer glee taking third. The ProblemsMultiReadUsed as: Division Two  Level One:
In this problem, you count each write as one cycle and each run of reads as ceiling(size/procs) cycles, where size is the number of reads in the run. Of course, integer division normally rounds down, so you need to do something special to round up instead. One easy formula is (size+procs1)/procs. See boba5551's and xtzz's submissions for nice examples. UnfairDivisionUsed as: Division Two  Level Two: Used as: Division One  Level One:
A glance at the submission and success rates in both divisions reveals that this was a tricky problem. At its core are two nested loops, one from Albert's point of view and one from Betty's point of view. Albert's loop is fairly straightforward. He considers all possible places he could cut and picks the one that gives him the best result. int bestAlbert = 0; for (int a = 1; a < n; a++) { int albert = how much does Albert get if he cuts here? bestAlbert = max(albert,bestAlbert); } return bestAlbert;Betty's loop is where things get tricky. First, you have to remember to switch points of view. Otherwise, you essentially let Albert pick both cuts. For example, consider a list of 9 assets, all worth $1. After both cuts have been made and the assets in each sublist have been totaled, Albert will get the smallest sublist. If Albert got to pick both cuts, he could get $3, by first cutting the 9 assets into a list of 3 and a list of 6, and then cutting the list of 6 into two lists of 3. However, Betty is not so cooperative. If Albert cut the 9 assets into a list of 3 and a list of 6, then Betty would cut the list of 6 into a list of 5 and a list of 1, giving herself $3 and Albert $1. Sure, Betty could cut the list of 6 into two lists of 3 and she would get the same amount. But remember that she holds a grudge and would rather see Albert get $1 than $3. The second tricky part about Betty's loop is getting the tiebreaker rules just right. Many people correctly maximized Betty's share but messed up minimizing Albert's share in the case of ties. Altogether, Betty's loop looks like int bestBetty = 0; int albert = 0; for (int b = 1; b < n; b++) { if (a == b) continue; int i = min(a,b), j = max(a,b); int[] sorted = { sum(0,i), sum(i,j), sum(j,n) }; sort( sorted ); if (sorted[1] > bestBetty  sorted[1] == bestBetty && sorted[0] < albert) { bestBetty = sorted[1]; albert = sorted[0]; } }where sum is a helper function that sums the assets in the given range of indices. See Lyova's solution for a clean implementation of this logic. CannibalsUsed as: Division Two  Level Three:
Three letters: BFS. Breadthfirst search. See any algorithms textbook or gladius's tutorial for a detailed description of BFS. As with all offtheshelf algorithms, however, the hard part is recognizing when to use it. Common tipoffs that BFS might be appropriate are (1) trying to find the smallest number of moves to reach a given state when (2) all moves have equal cost. To use BFS, you first have to decide what a “state” looks like. One thought is the numbers of missionaries and cannibals on each side of the river, but this is redundant because, given the numbers of missionaries and cannibals on one side of the river, you can figure out the numbers on the other side. You also need to keep track of where the boat is. Altogether then, a state is made up of three numbers: the number of missionaries on one side of the river, the number of cannibals on one side of the river, and the position of the boat. Once you know what a state looks like, you need to figure out which states you can get to in one move. You can do this with two loops generating all combinations of missionaries and cannibals that can fit on the boat. However, there are a lot of details to get right. First, you can't put more missionaries or cannibals on the boat than are on that side of the river. Second, you need to make sure that none of the missionaries get eaten, which involves checking the boat and both sides of the river. (If your state only tracks one side of the river, then it is easy to forget to check the other side.) See newcomer glee's submission for a BFSbased solution. InterleavePalUsed as: Division One  Level Two:
Dynamic programming is feared by the vast majority of coders in the world, so it is amusing to see how little provocation a Division 1 coder needs to reach for DP. Especially in problems like this, where a nominally simpler algorithm like depthfirst search is all that is required. Yes, if you want to claim that a DFS that keeps track of which states it has visited is doing a kind of DP, I won't argue with you, but thinking dynamic programming instead of depthfirst search puts you in a different mindset. A depthfirst search for this problem can work either outsidein or insideout. In either case, a state is characterized by start and end points in the first string and start and end points in the second string. A state (A,B,C,D) is true if it is possible to interleave the substrings S.substring(A,B) and T.substring(C,D) to make a palindrome. If you are working insideout, then possible successor states are (A1,B+1,C,D), (A1,B,C,D+1), (A,B+1,C1,D), and (A,B,C1,D+1), depending on which pairs of characters match. Starting from trivial palindromes for empty or singleton substrings, you “grow” larger and larger palindromes, keeping track of the longest you've found. For example, here is a recursive DFS procedure to do the search. void dfs(int slo,int shi,int tlo,int thi) { // only called when s.substring(slo,shi) and t.substring(tlo,thi) // can be interleaved to make a palindrome if (visited[slo][shi][tlo][thi]) return; visited[slo][shi][tlo][thi] = true; int len = (shislo)+(thitlo); if (len > longest) longest = len; if (slo > 0) { if (shi < m && s[slo1] == s[shi]) dfs(slo1,shi+1,tlo,thi); if (thi < n && s[slo1] == t[thi]) dfs(slo1,shi,tlo,thi+1); } if (tlo > 0) { if (shi < m && t[tlo1] == s[shi]) dfs(slo,shi+1,tlo1,thi); if (thi < n && t[tlo1] == t[thi]) dfs(slo,shi,tlo1,thi+1); } }This procedure is called by the main function from all possible starting positions: for (int i = 0; i <= s.length(); i++) { for (int j = 0; j <= t.length(); j++) { dfs(i,i,j,j); if (i < m) dfs(i,i+1,j,j); if (j < n) dfs(i,i,j,j+1); } }PowerCollector Used as: Division One  Level Three:
Obviously, with N up to 10^{18}, we cannot hope to loop through all the numbers and count which ones are powers. However, note that 10^{18} is approximately 2^{60}, so we only need to consider exponents up to about 60. That is a small enough number to loop through. How many powers below N have exponent K? That's just the Kth root of N, with can be found using binary search. (If you trust floating point arithmetic, you could also try N^{1.0/K}, but precision might be a problem.) So, one approach is to sum the roots of N for each possible exponent. Unfortunately, this approach overcounts dreadfully. For example, 16 is counted twice, once as 2^{4} and once as 4^{2}. To avoid this duplication, we only count exponents that are primes. So we would count 16 as 4^{2} but not as 2^{4}. This still doesn't quite work. For example, 64 is still counted twice, once as 8^{2} and once as 4^{3}. We can avoid this by excluding those bases that are themselves powers with a smaller exponent. For example, 4^{3} would be forbidden because 4 is 2^{2}. Now, how many such powers do we need to exclude? Well, it's the number of powers up to the relevant root of N. Hmm, I smell recursion... The core recursive function can be written long countPowers(long N, int p) { // count the powers <= N with a prime exponent < p long count = 1; // always count 1 as a power for (int k = 2; k < p; k++) { if (!isPrime(k)) continue; long r = root(N,k); // the kth root of N, rounded down if (r == 1) break; count += r  countPowers(r,k); } return count; }Then the main function simply calls the recursive function with the original N and a large enough p, such as 60. 
