HackerRank Combinatorics – Volleyball Match

Challenge: Volleyball Match

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464733902

Limbaj: java8

Link challenge: https://www.hackerrank.com/challenges/volleyball-match/problem

Cerinta

Tatyana is a big sports fan and she likes volleyball a lot! She writes down the final scores of the game after it has ended in her notebook. 

If you are not familiar with the rules of volleyball, here's a brief:

+ 2 teams play in total
+ During the course of the game, each team gets points, and thus increases its score by 1. 
+ The initial score is 0 for both teams. 

The game ends when 

+ One of the teams gets 25 points and another team has < 24 points ( strictly less than 24). 
+ If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2.  

Given the final score of a game in the format *A*:*B* i.e., the first team has scored *A* points and the second has scored *B* points, can you print the number of different sequences of getting points by teams that leads to this final score? 

**Input Format**  
The first line contains *A* and the second line contains *B*.  

**Constraints**  

0 ≤ A , B ≤ 10<sup>9</sup>

**Output Format**  
Output the number of different sequences of getting points by the teams that leads to the final score A : B. *Final* means that the game should be over after this score is reached. If the number is larger than 10<sup>9</sup>+7, output number modulo 10<sup>9</sup> + 7. Print `0` if no such volleyball game ends with the given score. 

**Example input #00**

    3
    25

**Example output #00**

<pre>2925</pre>

**Example input #01**

    24
    17

**Example output #01**

<pre>0</pre>

**Explanation #01**

There's no game of volleyball that ends with a score of 24 : 17.

Cod sursa

//https://www.hackerrank.com/challenges/volleyball-match
//See: https://www.hackerrank.com/contests/w1/challenges/volleyball-match
import java.io.*;

public class Solution{

    private final static int MOD = 1000000007;
    private final static int WIN_SCORE_GAP = 2;
    private final static int MIN_WIN_SCORE = 25;
    private final static int MANDATORY_TIE = 24;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());
        int B = Integer.parseInt(br.readLine());
        System.out.print(getNumPossibleGames(A, B));
    }

    private static int getNumPossibleGames(int A, int B){
        if (A < B){
            int temp = A;
            A = B;
            B = temp;
        }

        if (A < MIN_WIN_SCORE){
            return 0;
        }

        if (A == MIN_WIN_SCORE){
            return (A - B < WIN_SCORE_GAP) ? 0 : nCr(A-1, B, MOD);
        }

        if(A - B != WIN_SCORE_GAP){
            return 0;
        }

        int numGames = nCr(MANDATORY_TIE, MANDATORY_TIE, MOD);

        numGames = (int)((((long)numGames) * pow(2, B - 24, MOD))%MOD);
        return numGames;
    }

    private static int nCr(int n, int r, int mod){
        if (n < r){
            int temp = n;
            n = r;
            r = temp;
        }

        if (n < 1 || r < 1){
            return 1;
        }

        int[] row = new int[r];
        for(int i = 0; i < r; row[i++] = 1){}

        for(int i = 2; i < r; ++i){
            for(int j = i-1; j > 0; --j){
                row[j] = (row[j] + row[j-1])%mod;
            }
        }

        --r;
        int sum = row[r];
        for(int i = 0; i < n; ++i){
            for(int j = r; j > 0; --j){
                row[j] = (row[j] + row[j-1])%mod;
            }
            sum = (sum + row[r])%mod;
        }

        return sum;
    }

    private static int pow(int base, int exponent, int mod){
        if (exponent < 2){
            return (exponent < 1) ? 1 : base;
        }
        long product = pow(base, exponent>>1, mod);
        product = (product*product)%mod;
        return ((exponent & 1) == 1) ? (int)((product*base)%mod) : (int)(product);
    }
}