Match Editorial

This SRM seemed significantly easier than the last few for Division I coders, with seven coders within 50 points of leader tomek after the coding phase. After challenge phase, however, SnapDragon barely pulled ahead by picking up a successful challenge, and he won the match with an impressive 1629.45 points.

On the Division II side of things, the success rates for the easy and medium problems were very high, but many coders were stopped by the hard. The winner of it all was RandySaint, who used his high score on the 950 to finish in first place in Division II by over 100 points over sanjay31.

The Problems

Value	250
Submission Rate	236 / 242 (97.52%)
Success Rate	232 / 236 (98.31%)
High Score	NeverMore for 248.64 points (2 mins 6 secs)
Average Score	229.03 (for 232 correct submissions)

Projectiles coming at KiloMan? No worries, just dodge! Unfortunately, that's not as easy as it sounds. If the shots are coming at height above 2 and KiloMan jumps, then he gets hit, and if they are at height 2 or less and he stands still, then he is also hit. To put that in code, that turns out to be just a couple of if statements:

    hits = 0;
    for (int i = 0; i < pattern.size(); i++) {
        if (pattern[i] > 2 && jumps[i] == 'J') hits++;
        else if (pattern[i] <= 2 && jumps[i] == 'S') hits++;
    }
    return hits;

Value	550
Submission Rate	160 / 242 (66.12%)
Success Rate	142 / 160 (88.75%)
High Score	Krumble for 500.85 points (9 mins 4 secs)
Average Score	309.29 (for 142 correct submissions)

Value	300
Submission Rate	175 / 185 (94.59%)
Success Rate	174 / 175 (99.43%)
High Score	John Dethridge for 291.18 points (4 mins 58 secs)
Average Score	228.25 (for 174 correct submissions)

The algorithm given in the problem statement to open an arbitrary combination lock could basically be directly translated into code.

The initialization step was to set the current rotation direction to counterclockwise, and set N to be the number of numbers in the combination. Rotate the wheel N full turns in the current rotation direction, and then keep rotating until the notch points to the next number in the combination. Then decrement N, reverse the rotation direction, and repeat until there are no more numbers in the combination to input. The high success rate for this problem in both divisions was pretty indicative of its straightforward nature.

    int N = combo.length, L = N;
    double ret = 0;
    int at = start;
    int dir = 1;       //we're calling 1 counterclockwise and 1 clockwise
    for (int i = 0; i < L; i++, N--) {
        int K;
   if (dir == 1) K = combo[i] - at;
   else K = at - combo[i];
   if (K < 0) K += size;
   ret += 360.0 * (N + 1.0*K/size);
   at = combo[i];
   dir = -dir;
    }
    return ret;

Value	950
Submission Rate	48 / 242 (19.83%)
Success Rate	15 / 48 (31.25%)
High Score	RandySaint for 721.58 points (17 mins 9 secs)
Average Score	501.75 (for 15 correct submissions)

What we want is the smallest non-prime that isn't divisible by any of the first N. The first thing to do is determine what the first N primes are. Since N is, at most, 100000, and the 100000th prime is 1299709, you can use a variety of methods: Eratosthenes' Sieve, simply caching the primes as you find them, or the brute force, divide by every number up to the square root method.

At this point, what is the smallest number that isn't divisible by those first N primes that isn't prime, either? First, since it's not prime, it must have at least two prime divisors; for the smallest number possible, there must be only two such divisors, which must each be as small as possible. However, neither of those two numbers can be any of the first N primes, otherwise their product would be divisible by one of those primes. Thus, we take the (N+1)st prime and square it, thus forming the smallest number not divisible by the first N primes that is also not prime itself. Any lower number is either: (a) prime, or (b) divisible by at least one of the first N primes. (The proof is left as an exercise for the reader.)

    int p[100001];
    int at = 0;

    bool prime (int k) {
        for (int i = 0; i < at && p[i] * p[i] <= k; i++)
       if (k % p[i] == 0) return false;
   p[at++] = k;
        return true;
    }

    long long smallestNonPrime (int N) {
        p[at++] = 2;
        int count = 1;
        long long last = -1;
        for (int i = 3; at <= N; i += 2)
            if (prime(i)) last = i;
   return last * last;
    }

Value	500
Submission Rate	131 / 185 (70.81%)
Success Rate	91 / 131 (69.47%)
High Score	tomek for 446.13 points (10 mins 7 secs)
Average Score	299.48 (for 91 correct submissions)

As various match editorial writers have said in the past, the constraints should tell you something about the intended algorithm for the problem. Something like 15 to 20 should scream out "BRUTE FORCE!" And indeed, this problem was very brute-forceable.

What it asked for was the lexicographically earliest answer key that was consistent with the test papers. What many people skimmed over while reading was the stipulation that each question was answered correctly at least once, and the admin room received plenty of "example 2 doesn't work!" messages. But past that, it was a pretty simple loop over all possible answer keys - the maximum number possible was 2^16, or 65536. For each of the possible keys, you just check two things: that the number of right answers by each student is correct, and that the answer to each question appears in some students' answer to that question.

Value	1000
Submission Rate	56 / 185 (30.27%)
Success Rate	49 / 56 (87.50%)
High Score	dgarthur for 954.67 points (6 mins 14 secs)
Average Score	744.43 (for 49 correct submissions)

I just said that 15 to 20 should ring alarm bells, but here's one place that's not going to work. At first glance, it may seem that the best way to do things is a brute-force search over all N! boss orders, but at N = 15, that's not going to run in time. Instead, there's a massive time reduction that can be made by noticing that at any given point, you will have acquired some number of boss weapons, and that beating boss 1 and then boss 2 is exactly the same in terms of state as beating boss 2 and then boss 1. The only difference, perhaps, is the number of shots it takes. Looking at it in this way, the O(2^n) DP solution is the way to go.

Our desired state is the situation where we have all N weapons. To get there, we could have beaten any of those N bosses with any of the other N - 1 weapons, or with the KiloBuster, and we will pick the option that requires the least shots. This process is recursive, so we can just recurse until we get to the base case, which is possessing no weapons. There are a whole lot of overlapping subproblems, or subsets of weapons, so we can cache these efficiently using bitmasks. This one turned out to be essentially a textbook demonstration of DP, as evidenced by the extremely high scores on this problem, not to mention the high success rate by those who did submit.

    int N;
    int shots[16][16], health[15];
    int best[32768];

    int recurse(int x) {
        if (x == 0) return 0;
        if (best[x] != 0) return best[x];
   int ret = 2000000000;
   for (int i = 0; i < N; i++) {
       if ((x & (1 << i)) != 0) {
           int s = health[i];
      for (int j = 0; j < N; j++) {
          if (i != j && (x & 1 << j) != 0 && shots[j+1][i+1] < s)
              s = shots[j+1][i+1];
      }
      int q = recurse(x ^ (1 << i)) + s;
      if (q < ret) ret = q;
       }
   }
   return ret;
    }

    int leastShots(vector<string> damageChart, vector<int> bossHealth) {
        N = damageChart.size()
        for (int i = 0; i < N; i++)
            shots[0][i+1] = health[i] = bossHealth[i];
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) {
           if (i == j || damageChart[i][j] == '0') shots[i+1][j+1] = 1000000;
      else shots[i+1][j+1] = (health[j] + damageChart[i][j] - '1') /
                             (damageChart[i][j] - '0');
            }
   return recurse((1 << N)-1);    
    }

It should be noted that this problem is in fact just the same as the problem of constructing a minimal spanning tree on a directed graph, starting from a specified node, called the root. If I had insisted stubbornly on keeping N = 50, which was the original constraint size when I originally proposed the problem, then DP would also time out and a more sophisticated algorithm would have been necessary. While the undirected MST algorithm can be solved using a greedy algorithm, that doesn't quite work when the edges become directed, as one of the example cases demonstrated.

However, various algorithms have been discovered that solve the directed case of the Minimal Spanning Tree problem. More on such algorithms can be found here. Implementations of the Chu-Liu/Edmonds Algorithm run in O(E log V) on average and O(V^2) for dense graphs, certainly well in time to solve this problem, although with N = 15, it's overkill.