Knockout Tournaments

This problem is also from recent Dhaka Regional contest. Problem link -
http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010

The problem in short would be

For a number of tennis tournaments, each consisting of 8 rounds, you are given total number of wins (W) and losses (L). You have to find your average performance (round you reached) considering all possible scenarios. Two scenarios are different if the number of tournament played is different. W and L both are between 0 and 2*10^8.

First we need to check if the given data is valid or not. For that we'll need to calculate minimum and maximum number of tournaments possible with given W and L. There will be at least L tournaments played. Minimum number of tournaments will occur when the player reaches the final of each tournament and loses the final. So, there will be 7 wins for each loss. Any additional wins after that will mean that there will be one tournament played for each 8 matches. Hence,

minT = L + max( (W-7L+7)/8, 0)

Maximum number of tournaments will occur when the player loses first round of L tournaments and then wins 8 matches a tournament to a total of (W/8) tournaments. Hence,

maxT = L + (W/8)

If minT is greater than maxT, then the data is invalid.

Now, for solving the problem, we need to consider each possible number of tournaments between minT and maxT separately. One observation is that if we don't win any tournament, sum of the rounds reached will be just (W+L). For example, with L = 2 and W = 4, number of tournaments can only be 2 and possible rounds reached will be (1,5), (2,4), (3,3), (4,2) and (5,1). The problem with the tournaments where the player becomes champion is that after winning round 8, he remains in round 8 and doesn't advance to round 9. But this case is actually not different from the previous case. This is how - for a round R you reach (but doesn't eventually win the tournament) you will require 1 loss and (R-1) wins making a total of R matches. Now for winning the tournament, you'll need to win 8 matches and lose 0. So, losing the final (W=7, L=1) and winning the tournament (W=8, L=0) both mean you're in round 8.

So, for a particular tournament with T matches, the average round you reach is (W+L)/T. Considering all possible scenarios, this average becomes -

avgPerf = (1/nT) * Sum[(W+L)/T, minT, maxT]

Here

nT =  total number of scenarios = maxT - minT + 1

and Sum[x,a,b] means summation of all terms for values between a and b.

We can rewrite this equation like below -

avgPerf = (W+L)/nT * (Sum[1/T, 1, maxT] - Sum[1/T, 1, minT-1])

We can see that each of the summations become a different Harmonic number. The n-th Harmonic number is defined as -

Hn = 1 + 1/2 + 1/3 + ..... + 1/n

 Now, there are no closed form formula for calculating n-th Harmonic number. We have 2 options here -

• Calculate once and store the harmonic numbers in a array. But the maximum Harmonic number we will need to calculate is 2*10^8 + (2*10^8) / 8 which is way too high to store in an array. What we can do here is store every thousandth number which will require roughly 2*10^5 numbers to be stored and then for each test case we can calculate the actual number by looping from the nearest thousand.
• Use an approximation formula. You can find description of one such formula here - http://www.cs.cas.cz/portal/AlgoMath/MathematicalAnalysis/MathematicalConstants/HarmonicNumber.htm

I've used the approximation formula. But as the formula fluctuates around the actual value by large margin for small values of n, what I've done is to use the approximation formula for only for values of n greater than 1000.

Source code follows - 

/*
Problem Name : Knockout Tournaments
Problem Number : Archive 4859
Link   : http://acm.uva.es/archive/nuevoportal/region.php?r=as9&year=2010
Problemsetter : Shahriar Manzoor
Problem Type : Math, Harmonic Number
Difficulty  : Medium
Complexity  : O(1)
Date   : November 11, 2010
Useful Links : http://www.cs.cas.cz/portal/AlgoMath/MathematicalAnalysis/MathematicalConstants/HarmonicNumber.htm
    : http://en.wikipedia.org/wiki/Bernoulli_number
*/

#include <stdio.h>
#include <math.h>

#define max(a,b) (((a)>(b))?(a):(b))

const double gamma = 0.5772156649;

double Bn[] = {1.0/6.0, -1.0/30.0, 1.0/42.0, -1.0/30.0, 5.0/66.0};

//calculates n-th Harmonic number
//Hn = 1 + 1/2 + 1/3 + ..... + 1/n
double Hn(int n) {
 if(n <= 0) return 0;
 double r = 0;
 int i;
 if(n <= 1000) {
  for(i = 1; i <= n; i++) {
   r += (1.0/(double)i);
  }
  return r;
 }
 r = log(n) + gamma + .5/n;
 for(i = 0; i < 5; i++) {
  r -= (Bn[i] / (2.0*(i+1)*pow(n,2*(i+1)))) ;
 }
 return r;
}

int main() {
 int kase = 1;
 int W,L;
 int minT, maxT;
 double res;
 while(scanf(" %d %d",&W,&L) == 2) {
  if(W == 0 && L == 0) break;
  printf("Case %d:\n",kase++);

  minT = L + max( (W-7*L+7)/8, 0);
  maxT = L + (W/8);
  if(minT > maxT) {
   printf("Situation Impossible.\n");
   continue;
  }

  res = ((W + L) / (double) (maxT - minT + 1)) * (Hn(maxT) - Hn(minT - 1));
  printf("On Average Bob Reaches Round %.2lf\n",res);
 }
 return 0;
}