|Level 1||Level 2||Level 3|
|Div 1||Level 2||Level 3|
Division One - Level Three:
Division One - Level Two:
Division One - Level One:
SolutionThis problem is pretty similar with DivTwo_LevelTwo problem, but the thing is different because the number of geese has to be even. So the problem is partitioned into two parts, group with even number of geese, and the group with odd number of geese. The answer would be #_of_way_in_even_group multiply #_of_way_in_odd_group.
For the even number group, it could be all dogs, or all geese, either. If we have x number of groups each has even number of elements, then we could make 2^x possible choices.
For the odd number group, it can't be saved until another odd number group popped up.So, we assume we have x number of odd groups, for the number of possible ways, we could choose any even number of groups from these x groups, So the answer for odd group would be The Sum of C(x, Even Number < x), so we need to calculate the sum of binomial coefficient.
For the calculation of binomial coefficient, I used the Dynamic programming again, which could save both time and precision.
1st, DFS makes each element in grids into some group, it returns the number of elements in that group.
2nd, binomial_coefficient returns the table of all coefficients will be need
Theorem: (n, 0) + (n, 2) + ... = (n, 1) + (n, 3) + ... = 2^(n - 1)
Proof: We know from binomial theorem:
(1 + x)^n = (n, 0)x^0 + (n, 1)x^1 + ... + (n, n)x^n
Putting x = 0 and -1, we get:
(n, 0) + (n, 1) + (n, 2) + (n, 3) ... = 2^n
(n, 0) - (n, 1) + (n, 2) - (n, 3) ... = 0
By adding and subtracting (and dividing by 2) we get:
(n, 0) + (n, 2) + ... (n, n - 1) = 2^(n - 1)
(n, 1) + (n, 3) + ... (n, n) = 2^(n - 1)
This theorem could greatly improve the algorithm I used to calculate the number of possible ways to format groups with odd number of elements.