JOIN
 Match Editorial
2008 TopCoder Open
Online Round 3

Saturday, March 1, 2008

## Match summary

Participation 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 Problems

ZenoDivision
Used as: Division One - Level One:
 Value 250 Submission Rate 273 / 295 (92.54%) Success Rate 205 / 273 (75.09%) High Score Petr for 245.97 points (3 mins 38 secs) Average Score 191.30 (for 205 correct submissions)

Task 1: determine the length of the shortest pattern
If the pattern has length

N
then
(2N-1)/(2N)
pieces of the cake will be eaten in the first
N
steps. The easiest way to determine the smallest possible
N
is to set
N
= 1..60 and then check whether
2N-1
is divisible by
b
.

Task 2: determine who eats which piece
This can be accomplished by checking which bits of
(2N-1)*a/b
are 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:
 Value 500 Submission Rate 100 / 295 (33.90%) Success Rate 70 / 100 (70.00%) High Score bhzhan for 368.91 points (18 mins 21 secs) Average Score 247.26 (for 70 correct submissions)

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:
 Value 1000 Submission Rate 94 / 295 (31.86%) Success Rate 72 / 94 (76.60%) High Score nigulh for 931.34 points (7 mins 49 secs) Average Score 641.12 (for 72 correct submissions)

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.

For a clear implementation of this approach see nigulh's solution.

By otinn
TopCoder Member