There are N points on the circumference. How many ways are there to connect any number of (possibly 0) disjoint strings?
Input:
Read in a number N.
Output :
Since the result can be big, output the answer mod 12345.
Sample input:
4
Sample output:
9
data range:
1 <= N <= 1000
time limit:
1000
Memory limit:
65536
First, we need to find a pattern or equation. We can confirm that both when there are zero points, there is one way to connect them, do nothing. Having one point is also the same, as two points are required to make a string (line segment). But, as the number of points keeps increasing, it becomes obvious that there is no simple pattern. So, we turn to equations.
Let’s approach this problem mathematically. We can split the problem into cases. For the subproblem with zero strings, there is only one way to connect them, do nothing. For the problem with 1 string connecting, you can choose any two points out of the total points, so the number of ways to connect them is nCr(n,2), which means n choose 2. While there are two strings, it becomes n choose 4, and so on. By repeating this until you have used as many sets of two points as possible, you end up with f(n) = f(n-1) + f(0)*f(n-2) + f(1)*f(n-2–1)+…+f(n-2)*f(0).
Next, let’s implement this formula into code. After selecting the libraries, inputting a variable n, and creating an array with size[n], we can move on to the actual code. The equation is recursive, so we should look to call previous values of our array. To do this, we need a couple of starting numbers and their answers. Having already calculated 0,1, and 2, whose answers are 1,1, and 2 respectively, we set
arr[0] = 1
arr[1] = 1
arr[2] = 2.
This gives our formula a starting point.
We need two variables to utilize the formula, which we can set as i and j, defined inside for loops going from
i-0; i <= n (we need to run through all the numbers), and
j = 0; j < i-1 (this is the part of the formula that goes from 0 to i-1).
Instead of using a third variable to represent n-2 to 0, we can use
i-j -2.
Something is missing. We still haven’t added the first term of the right part of the equation, f(n-1). We add that using
arr[i] = arr[i] + arr[i-1] or arr[i] += arr[i-1].
The question also instructs us to mod the result by 12345, so we do that here:
arr[i] = arr[i] % 12345.
Finally, we output the result, the n-th element of our array, arr[n].
