Match Editorial

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

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

(2N-1)/(2N)

N

N

N

2N-1

b

(2N-1)*a/b

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;
  }
};

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

n

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 2⁴⁰ 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.