JOIN
 Match Editorial
SRM 413
Wednesday, August 6, 2008

## 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

Subway2
Used as: Division Two - Level One:
 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*t2. 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;
}```
ArithmeticProgression
Used as: Division Two - Level Two:
 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)
Used as: Division One - Level One:
 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 seqi 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);
}```
InfiniteSequence
Used as: Division Two - Level Three:
 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.

InfiniteSequence2
Used as: Division One - Level Two:
 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.

TreeCount
Used as: Division One - Level Three:
 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.

By otinn
TopCoder Member