Match Editorial

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

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.

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)

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;

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];
        }
      }

See Lyova's solution for a clean implementation of this logic.

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.

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);
    }
  }

    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);
      }
    }

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 10¹⁸, we cannot hope to loop through all the numbers and count which ones are powers. However, note that 10¹⁸ is approximately 2⁶⁰, 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 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⁴ and once as 4². To avoid this duplication, we only count exponents that are primes. So we would count 16 as 4² but not as 2⁴.

This still doesn't quite work. For example, 64 is still counted twice, once as 8² and once as 4³. We can avoid this by excluding those bases that are themselves powers with a smaller exponent. For example, 4³ would be forbidden because 4 is 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 k-th root of N, rounded down
        if (r == 1) break;
        count += r - countPowers(r,k);
     }
     return count;
  }