Match Editorials

Match summary

Round 2 of 2009 TCHS Tournament had 334 participants, and 250 of them were to advance to the next round, so a good time on easy guaranteed advancement. The problemset was relatively easy but quite challengeable, and the challenge phase was pretty eventful this time.

The match was won by tourist, due to impressive time on all problems and 3 successfull challenges. exod40 with 5 challenges took the second place, and neal_wu came third.

The Problems

Value	250
Submission Rate	318 / 330 (96.36%)
Success Rate	280 / 318 (88.05%)
High Score	niyaznigmatul for 249.28 points (1 mins 31 secs)
Average Score	221.30 (for 280 correct submissions)

Let a be a string of length m<n which generates the same sequence as s. First, it's evident that a is a prefix of s. Second, note that the sequence generated by a string of length k is periodical with a period equal to k, so if the first m*n elements of the sequences generated by strings a and s are identical, the sequences themselves are the same.

So, to find the shortest string which generates the same sequence as s, one had simply to check all prefixes of s, from the shortest to the longest, and for a prefix of length m check whether the first m*n elements of the generated sequences are the same.

Java code follows:

public class CyclicSequence {
     public String minimalCycle(String s) {
          int m;
          for (m=1; m<s.length(); m++)
          {    boolean ok=true;
               for (int i=0; i<m*s.length(); i++)
                    if (s.charAt(i%m)!=s.charAt(i%s.length()))
                         ok=false;
               if (ok)
                    break;
          }
          return s.substring(0,m);
     }
}

Value	600
Submission Rate	168 / 330 (50.91%)
Success Rate	163 / 168 (97.02%)
High Score	crazyb0y for 581.83 points (5 mins 3 secs)
Average Score	373.79 (for 163 correct submissions)

Let win[i][j] be the probability of competitor i winning against competitor j, and adv[i][k] be the probability of competitor i advancing to round k (denoting winning the tournament as "advancing to round 4"). adv[i][1] is simply 1.0, since all competitors take part in round 1. Let's calculate the values of adv[i][k] for k between 2 and 4, inclusive.

To get to round 2, competitor i must win against one opponent - player i+1 for even i or player i-1 for odd i. Note that the index of the opponent can be calculated as (i xor 1).

adv[i][2] = win[i][i xor 1] = adv[i][1] * adv[i xor 1][1] * win[i][i xor 1]

adv[i][3] = adv[i][2] * (adv[i xor 2][2] * win[i][i xor 2] + adv[i xor 3][2] * win[i][i xor 3])

Value	900
Submission Rate	154 / 330 (46.67%)
Success Rate	88 / 154 (57.14%)
High Score	wcao for 889.45 points (3 mins 6 secs)
Average Score	674.95 (for 88 correct submissions)

If we replace (arrivalTimes[i] - scheduledTimes[i]) with delta[i], the problem is reduced to the following classic problem: given N points on a straight line, find the points on this line with the minimal total distance to these points.

It's easy to prove that after sorting the array delta in ascending order, the points which minimize the total distance to the points of delta are delta[(N-1)/2] for odd N or the interval of points between delta[N/2-1] and delta[N/2] for even N. The answer to the given problem is 1 for odd N and (delta[N/2]-delta[N/2-1]+1) for even N.

One could also implement a more straightforward approach, which included selecting unique points from delta, sorting them, calculating the value of total waiting time in each point, finding a point or two points which minimize the total waiting time and returning the number of points between them.

However, realizing that the wanted points will form a continuous interval with ends in delta was vital for solving this problem, since checking all integer points between minimal and maximal values of delta separately ended in time limit.