AtCoder - ABC185C. Duodecim Ferra

You can practice the problem Duodecim Ferra here.

Problem Statement

There is an iron bar of length L lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length.

Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways. Under the constraints of this problem, it can be proved that the answer is less than 2^63.

Solutions

This problem can be solved using Stars and Bars Theorem. Given the lenght L, we have a Diophantine equation x[0] + x[1] + ... + x[11] = L where x[i] are the lengths of the bars after the division. We need to select 11 positions out of L - 1 positions. For example, if L is 14, we will have the following possible points to cut.

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14

Therefore, the answer is

C(n, r)
= C(L - 1, r - 1)
= C(14 - 1, 12 - 1)
= C(13, 11)
= 78

We can solve it in O(r) time complexity and O(1) space complexity .

nCr can be written as

(n)! / (r)!( / (n - r)!
= (n * (n - 1) * (n - 2) * ... * 1 ) / (r * (r - 1) * (r - 2) * ... * 1) / ((n - r) * (n - r - 1) * (n - r - 2) * ... * 1)
= n * (n - 1) * (n - 2) * ... * (n - (r - 1)) / (r * (r - 1) * (r - 2) * ... * 1)

// AC - 3 ms
void solve() {
    ll L; cin >> L;
    ll ans = 1;
    FOR(i, 1, 12) {
        ans *= L - i; // n * (n - 1) * (n - 2) * ... * (n - (r - 1))
        ans /= i;     // r * (r - 1) * (r - 2) * ... * 1
    }
    OUT(ans);
}

We can turn it to a template for similar problems

template< typename T >
T comb(int64_t N, int64_t K) {
  if(K < 0 || N < K) return 0;
  T ret = 1;
  for(T i = 1; i <= K; ++i) {
    ret *= N--;
    ret /= i;
  }
  return ret;
}

// AC - 7 ms
void solve() {
    ll L; cin >> L;
    OUT(comb<ll>(L - 1, 11));
}

We can also use dynamic programming to solve this problem. The recursive formula is

C(n, r) = C(n - 1, r - 1) + C(n - 1, r)

For r == 0 and n == r, the result would be 1.

// AC - 10 ms
const int mxN = 205;
ll c[mxN][mxN];

void solve() {
    ll L; cin >> L;
    REP(i, l) {
        c[i][0] = c[i][i] = 1;
        FOR(j, 1, i) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }
    OUT(c[L - 1][11]);
}