Solution to GCJ2014 R1A

---

Charging Chaos

We can describe the problem in another way:
Given a 0-1 matrix A as the initial matrix and another 0-1 matrix B as the destination matrix.
We can flip some column of A such that the rows of A is a permutation of B.
The basic idea is that after some flips, the first row is equal to one row of B.
We enumerate the index of row of B, which is the first row of A equal to.
An O(n^2l) algorithm comes up.

---

Full Binary Tree

Given a tree, and removes some nodes to make it become a full binary tree.
The first step is to enumerate the root of the full binary tree, then apply tree-shaped dynamic programme.
We use cost[i] to denote the minimal cost of making the sub-tree with root i to become a full binary tree.
Then given a node i, its child count should become 0 or 2.
When a child j of i is selected to remove, then the cost is the nodes count of sub-tree j.
Otherwise, the cost is cost[j].
The problem of find minimal cost to select two children to remain can be solved by dynamic programme.
Total complexity: O(n^2).

---

Proper Shuffle

If it is random uniformly shuffled, the probability of number I existing on position J is 1/N.
Otherwise we can pre-calculate the probability of number I existing on position J.
The sub-problem can be solved in a dynamic programme algorithm in O(n^3) and it is possible to be optimized to O(n^2).
But, a much easier way is to simulate the non-uniform shuffle algorithm one million times and obtain the probability.
We use p[I][J] to denote the probability of number I exists on position J.
The strategy is to compare p[input[0]][0] * p[input[1]][1] * ... * p[input[N-1]][N-1] to (1/N)^N.
The value may be too small, so we apply log function on each value.
When the first value is bigger, the probability of the non-uniform random algorithm is bigger, and vice versa.
There are some other strategies based on other characteristic of the random shuffle algorithm.