Wednesday, August 6, 2008 Match summaryIn 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. Top 3 in division 1: Vasyl[alphacom] (1715.26), Zuza (1654.34), klopyrev (1580.38). The ProblemsSubway2Used as: Division Two  Level One:
Distance s you can travel in t seconds by accelerating from 0 m/s: s = 0.5*acceleration*t^{2}.
Without the speed limit the best way is to accelerate length/2 meters and then decelerate the rest of the way. 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: Used as: Division One  Level One:
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. 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:
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. InfiniteSequence2Used as: Division One  Level Two:
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. 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. Used as: Division One  Level Three:
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. 
