Match Editorial

Match summary

In both divisions the SRM started with average times on the easy. The division 1 easy (division 2 medium) was a bit unusual but the forgiving example cases didn't stop many people from submitting their (incorrect) solutions. The division 1 medium (hard version of division 2 hard) was a bit more unusual. Many people with all kinds of ratings submitted very fast solutions. While low rated coders submitting when high rated coders still work indicates a tricky problem, this problem didn't give it's true nature away that easily.

This was the prequel for the most active challenge phase in a while. In total there were 863 challenges in division 1 (467 successful) and 635 in division 2 (211 successful). This meant a large change on the Challenge Success for a Single Match page.

Most challenge points in division 1: OpenGL (700), Egor (650), an extra 23 coders got 300 or more.
Most challenge points in division 2: theycallmemorty (325), kcm1700 (300).

Top 3 in division 1: Vasyl[alphacom] (1715.26), Zuza (1654.34), klopyrev (1580.38).
Top 3 in division 2: kcm1700 (1831.71), theycallmemorty (1696.31), saskuechan (1535.05).

The Problems

Value	250
Submission Rate	541 / 732 (73.91%)
Success Rate	473 / 541 (87.43%)
High Score	kcm1700 for 241.05 points (5 mins 30 secs)
Average Score	166.05 (for 473 correct submissions)

Distance s you can travel in t seconds by accelerating from 0 m/s: s = 0.5*acceleration*t². Without the speed limit the best way is to accelerate length/2 meters and then decelerate the rest of the way.
Done this way it would take t1 = sqrt(length / maxAcceleration) seconds to reach the midpoint. If the speed you would gather in that time is less than or equal to maxVelocity then the result is just 2 * t1. Otherwise you must accelerate to maxVelocity in t2 = maxVelocity / maxAcceleration and keep going until you are 0.5 * maxAcceleration * t2 * t2 meters from the end.

C++ code:

double minTime(int length, int maxAcceleration, int maxVelocity) {
  double t1 = sqrt(length / double(maxAcceleration));
  if(maxAcceleration * t1 > maxVelocity) {
    double t2 = maxVelocity / double(maxAcceleration);
    return (length - maxAcceleration * t2 * t2) / maxVelocity + 2 * t2;
  } else
    return 2 * t1;
}

Value	500
Submission Rate	414 / 732 (56.56%)
Success Rate	80 / 414 (19.32%)
High Score	kcm1700 for 452.67 points (9 mins 23 secs)
Average Score	292.97 (for 80 correct submissions)

Value	250
Submission Rate	590 / 618 (95.47%)
Success Rate	276 / 590 (46.78%)
High Score	bmerry for 243.98 points (4 mins 29 secs)
Average Score	184.75 (for 276 correct submissions)

This problem offered many ways to solve it but most of them suffered from floating point imprecision. If you have not read Representation of Integers and Reals then this would be a good time to do so.
For each seq_i the minimum d = (seq[i] - a0) / (i + 1). You will obviously need the largest of them to have a chance of satisfying all of them. To confirm that your result is valid, you need to check whether seq[i] == floor(a0 + (i + 1) * d) for every i.

C++ code:

double minCommonDifference(int a0, vector <int> seq) {
  // fraction representing 0/1 (minimum permissible value)
  pair <long long, long long> res(0, 1);
  // find d
  for(int i = 0; i < seq.size(); ++i)
    if(res.first * (i + 1) < (seq[i] - a0) * res.second) {
      res.first = seq[i] - a0;
      res.second = i + 1;
    }
  // check whether a solution is possible
  for(int i = 0; i < seq.size(); ++i)
    if(seq[i] != a0 + (i + 1) * res.first / res.second)
      return -1;
  return res.first / double(res.second);
}

Value	1000
Submission Rate	286 / 732 (39.07%)
Success Rate	149 / 286 (52.10%)
High Score	jtmr for 974.88 points (4 mins 35 secs)
Average Score	747.90 (for 149 correct submissions)

This was the easy version of InfiniteSequence2 with x and y set to 0. This simplification allowed simple memoization to pass without problems by doing exactly what the problem statement tells you to do.

C++ code:

map <long long, long long> mem;
long long calc(long long n, int p, int q) {
  if(n == 0)
    return 1;
  if(mem.count(n))
    return mem[n];
  mem[n] = calc(n / p, p, q) + calc(n / q, p, q);
  return mem[n];
}

In other languages you would have to use either an associative container instead of map or use a solution of InfiniteSequence2.

Value	500
Submission Rate	537 / 618 (86.89%)
Success Rate	96 / 537 (17.88%)
High Score	RAVEman for 480.64 points (5 mins 44 secs)
Average Score	344.61 (for 96 correct submissions)

Here you can't do full memoization because of the memory limit and can't do plain recursion because of the time limit so you need to use a hybrid approach.
Since all examples could be passed with simple recursion, many low rated coders submitted without verifying that their solutions is fast enough.
Many extra tests that could be passed by using full memoization. This caused many higher rated coders to fail.
The result was a very low success rate and very active challenge phase.

To fit inside both the time and memory limits you had to memoize the result for a few million smaller values of n and use plain recursion for the rest.
See Krayev_Alexey's code for an example of this.

Value	1000
Submission Rate	68 / 618 (11.00%)
Success Rate	44 / 68 (64.71%)
High Score	klopyrev for 811.34 points (14 mins 24 secs)
Average Score	546.11 (for 44 correct submissions)

This dynamic programming problem offered a few different ways to represent the state/location you were currently in. The main thing to notice is that if you are at vertex v and you came there from vertex parent then you will never reach a vertex you have already visited unless you go from v back to parent.
See ACRush's solution for a double dynamic programming solution or krijgertje's code for an entry to the shortest code competition.