Facebook Hacker Cup 2014 – Qualification Round Problem 3


The third problem of the classification problem:

—–
You may be familiar with the works of Alfred Lord Tennyson, the famous English poet. In this problem we will concern ourselves with Tennison, the less famous English tennis player. As you know, tennis is not so much a game of skill as a game of luck and weather patterns. The goal of tennis is to win K sets before the other player. However, the chance of winning a set is largely dependent on whether or not there is weather.

Tennison plays best when it’s sunny, but sometimes of course, it rains. Tennison wins a set with probability ps when it’s sunny, and with probability pr when it’s raining. The chance that there will be sun for the first set is pi. Luckily for Tennison, whenever he wins a set, the probability that there will be sun increases by pu with probability pw. Unfortunately, when Tennison loses a set, the probability of sun decreases by pd with probability pl. What is the chance that Tennison will be successful in his match?

Rain and sun are the only weather conditions, so P(rain) = 1 – P(sun) at all times. Also, probabilities always stay in the range [0, 1]. If P(sun) would ever be less than 0, it is instead 0. If it would ever be greater than 1, it is instead 1.

Input
Input begins with an integer T, the number of tennis matches that Tennison plays. For each match, there is a line containing an integer K, followed by the probabilities ps, pr, pi, pu, pw, pd, pl in that order. All of these values are given with exactly three places after the decimal point.

Output
For each match, output “Case #i: ” followed by the probability that Tennison wins the match, rounded to 6 decimal places (quotes for clarity only). It is guaranteed that the output is unaffected by deviations as large as 10-8.

Constraints
1 ≤ T ≤ 100
1 ≤ K ≤ 100
0 ≤ ps, pr, pi, pu, pw, pd, pl ≤ 1
ps > pr

Sample Input
5
1 0.800 0.100 0.500 0.500 0.500 0.500 0.500
2 0.600 0.200 0.500 0.100 1.000 0.100 1.000
1 1.000 0.000 1.000 1.000 1.000 1.000 1.000
25 0.984 0.222 0.993 0.336 0.207 0.084 0.478
58 0.472 0.182 0.418 0.097 0.569 0.816 0.711

Sample Output
Case #1: 0.450000
Case #2: 0.352000
Case #3: 1.000000
Case #4: 0.999956
Case #5: 0.000000
—–

My Solution

#include <stdio.h>

double mat[100][100][2];
double ps,pr,pw,pu,pl,pd;

double findProbability(int totalSets, int mySets, int oppSets, int wonLast, int first, double pi){
  double winProb, loseProb;
  double newPi;

  if(mySets==totalSets)
    return 1;
  else if(oppSets==totalSets)
    return 0;

  if(mat[mySets][oppSets][wonLast]!=2)
    return mat[mySets][oppSets][wonLast];

  /*calculate pi*/
  if(first)
    newPi = pi;
  else if(wonLast)
    newPi = pw*(pi+pu) + (1-pw)*pi;
  else
    newPi = pl*(pi-pd) + (1-pl)*pi;

  if(newPi>1)
    newPi = 1;
  if(newPi<0)
    newPi = 0;

  /*probability winning this set*/
  winProb = ps*newPi + (1-newPi)*pr;  
  winProb = winProb * findProbability(totalSets, mySets+1,oppSets,1,0,newPi);

  /*probability losing this set*/
  loseProb = 1 - (ps*newPi + (1-newPi)*pr);
  loseProb = loseProb * findProbability(totalSets,mySets,oppSets+1,0,0,newPi);

  
  mat[mySets][oppSets][wonLast] = winProb + loseProb;
  return winProb + loseProb;
}

int main(){
  int k,t;
  int winSets;
  double result;
  int i,j,w;
  double pi;

  scanf("%d",&t);
  
  for(k=0;k<t;k++){
    for(i=0;i<100;i++)
      for(j=0;j<100;j++)
        for(w=0;w<2;w++)
          mat[i][j][w] = 2;      
    scanf("%d",&winSets);
    scanf("%lf %lf %lf %lf %lf %lf %lf",&ps, &pr, &pi, &pu, &pw, &pd, &pl);
    
    result = findProbability(winSets,0,0,0,1,pi);
    if(k>0)
      printf("\n");
    printf("Case %d: %f",k+1,result);    
  }
}


2 thoughts on “Facebook Hacker Cup 2014 – Qualification Round Problem 3

  1. Saad

    Hello Daniel,

    First of all, I thank you for posting your solutions in your blog. I’m concerned about the Third Problem ( the probability problem), I didn’t understand your solution. If only u can give me some clarifications or send me the code with comments , that would very generous from you.

    Thanks in advance.

    Reply
  2. Jitendra

    Sorry for asking stupid question. I am new to facebook hacker cup.
    I want to know how to generate output file for hacker cup problems.

    For example-
    I want to read input from file and write output to a file for below program. How can i do that?

    #include
    using namespace std;

    int main() { int t,n; cin >> t; while (t–) { cin >> n; cout << 2 * n; }

    }

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *