Competitive Programming: POJ 2084 – Game of Connections

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

import java.math.BigInteger;
import java.util.Scanner;

/*
 * There are two ways to solve it.
 * 
 * 1. RECURSIVE
 * 
 * Select a fixed point O from one of the 2n points on the circle. A line going 
 * from this point would have to divide the circle into two regions, each 
 * containing an even number of points. There are thus n possible choices for a 
 * chord leaving from O (try drawing it).
 * 
 * Choosing one such chord will lead to unique divisions of the circle (two 
 * different chords leaving from O will give different divisions). Any division 
 * of the circle would match with one of these chords. So we have divided the 
 * problem into a set of disjoint subproblems.
 * 
 * Then, to get a recursive formula, we need to count, for each possible chord,
 * how many points are on each side of the chord : the regions have 
 * (2k, 2(n-k-1)) points, for 0 <= k <= n-1.
 * 
 * So a recursive formula for h(n) would be:
 * 
 *      h(n) = sum, from k = 0 to k = n-1, of h(k) * h(n-k-1)
 *      
 * 2. CLOSED FORM
 * 
 * The solution is the set of Catalan numbers. The nth Catalan number can be 
 * calculated directly as:
 * 
 *     the product, from k = 2 to k = n, of (n + k) / k
 *     
 * NOTE: We use BigIntegers because Catalan numbers get big very quickly. 
 * (See https://oeis.org/A000108)
 *  
 */
public class Main {

	static BigInteger catalan(int n) {

		// dp array containing the sum
		BigInteger[] dpArray = new BigInteger[n + 1];

		dpArray[0] = BigInteger.ONE;
		dpArray[1] = BigInteger.ONE;

		for (int i = 2; i <= n; i++) {
			dpArray[i] = BigInteger.ZERO;

			for (int k = 0; k < i; k++) {
				dpArray[i] = dpArray[i].add(dpArray[k].multiply(dpArray[i - k - 1]));
			}
		}

		return dpArray[n];
	}

	static BigInteger catalanClosedForm(int n) {

		if (n <= 1)
			return BigInteger.ONE;

		BigInteger num = BigInteger.ONE;
		BigInteger denom = BigInteger.ONE;
		
		for (int k = 2; k <= n; k++) {
			num = num.multiply(new BigInteger((n + k) + ""));
			denom = denom.multiply(new BigInteger(k + ""));
		}
		
		return num.divide(denom);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		while (n != -1) {
			System.out.println(catalan(n).toString());
			n = sc.nextInt();
		}
		sc.close();
	}
}