🔗 Problem #1010

Jaewon has become the mayor of a city. This city has a large, straight river running through it, dividing the city into east and west. However, Jaewon realized that citizens were having great difficulty crossing the river because there were no bridges, so he decided to build some. A location along the river suitable for building a bridge is called a site. After carefully surveying 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 ≤ M)$

Jaewon wants to connect a west-side site to an east-side site with a bridge. (At most one bridge can be connected to any given site.) Since Jaewon wants to build as many bridges as possible, he plans to build as many bridges as there are west-side sites ($N$ of them). Bridges cannot cross each other, and under this condition, write a program that computes the number of ways to build the bridges.

The first line of the input gives the number of test cases $T$. From the next line, each test case gives the integers $N$, $M$ $(0 < N ≤ M < 30)$, the number of sites on the west and east sides of the river respectively.

For each test case, print the number of ways to build the bridges under the given conditions.

• Input

TC
3
2 2
1 5
13 29

• Output

TC
1
5
67863915

The rules can be summarized as follows.

1. Bridges are built from zone $N$ to zone $M$.
2. $N <= M$.
3. Each site has exactly one bridge connected to it.
4. Bridges cannot cross each other.

Since I've been solving problems in order starting from #1000, problem #1007 Vectors made it easy to recognize the keyword "combination" here. Since the problem describes building bridges from zone $N$ to zone $M$, it's easy to fall into thinking in terms of $N$. Instead, thinking in terms of $M$ reveals the key to the solution. This is because we can compute, from the sites in zone $M$, the combinations of sites to connect matching the count of sites in zone $N$.

For example, suppose zone $N$ has 3 sites and zone $M$ has 5 sites.

There are a total of 10 possible cases. This matches the result of $_5C_3$.

$$_5C_3 = \frac{5!}{3! \times 2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)} = \frac{5 \times 4}{2 \times 1} = 10$$

❓ Why does the number have an exclamation mark (!)?
That's the Factorial operator, computed as $n! = n \times (n - 1) \times (n - 2) \times ... \times 1$.

All we need to do is design a straightforward combination algorithm. Since we don't need to return the actual elements of the combination — just the count — this is simpler than problem #1007 Vectors.

If you naively implement the combination algorithm with the formula above, you'll hit a time limit exceeded error. That's because, while the underlying idea is simple, the time limit of 0.5s is very tight. Since the maximum value of $M$ is 30, we may need to compute something on the order of $30!$. Because of this, we need to apply an optimization called memoization.

❓ What is memoization?
A technique that eliminates redundant computation by storing previously computed values in memory and reusing them when the same calculation would otherwise be repeated.

The combination formula can be expressed recursively as follows.

$$_nC_r = _{n-1}C_{r-1} + _{n-1}C_r$$

The picture below makes it easier to understand.

If we compute $_5C_3$, it proceeds as follows.

Here, $_3C_2$ is called multiple times, since it's needed to compute both $_4C_2$ and $_4C_3$. If memoization weren't applied, we'd have to recompute $_3C_2$ from scratch every time it's needed. As numbers get larger, like $_{30}C_{14}$, the depth of the diagram above also grows deeper, causing a lot of overhead.

If we could store these computed values in memory instead of discarding them, we'd gain a huge advantage in computation. If we've already stored $_3C_2$, we can immediately retrieve the stored $_3C_2$ when computing $_4C_2$ and $_4C_3$. We can skip the complex computation, and it doesn't matter how many times the same value is called.

If we store each newly computed value from this problem's combination algorithm into an array and reuse it, we should be able to meet the tight 0.5-second time limit.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Baekjoon problem #1010 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1010">1010 solution</a>
 * @since 2021.06.09 Tue 14:14:09
 */
public class Main
{
	// Number of ways to build bridges
	private static final int[][] dp = new int[31][31];
	
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 *
	 * @throws IOException data input/output exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// Number of cases
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			int N = Integer.parseInt(temp[0]);
			int M = Integer.parseInt(temp[1]);
			
			System.out.println(combination(M, N));
		}
		
		reader.close();
	}
	
	/**
	 * Function that returns the combination result
	 *
	 * @param n: [int] number of elements
	 * @param r: [int] number to choose
	 *
	 * @return [int] combination
	 */
	private static int combination(int n, int r)
	{
		// If already computed
		if (dp[n][r] > 0)
		{
			return dp[n][r];
		}
		
		// If the number of elements equals the number to choose, or is 0
		else if (n == r || r == 0)
		{
			return dp[n][r] = 1;
		}
		
		// General case
		else
		{
			return dp[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
		}
	}
}

Since $dp[n][r]$ is an int array, its default value is 0. That is, if $dp[n][r] > 0$, it means $_nC_r$ has already been computed, so the already stored value is returned.

For cases like $_5C_0$, $_5C_5$ — that is, $_nC_0$, $_nC_n$ — the value is 1. In such cases, 1 is returned. (There's only one way to select everything, or nothing at all.)

For the remaining general cases, the recursive formula for $_nC_r$, which is $_{n-1}C_{r-1} + _{n-1}C_{r}$, applies.

Also, the $dp$ 2D array is initialized with a size of 31x31, since the maximum value of $N$ and $M$, which become the array's dimensions, is 30. Since arrays start indexing at 0, we need to add 1.

Also, note that $dp$ is not reset per case, since combinations are general-purpose and can be reused. The value of $_5C_3$ is 10 regardless of whether it's case #1 or case #100. So, by not resetting it, we can actually reuse values computed in previous cases — a net gain. If, for instance, $_{30}C_{12}$ was computed in the first case, then all of the sub-combinations for something like $_{12}C_{5}$ in a later case could skip computation entirely.

• Math
• Dynamic Programming
• Combinatorics