[C/C++] #1010 Building bridges(combination)

The Baekjoon Problem #1010 “Building Bridges” requires a certain understanding of the concept of combinations in probability and statistics.

 

constructing bridges

On one side of the river, there are  N  sites, and on the other side, there are  M  sites. The goal is to build bridges connecting the  N  sites on the left side to  M  sites on the right side, ensuring that the bridges do not cross each other. The question asks for the number of ways to do this.

To calculate the number of possibilities, we use either permutations or combinations. In a case like this, where the order must be maintained (e.g., increasing or decreasing), combinations are the appropriate choice. This problem is essentially about selecting  N  items from  M , which is a combination problem.

For more details, refer to the official Baekjoon problem at the following link:
https://www.acmicpc.net/problem/1010

Jaewon has become the mayor of a city. In this city, there is a large straight river that divides the city into east and west. However, Jaewon has realized that the lack of bridges is causing significant inconvenience for the citizens to cross the river, so he decided to build bridges. Suitable locations for building bridges are referred to as “sites.”

After thoroughly inspecting the area around the river, Jaewon found that there are  N  sites on the west side of the river and  M  sites on the east side ( \(N \leq M\) ).

Jaewon plans to connect the sites on the west side to the sites on the east side with bridges. (Each site can only be connected to one bridge at most.) Since Jaewon wants to build as many bridges as possible, he aims to build exactly  N  bridges, corresponding to the number of sites on the west side. Given that the bridges cannot overlap, write a program to calculate the number of possible ways to build the bridges.

 

The first line of input specifies the number of test cases,  T . For each test case, two integers  N  and  M  are given, representing the number of sites on the west and east sides of the river, respectively ( \(0 < N \leq M < 30\) ).

When solving problems on Baekjoon, it is always important to consider the range of numbers, such as whether the problem can be solved using the int data type. Additionally, it is necessary to check whether intermediate calculations exceed the allowable range of the data type. In practice, determining this for every calculation can be tedious, so when in doubt, it is common to use a data type with a broader range.

To calculate combinations, continuous multiplication of numbers is used, which can lead to overflow. In such cases, even if the final result fits in an int type, it may be necessary to use long long during intermediate calculations.

The combination calculation algorithm I used employs a simple for loop. In this case, there is a high chance of overflow during intermediate steps. (Using a different combination calculation algorithm could address this.) When the range of numbers in the combination goes up to 30, overflow is guaranteed with the int type, as  \(10! \approx 10^6\) . The range that the int type can handle is up to about  13! . With long long, the range extends to about  \(10^{18}\) , which corresponds to roughly  24! . For  30! , even long long may need to be carefully considered, but in practice, it is not necessary to multiply all 30 numbers to calculate the factorial.

 

//----------------------------------------------------------
//    baekjoon #1010 - Building bridges
//        - by Aubrey Choi
//        - created at 2019-08-02
//----------------------------------------------------------
#include <stdio.h>

long long comb(int n, int k)
{
    long long c=1;
    if(2*k > n) k=n-k;
    for(int i=1; i<=k; i++)
        c = c*(n--)/i;
    return c;
}

int main()
{
    int t, n, m;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        printf("%lld\n", comb(m,n));
    }
    return 0;
}