F: The idea comes from Petrozavodsk Summer 2016. Day 7: Ural FU Dandelion Contest. F. Suffix Array for Thue-Morse.

Build the compacted suffix automaton of $$$fib_n$$$ and you can find some nice structures.

• Every fibonacci word ends with ab and ba alternatively.
• The states corresponding with $$$fib_n, fib_{n-2}, \dots, fib_{n \bmod 2}$$$ are accepting states.
• Except with the edge in the main string, there are $$$\min(n-2,0)$$$ extra edges.
• Every extra edge starts from some position like $$$fib_i-2$$$ and ends at $$$fib_{i+1}-1$$$. The label in the edge is determined by the parity of $$$i$$$.
• We will never go through two extra edges consecutively.

An example for $$$fib_6$$$

       _________a__________                _________________a_______________
      /                    \              /                                 \
0-a->[1]-b->[[2]]-a->[3]-a->4-b->[[5]]-a->6-b->7-a->[8]-a->9-b->10-a->11-a->12-b->[[13]]
\_____b_____/      \__________b_______________/

The [[x]] means the accepting states, and the [x] means a fibonacci word.

It can be seen that we can only use $$$O(n)$$$ states to represent $$$fib_n$$$. And the suffix array can be obtained by walking the compacted suffix automaton. Since the maximum index is $$$10^{18}$$$, we can only keep the last $$$O(\log 10^{18})$$$ nodes.

E: It can be seen that $$$dp_x$$$ equals to some $$$a_i+b_{i+1}+\dots+b_{x}$$$. Let the prefix sum of $$$b$$$ be $$$s$$$,

Use segment tree to maintain the value of $$$a_i-s_i$$$.

Meh, nine <=medium problems that can be done in <=2.5h and one boring killer.

My solution for $$$H$$$ is supposed to be $$$nlogn$$$ but I have been getting TLE with it. Here's my code if someone could help me find out why I'm TLEing: https://ideone.com/AirWlG and I will explain my idea below.

Let's look at the $$$sum$$$ case first. Let $$$totalSum(m)$$$ be the sum of all hamming distances for $$$S^m$$$.

Since $$$S^m = S^{m - 1} + [m] + S^{m - 1}$$$, it's easy to see that $$$totalSum(m)$$$ can be defined recursively as $$$2 * totalSum(m - 1) + subSum(m)$$$. Where $$$subSum(m)$$$ is the sum of the hamming distances of the subarrays that contain $$$m$$$ in $$$S^m$$$ (I will explain the base case later).

Let's solve $$$subSum(m)$$$. Let $$$d$$$ be the smallest $$$d$$$ $$$s.t.$$$ $$$\lvert{S^d}\rvert >= n - 1$$$. The middle part of any $$$S^m$$$ $$$s.t.$$$ $$$ m > d$$$ will look something like this:

$$$[..., v_1, v_2, ..., v_{n - 1}, m, v_1, v_2, ... v_{n - 1}, ...]$$$

Key observation is that for any $$$m > d$$$, All $$$n$$$ subarrays we want to consider in the calculation of $$$subSum(m)$$$ will only differ in the element with value $$$m$$$. I will refer to these subarrays by their order from now on. (e.g. $$$[v_1, v_2, ..., m]$$$ is first subarray, $$$[v_1, v_2, ..., m, v_1]$$$ is the second, and $$$[m, v_1, v_2, ..., v_{n - 1}]$$$ is the $$$n^{th}$$$

Let's define $$$F[i]$$$ to be the hamming distance of the $$$i^{th}$$$ subarray $$$without$$$ the element $$$m$$$. Now $$$F$$$ is the same for all $$$m > d$$$.

Now $$$subSum(m)$$$ is $$$(\sum\limits_{i=1}^n F[i]) + n - freq[m]$$$. Where $$$freq[m]$$$ is the frequency of element $$$m$$$ in array $$$a$$$. (This is because element $$$m$$$ will be compared against event element in $$$a$$$).

We now need to compute 2 things:
(1) $$$F$$$
(2) $$$subSum(d)$$$ (To use this as a base case for our recursive definition above).

We will compute both of them in a similar manner.

Define $$$H(a, b, k)$$$ to be a function that returns a vector $$$ans$$$ of size $$$k$$$. $$$ans[i]$$$ is hamming distance between $$$a$$$ and the $$$i^{th}$$$ cyclical shift of $$$b$$$.

With some goofing around, you can see that you can use this function (or something similar) to get:
(1) $$$F$$$ = $$$H(a, [v_1, v_2, ..., v_{n - 1}], n)$$$.
(2) $$$subSum(d)$$$ = $$$H(a, S^d, length(S^d) - n + 1)$$$.
(I can explain them in another comment if someone wants to but I don't want to make this text any longer than it already is :c).

Key Observation to calculate $$$H$$$ is to see that the $$$b$$$ we send is a special array. It has at most $$$log_2(n)$$$ unique values, and the distance between two occurrences of any element of $$$x$$$ is $$$2^x$$$. You can combine these 2 observations to calculate $$$H$$$ in $$$log_2(n) * k$$$ (I believe its calculation is clear in the code but I could explain it in another comment too if someone wants).

The $$$minimum$$$ case is similar. Define $$$minHamming(m) = min(minHamming(m - 1), minSubHamming(m))$$$.

$$$minSubHamming(m)$$$ will either be $$$minF$$$ or $$$minF - 1$$$. Where $$$minF$$$ is the minimum value in $$$F$$$ calculated above. The case where it will be $$$minF - 1$$$ is when the element $$$m$$$ matches its counterpart in $$$a$$$. You can iterate over indices $$$i$$$ of element $$$m$$$ in $$$a$$$ and minimize with $$$F[n - i - 1]$$$ Since this is the only subarray that will make $$$m$$$ match in index $$$i$$$.

Was solution for D just implication of Sylvester's determinant theorem, like $$$det(M)=x^{n}(1+\sum_{1}^{n}\frac{a_ib_i}{x})$$$? Are there some special cases?

Several teams (including us) missed this case on H:

7 3
1 1 2 1 3 1 2

The answer is 6 6 (there is only one orientation allowed, and it has distance 6), but it's easy to print 1 6 if you accidentally allow the shift i=2 when computing the min. It's a one or two line fix but unfortunately wasn't in the test data.

How to solve I.. ?

For J first you make an observation that if jailings intersect in interesting way then their sets of boundary cells intersect. You also note that number of boundary cells of jailing is at most linear in terms of cells with particular value corresponding to that jailing that lets you iterate through it.

First, for each cell you gather all values such that this cell lies on boundary of corresponding jailings. Then for each value you iterate through all its boundary cells and check it with all values gathered there. I guess it works in $$$O(area)$$$, but no idea why.

How solve G without tl issues?

What was the correct idea for B?

How to solve problem A (Arrange And Count) from div1 ? We thought about DP ,but we didn't manage to solve it.

How to solve problem C (Choose Two Subsequences) from div1 ? We thought about DP ,but we didn't manage to solve it. We got WA2. Um_nik , tourist , pashka, Ra16bit .