Online Round 3 Saturday, March 1, 2008 Match summaryParticipation in this round was a requirement for getting a TCO08 t-shirt in the algorithm competition. 295 of the 300 advancers from round 2 were excited about the opportunity although the potential magical properties of the t-shirts have not been confirmed. The first two problems were of expected difficulty while the third one was slightly easier than usual. In the end a fast solution for the easy problem was enough to be among the 150 advancers to the last online round. The top three consisted of two usual suspects: ACRush first and Petr third. The second place went to a new target, yuhch123. The ProblemsZenoDivisionUsed as: Division One - Level One:
Task 1: determine the length of the shortest pattern Nthen (2N-1)/(2N)pieces of the cake will be eaten in the first Nsteps. The easiest way to determine the smallest possible Nis to set N= 1..60 and then check whether 2N-1is divisible by b. Task 2: determine who eats which piece This can be accomplished by checking which bits of (2N-1)*a/bare set. If the bit is set then you will eat the piece, otherwise your friend will. For a clear implementation of this approach see Petr's solution. BattleDice Used as: Division One - Level Two:
This problem was the slowest solved one, nonetheless it was solvable by quite straightforward brute force. This can be done by generating all possible third dice and then calculating the probability that you win. The possibility of a tie can be ignored since previous throws don't affect the later throws in any way. As always with the kind of problems where you are asked to return the lexicographically earliest solution, it is a good idea to generate the possibilities in that order. C++ implementation follows (it passes in approximately 150 milliseconds in worst case): struct BattleDice { vector <int> d1, d2, d3, result; int len, r, ibeat[2][16], beaten[2][16]; double best, p1b2; void Solve(int p, int m, int ibeat1, int ibeat2, int beaten1, int beaten2) { if(p == len) { double p1b3 = beaten1 / double(ibeat1 + beaten1); double p2b3 = beaten2 / double(ibeat2 + beaten2); double now = min(max(1-p1b2, 1-p1b3), min(max(p1b2, 1-p2b3), max(p1b3, p2b3))); if(now > best) { best = now + 1e-9; result = d3; } } else for(d3[p] = m; d3[p] <= r; ++d3[p]) Solve(p + 1, d3[p], ibeat1 + ibeat[0][d3[p]], ibeat2 + ibeat[1][d3[p]], beaten1 + beaten[0][d3[p]], beaten2 + beaten[1][d3[p]]); } void prep() { int ibeat = 0, beaten = 0; for(int i = 0; i < len; ++i) for(int j = 0; j < len; ++j) if(d1[i] < d2[j]) ++beaten; else if(d1[i] > d2[j]) ++ibeat; p1b2 = ibeat / double(ibeat + beaten); } vector <int> die3(vector <int> die1, vector <int> die2, int range) { best = 0; len = die1.size(); r = range; d1 = die1; d2 = die2; d3.resize(len); memset(ibeat, 0x00, sizeof(ibeat)); memset(beaten, 0x00, sizeof(beaten)); for(int j = 1; j <= r; ++j) for(int i = 0; i < len; ++i) { if(j < d1[i]) ++beaten[0][j]; else if(j > d1[i]) ++ibeat[0][j]; if(j < d2[i]) ++beaten[1][j]; else if(j > d2[i]) ++ibeat[1][j]; } prep(); Solve(0, 1, 0, 0, 0, 0); return result; } };SuperWatch Used as: Division One - Level Three:
Given some time zones and an equal number of times in different zones in an infinitely long day, the minimum possible imprecision can be calculated by subtracting the n. smallest time zone offset from the n. smallest time and then subtracting the smallest such element from the largest. To the dismay of 295 coders, the days in this problem were not infinitely long.
Each of the times is given for either day N or day N + 1. Checking 240
possibilities is clearly too much so the most naive solution is out of the
question. Looking at the above algorithm for calculating the minimum imprecision
one should notice that adding a day to any time other than the smallest one can
never improve the result. At the same time it is never useful to add more than
one day to any of the times. Thus one can just try to add a day to the first M
times and see whether it produces a more optimistic result.
|
|