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.)
The ProblemsStringSegmentUsed as: Division Two  Level One:
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. ExtraordinarilyLargeUsed as: Division Two  Level Two: Used as: Division One  Level One:
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 :)
Find out the integer part x and the number of factorial n. while(x<=15 and n>0) { x = factorial of x; n; }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 Used as: Division Two  Level Three: Used as: Division One  Level Two:
This problem was not supposed to be a Div 1medium 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 Used as: Division One  Level Three:
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.
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 bottomup, 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++) nCr[i][0]=nCr[i][i]=1; for(i=2; i<=m*n; i++) for(j=1; j<i; j++) nCr[i][j]=nCr[i1][j1]+nCr[i1][j]; count[0]=0; ok[0]=true; for(i=1; i<1<<m; i++) { count[i]=count[i&i1]+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[p1][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; } } 
