Match Editorial

Match summary

With TCCC and GCJ matches filling up the whole month, this was only the second -- and also the last SRM -- of September. Whether the tournament advancers wanted more practice, or the other members were just hungry for matches, there were 1149 participants joining this SRM -- a new record of TopCoder! (Or maybe the actual reason is a simple one, and TopCoder is just getting more popular than ever.)

In Division 1, fast submissions of the 500 and 1000 along with a feast of challenges gave first place to ACRush, with 1813.92 points. This score also earned him a spot on the Highest Match Total list. Rounding out the top three were Petr and Revenger in second and third.

In Division 2, three first-time participants -- MLS, xhl_kogitsune and damien06 -- locked up the top three positions. Congratulations on a nice debut! One surprise is that none of the three come from Top 10 countries for algorithm competitors; instead, they hail from Indonesia, Japan and Australia.

The Problems

Value	250
Submission Rate	523 / 553 (94.58%)
Success Rate	496 / 523 (94.84%)
High Score	ainu7 for 249.14 points (1 mins 40 secs)
Average Score	216.87 (for 496 correct submissions)

In this problem, you need to compute (the sum of segment length)/(number of segments). It is simple and there are no hidden tricks to take down others' solutions. However, if you figure out that the required value is actually equal to (length of s)/(number of segments in s), you can probably save some time.

Value	500
Submission Rate	251 / 553 (45.39%)
Success Rate	32 / 251 (12.75%)
High Score	broutcha for 444.50 points (10 mins 18 secs)
Average Score	265.11 (for 32 correct submissions)

Value	250
Submission Rate	468 / 528 (88.64%)
Success Rate	161 / 468 (34.40%)
High Score	andrewzta for 243.43 points (4 mins 41 secs)
Average Score	163.49 (for 161 correct submissions)

When I got the idea for this problem, I could already foresee the ocean of challenges. What I couldn't foresee is that even my own solution was faulty. (Yes, a solution that I got several weeks to prepare for is faulty.) Fortunately, this is fixed by OlexiyO before the challenge phase :)

The fastest solutions from andrewzta, kalinov and Burunduk1 all adopted the same approach. Given any extraordinarily large number:

Find out the integer part x and the number of factorial n.
while(x<=15 and n>0)
{
   x = factorial of x;
   n--;
}

Value	1000
Submission Rate	127 / 553 (22.97%)
Success Rate	86 / 127 (67.72%)
High Score	ainu7 for 930.13 points (7 mins 54 secs)
Average Score	654.80 (for 86 correct submissions)

Value	500
Submission Rate	433 / 528 (82.01%)
Success Rate	392 / 433 (90.53%)
High Score	ACRush for 493.56 points (3 mins 15 secs)
Average Score	386.26 (for 392 correct submissions)

This problem was not supposed to be a Div 1-medium originally, so I wasn't surprised by the high submission rate and success rate in Division 1. This is a typical dynamic programming problem. Let A[s] be the expected number of matches John will win in the time interval [s,infinity). Then the value of A[s] can be computed backward. A[s] must not be less than A[s+1], since John can choose to give up the time interval [s,s+1) and see how many matches he will win in time interval [s+1,infinity). And for any match that starts at s, ends with t, and with winning probability p, A[s] must be not be less than A[t]+p. Thus, the following pseudo code will compute all the entries of A correctly.

A[maximum_time] = 0
for T = maximum_time - 1 down to 0
   A[T] = A[T+1]
   for each match(s,t,p) with s=T
      A[T] = max(A[T], p+A[t]);

Value	1000
Submission Rate	102 / 528 (19.32%)
Success Rate	74 / 102 (72.55%)
High Score	ACRush for 843.97 points (12 mins 42 secs)
Average Score	523.76 (for 74 correct submissions)

If the probability of an event to occur is p, then the expected number of trials before that event will occur is just 1/p. So, in this problem, you need to find the probability that a random seating plan is good (i.e. no two cheaters sitting on two adjacent seats), and return its reciprocal.

This probability is simply (the number of good seating plans)/(the number of all possible seating plans). The number of all possible seating plans is just (m*n choose k), which is at most (80 choose 20) and fitted within 64-bit integer. The hard part would be to compute the number of good seating plans. Without loss of generality, assume m<=n. Let A[u][v][b] be the number of good seating plans of m by u seats with v cheaters and the u-th column is assigned with cheaters according to the 1-bits in b.

A column with cheaters as bits in b is good if there are no two adjacent bits as 1 in b. Two adjacent columns with cheaters as bits in b1 and b2 is good if b1 is good and b2 is good and b1 bitwise-and b2 is 0. Thus,

if b is good
   for all good b'
      A[u+1][v][b]+=A[u][v-(number of 1's in b)][b']

public class SeatingPlan
{
   private long gcd(long a, long b)
   {
      return a!=0?gcd(b%a, a):b;
   }
   
   public String expectedTrial(int m, int n, int k)
   {
      long[][] nCr=new long[128][128];
      boolean[] ok=new boolean[256];
      int[] count=new int[256];
      long[][][] dp=new long[128][256][32];
      long a, b, g;
      int i, j, p, q;
      
      if(m>n) { p=m; m=n; n=p; }
      
      for(i=1; i<=m*n; i++)
         nCr[i][0]=nCr[i][i]=1;
      for(i=2; i<=m*n; i++)
         for(j=1; j<i; j++)
            nCr[i][j]=nCr[i-1][j-1]+nCr[i-1][j];
      
      count[0]=0;
      ok[0]=true;
      for(i=1; i<1<<m; i++)
      {
         count[i]=count[i&i-1]+1;
         for(j=0; j<m && (3<<j&i)!=3<<j; j++);
         ok[i]=j==m;
      }
      
      dp[0][0][0]=1;
      for(p=1; p<=n; p++)
         for(i=0; i<1<<m; i++)
            for(j=0; j<1<<m; j++)
               if(ok[i] && ok[j] && (i&j)==0)
                  for(q=0; q+count[j]<=k; q++)
                     dp[p][j][q+count[j]]+=dp[p-1][i][q];
      
      for(a=i=0; i<1<<m; a+=dp[n][i++][k]);
      if(a==0)
         return "Impossible!";
      g=gcd(a, b=nCr[m*n][k]);
      a/=g;
      b/=g;
      return ""+b+"/"+a;
   }
}