HFCQ2016 Problem Analysis

Ranked first at HFCQ 🙂 (Results | Problems )

I started with the first problem (Two Strings), I found it a bit ambiguous, so I read the second one (Century Coder), but I didn’t understand it (it was about cricket, and I didn’t knew that game), so I skipped it and started thinking on the third problem (Earie String), I realized that this problem requires a suffix array. I haven’t solved many problems with suffix arrays so I felt a bit insecure and turned back to the first problem.
After getting AC on the first problem I cracked the fourth one (Trip To Thailand), I started coding it in C++, however I didn’t had a primalty testing algorithm in hand, so I switched to Java. Later I solved the problem about cricket and the other involving suffix arrays.
With only this four problems I was ranked third, so I went to lunch 🙂
After (a fast) lunch I realized that nobody had cracked the last problem yet. So I though it was a hard problem and I had only 45 minutes to solve it, fortunately I cracked the last problem and got AC 30 seconds before the end of the contest;

Problem Analysis

Two Strings
If $c$ is the number of elements of T, then the answer to the problem will be $2^c$ .
$s_i$ belongs to the multiset if $s_i \neq s_{i-1}$ and $s_i \neq s_{i+1}$
Implementation

Trip To Thailand
Let $n=p_1 \cdot p_2 ... \cdot p_x$ and $k=q_1 \cdot q_2 \cdot ... \cdot q_y$
Then $P(n^{P(k)}) = P(n^{2^y})=(2^y+1)^x$
So the only problem that remains is how to calculate the number of divisors of a square free number $A \leq 10^{17}$
Let’s divide A by all its prime divisors less than or equal to $A^{1/3}$ , the resulting number can only have two prime divisors (why?) So we only need to check if it is a prime or not.

Implementation

Century Coder
The problem can be solved using dp. Let $f[b][n][z]$ be the number of ways of winning if there are $b$ regular balls, $n$ free-hit balls, and the batsman failed scored 0 in the last z runs.

Implementation

Erie Strings
In order to solve any query, we only need to know the following:
1. the number of different substrings in A
2. the number of different substrings in B
3. the number of different substrings that are in A or B (or both)
In order to solve the first two problems, we need to calculate the number of different substrings of length k of a given string S.
That can be done by calculating the suffix array and the LCP – the answer will be the number of indices in which $LCP_i < k$
The third query can be solved similarly concatenating both strings: $S=A + "." + B$ and removing all the substrings of length $k$ that contains the special character "."

Implementation

Panda Game
The moves of the knights determine cycles very similar to the: Island Puzzle

If n is odd:
There is just one cycle that contains all the elements, so we just have to check if the two cycles are equal (with rotations).

If n is even:
1. There are two cycles – one that contains elements at even positions and one of odd positions.
2. The parity of the index of the empty cell must be equal in both configurations.
3. the cycles that contains the empty cell must be equal (with rotations)
4. The cycles that does not contain the empty cell must be equal (without rotations);

Implementation