Practice solutions: NEERC 2007

A. Snooker

B. Join the Strings

Sort the strings using the sorting criteria $s_is_{i+1} < s_{i+1}s_i$.

Proof:

If there is $s_is_{i+1} > s_{i+1}s_i$, you can swap $s_i$ and $s_{i+1}$ to get a better solution.

Question

Can the case that $s_1 > s_2 > s_3$ and $s_1 < s_3$ happen?

C. Twisting the number

Summary

Find the minimum $m$ such that the binary shifting generator $\{ 1, 2, ..., m\}$ can produce all numbers from $1$ to $n$.

Solution

Suppose $n = 10010000100$ in binary.
smallest group representation (SGR) = smallest number that start from 1 and can be used to make $n$ by binary shifting.
In this case, SGR = 1000100100
We can see that $m \leq SGR$
Consider 1000111111 $\Rightarrow$ $m \leq 1000111111$
Consider 1001000011, its SGR = 1000011100 $\Rightarrow$ $m \leq 1000011100$.

Number bigger than $\max m$ will be covered by $1 \leq x \leq \max m$

E. XOR-omania

H. Billing

I. Just Matrix

Summary

Given $n \times n$ matrix $A$, $top$, and $left$.
Construct the matrix such that

• $\sum_{j=1}^{i-1} (a_{jx} > a_{ix}) = top_{ix}$ and
• $\sum_{j=1}^{i-1} (a_{xj} > a_{xi}) = left_{ij}$

Solution

Consider some example
0 0 0 $\Rightarrow$ $a_3 > a_2 > a_1$
0 0 2 $\Rightarrow$ $a_3 < a_1 < a_2$
0 1 2 $\Rightarrow$ $a_3 ...$
So from the $top$ and $left$ matrices, we can determine the relationship between elements in the matrix $A$
$\Rightarrow$ Create a directed graph and do topological sort.

The problem is how do we actually build the relationship.
Cannot do naive brute-force because $n \leq 600$

Maintain a BIT
Consider the number from bottom to top (or from right to left)

0 1 0 2

Our BIT Tree: 0 0 0 0
$a_4$ must be placed in a position that there is exactly two holes before it $\Rightarrow$ the third place.
Our BIT Tree: 0 0 1 0
$a_3$ must be placed in a position that there is exactly zero holes $\Rightarrow$ the first element.
Our BIT Tree: 1 0 1 0
$a_2$ must be placed in a position that there is exactly one hole before it $\Rightarrow$ the fourth position.

Can easily find the position by maintaining a BIT of holes and do binary search.

Total complexity: $O(n^2\log^2{n})$

J. Numbers Painting

K. Extrasensory Perception

Summary

Count the number of pair of $n$ permutations in which two permutations (guess permution and solution permutation) in a pair has exactly $k$ matches ($k$ fixed points).

Bryan’s Solution

Observation 1

Since the probability of each solution is the same $\Rightarrow$ we can fixed the solution to 1 2 3 … $n$.

Can do dynamic programming to find the number of permutation that has exactly $k$ fixed points.

Robert’s Solution

Using inclusion-exclusion principle.

$3!$
$-\binom{3}{1} \times 2!$ // (# of ways to choose fixed point $\times$ # of ways to choose other points (new fixed points can occur, but we are over counting))
$+\binom{3}{2} \times 1!$
$-\binom{3}{3} \times 0!$

Need BigInteger in Java or coding in Python.

L. Remote Control