Get Time
statistics_w  Match Editorial
SRM 320
Saturday, September 30, 2006

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

StringSegment rate it discuss it
Used as: Division Two - Level One:
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.

ExtraordinarilyLarge rate it discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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;
Finally, with two numbers (x1,n1) and (x2,n2), the answer can simply determined by n1 and n2 if they are different, otherwise, determined by x1 and x2.

You can read kalinov's solution for a very clear implementation. (By the way, you probably have no idea how exciting it is to watch the challenge phase!)

ContestSchedule rate it discuss it
Used as: Division Two - Level Three:
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)
Used as: Division One - Level Two:
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]);
Then A[0] is the answer. But there is a problem with the above method. The size of A is too large, up to 1000000000. Note that there are at most 50 cases and thus at most 100 distinct values of time. So a mapping of the times to [0,100] will resolve the problem.

SeatingPlan rate it discuss it
Used as: Division One - Level Three:
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']
After filling the whole table A bottom-up, the number of good seating plan would be the sum of A[n][k][b] for all good b. The following is an implementation of the above method:
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++)
      for(i=2; i<=m*n; i++)
         for(j=1; j<i; j++)
      for(i=1; i<1<<m; i++)
         for(j=0; j<m && (3<<j&i)!=3<<j; j++);
      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++)
      for(a=i=0; i<1<<m; a+=dp[n][i++][k]);
         return "Impossible!";
      g=gcd(a, b=nCr[m*n][k]);
      return ""+b+"/"+a;

By lyc1977
TopCoder Member