CF #83

B. Basketball team. The trick is to calculate 1.0-ans, and it is (sum-s[h] choose n-1)/(sum-1 choose n-1). Took quite some time to figure it out.

C Arrangement
http://codeforces.com/contest/107/problem/C
I don't know if this is a hard problem but it took me almost a week to understand what's going on. The problem looks innocent enough, put n professors into n seats, return the yth permutation (1-based) in lexicographic order, with additional restriction that prof at pos=a must be less than prof at pos=b, if edge(a,b) is given in the input. A natural idea is to enumerate and count. Suppose profs are 0 to n-1, and seats are 0 to n-1. You fill pos from 0 to n-1 one by one.

For pos=0, you first try prof=0 at pos=0. Then count #perms with prof[0] at seat[0]. If this is >=k, then you know prof[0] is at seat[0]. Now work on pos=1, ...

The hard part is to count #perm with pos 0..p-1 already fixed to some prof. Now how do you do this? It has to be some DP solution. Since prof at pos=b has to be less than all prof at pos=a with edge(a,b), you kind of have to know the profs at all such pos=a when you put a prof at pos=b. So this tells you that you work in the order of prof when do counting. You can put prof[0] at pos=0 to n-1, after that you can put prof[1] at pos=0 to n-1...

// count number of perms with some prof fixed
long long calc(int elem, int n, int taken, int fixed[])
{
if elem>=n, found a perm to place all profs, so return 1
if dp[taken]>=0, subproblem solved before, so return dp[taken]

ans=dp[taken];
ans=0;
if (elem appear in fixed[]) {
if (pos=fixed[elem] not taken)
ans=calc(elem+1,n,taken|1< }
else {
try p=0 to n-1 for elem
if (p not taken and all pred[p] are taken)
ans += calc(elem+1,n,taken|1< }
return ans;
}

D. Crimes
only 6 or less may have m[i]>=2.
for m[i]=1, let there be k of them, number of seq is k^n if only use m[i]=1.
but how to count m[i]>=2 ones, with n=10^18

E. Darts
the only problem is to calculate the area covered by one or more rectangles. Given there are n=500 rectangles, there has to be a way to do it faster than inclusion-exclusion.