JOIN
 Match Editorial
SRM 305
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 Problems

Used as: Division Two - Level One:
 Value 250 Submission Rate 270 / 304 (88.82%) Success Rate 248 / 270 (91.85%) High Score scorpio2g5 for 244.91 points (4 mins 6 secs) Average Score 193.05 (for 248 correct submissions)

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+procs-1)/procs.

See boba5551's and xtzz's submissions for nice examples.

UnfairDivision
Used as: Division Two - Level Two:
 Value 500 Submission Rate 99 / 304 (32.57%) Success Rate 30 / 99 (30.30%) High Score preyas_p for 417.75 points (13 mins 9 secs) Average Score 272.48 (for 30 correct submissions)
Used as: Division One - Level One:
 Value 250 Submission Rate 274 / 309 (88.67%) Success Rate 189 / 274 (68.98%) High Score soul-net for 236.00 points (7 mins 0 secs) Average Score 169.37 (for 189 correct submissions)

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.

Cannibals
Used as: Division Two - Level Three:
 Value 1050 Submission Rate 8 / 304 (2.63%) Success Rate 3 / 8 (37.50%) High Score preyas_p for 495.20 points (41 mins 37 secs) Average Score 470.58 (for 3 correct submissions)

Three letters: BFS. Breadth-first search. See any algorithms textbook or gladius's tutorial for a detailed description of BFS. As with all off-the-shelf 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 BFS-based solution.

InterleavePal
Used as: Division One - Level Two:
 Value 500 Submission Rate 84 / 309 (27.18%) Success Rate 45 / 84 (53.57%) High Score Ying for 432.85 points (11 mins 33 secs) Average Score 289.05 (for 45 correct submissions)

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 depth-first 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 depth-first search puts you in a different mindset.

A depth-first search for this problem can work either outside-in or inside-out. 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 inside-out, then possible successor states are (A-1,B+1,C,D), (A-1,B,C,D+1), (A,B+1,C-1,D), and (A,B,C-1,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 = (shi-slo)+(thi-tlo);
if (len > longest) longest = len;

if (slo > 0) {
if (shi < m && s[slo-1] == s[shi]) dfs(slo-1,shi+1,tlo,thi);
if (thi < n && s[slo-1] == t[thi]) dfs(slo-1,shi,tlo,thi+1);
}
if (tlo > 0) {
if (shi < m && t[tlo-1] == s[shi]) dfs(slo,shi+1,tlo-1,thi);
if (thi < n && t[tlo-1] == t[thi]) dfs(slo,shi,tlo-1,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:
 Value 900 Submission Rate 36 / 309 (11.65%) Success Rate 18 / 36 (50.00%) High Score Michael_Levin for 754.03 points (13 mins 1 secs) Average Score 559.04 (for 18 correct submissions)

Obviously, with N up to 1018, we cannot hope to loop through all the numbers and count which ones are powers. However, note that 1018 is approximately 260, 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 K-th root of N, with can be found using binary search. (If you trust floating point arithmetic, you could also try N1.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 24 and once as 42. To avoid this duplication, we only count exponents that are primes. So we would count 16 as 42 but not as 24.

This still doesn't quite work. For example, 64 is still counted twice, once as 82 and once as 43. We can avoid this by excluding those bases that are themselves powers with a smaller exponent. For example, 43 would be forbidden because 4 is 22. 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 k-th 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.

By vorthys
TopCoder Member