Saturday, January 10, 2008 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 ProblemsCyclicSequenceUsed as: Division One  Level One:
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.
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); } }One could also note that the length of the prefix should divide the length of the original string, check only the prefixes of such length and only the first n elements of the sequence. TournamentWinner Used as: Division One  Level Two:
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.
adv[i][2] = win[i][i xor 1] = adv[i][1] * adv[i xor 1][1] * win[i][i xor 1]To get to round 3, competitor i must advance to round 2 and win against one of the two opponents who could have advanced to round 2 as well. Competitors 0 and 1 will play against one of the competitors 2 and 3, while competitors 4 and 5 will play against one of the competitors 6 and 7. So, for competitor i the possible opponents' indices can be calculated as (i xor 2) and (i xor 3). 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])The pattern contunues: to get to round k, competitor i must get to round k1 and win against one of the competitors who could have advanced to round k1 as well. Thus, the probability of competitor i winning the tournament can be calculated as sum of (adv[i][3] * adv[i xor m][3] * win[i][i xor m]) over m between 4 and 7. See neal_wu's solution for a clean implementation of this approach. WizardsAppointments Used as: Division One  Level Three:
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.

