Codeforces Round #305 Editorial

Python Code by Haghani

Python Code by Zlobober

548B - Майк и весёлая игра

Consider this problem: We have a binary sequence s and want to find the maximum number of consecutive 1s in it. How to solve this? Easily:

ans = 0
cur = 0
for i = 1 to n:
     if s[i] == 0
          then cur = 0
     else
          cur = cur + 1
     ans = max(ans, cur)

Finally, answer to this problem is ans. For each row r of the table, let ans_r be the maximum number of consecutive 1s in it (we know how to calculate it in O(m) right ?). So after each query, update ans_i in O(m) and then find max(ans₁, ans₂, ..., ans_n) in O(n).

Time complexity: $\text{[math]}$

Python Code by Zlobober

547A - Майк, лягушка и цветок

In this editorial, consider p = m, a = h₁, a′ = a₁, b = h₂ and b′ = a₂, x = x₁, y = y₁, X = x₂ and Y = y₂.

First of all, find the number of seconds it takes until height of Xaniar becomes a′ (starting from a) and call it q. Please note that q ≤ p and if we don't reach a′ after p seconds, then answer is - 1.

If after q seconds also height of Abol will become equal to b′ then answer if q.

Otherwise, find the height of Abdol after q seconds and call it e.

Then find the number of seconds it takes until height of Xaniar becomes a′ (starting from a′) and call it c. Please note that c ≤ p and if we don't reach a′ after p seconds, then answer is - 1.

if g(x) = Xx + Y, then find f(x) = g(g(...(g(x)))) (c times). It is really easy:

c = 1, d = 0
for i = 1 to c
     c = (cX) % p
     d = (dX + Y) % p

Then,

f(x)
     return (cx + d) % p

Actually, if height of Abol is x then, after c seconds it will be f(x).

Then, starting from e, find the minimum number of steps of performing e = f(e) it takes to reach b′ and call it o. Please note that o ≤ p and if we don't reach b′ after p seconds, then answer is - 1.

Then answer is x + c × o.

Time Complexity: $\text{[math]}$

547B - Майк и футы

For each i, find the largest j that a_j < a_i and show it by l_i (if there is no such j, then l_i = 0).

Also, find the smallest j that a_j < a_i and show it by r_i (if there is no such j, then r_i = n + 1).

This can be done in O(n) with a stack. Pseudo code of the first part (second part is also like that) :

stack s // initially empty
for i = 1 to n
     while s is not empty and a[s.top()] >= a[i]
          do s.pop()
     if s is empty
          then l[i] = 0
     otherwise
          l[i] = s.top()
     s.push(i)

Consider that you are asked to print n integers, ans₁, ans₂, ..., ans_n. Obviously, ans₁ ≥ ans₂ ≥ ... ≥ ans_n.

For each i, we know that a_i can be minimum element in groups of size 1, 2, ..., r_i - l_i - 1.

Se we need a data structure for us to do this:

We have array ans₁, ans₂, ..., ans_n and all its elements are initially equal to 0. Also, n queries. Each query gives x, val and want us to perform ans₁ = max(ans₁, val), ans₂ = max(ans₂, val), ..., ans_x = max(ans_x, val). We want the final array.

This can be done in O(n) with a maximum partial sum (keeping maximum instead of sum), read here for more information about partial sum.

Time complexity: $\text{[math]}$ .

547C - Майк и пена

We define that a number x is good if and only if there is no y > 1 that y² is a divisor of x.

Also, we define function f(x) as follow:

Consider x = p₁^a₁ × p₂^a₂ × ... × p_k^a_k where all p_is are prime. Then, f(x) = a₁ + a₂ + ... + a_n.

Use simple inclusion. Consider all the primes from 1 to 5 × 10⁵ are p₁, p₂, ..., p_k.

So, after each query, if d(x) is the set of beers like i in the shelf that x is a divisor of a_i, then number of pairs with gcd equal to 1 is: $\text{[math]}$

Consider good numbers from 1 to 5 × 10⁵ are b₁, b₂, ..., b_m. The above phrase can be written in some other way: |d(b₁)| × ( - 1)^f(b₁) + |d(b₂)| × ( - 1)^f(b₂) + ... + |d(b_m)| × ( - 1)^f(b_m).

So, for each query if we can find all good numbers that a_i is divisible by them in a fast way, we can solve the rest of the problem easily (for each good number x, we can store |d(x)| in an array and just update this array and update the answer).

Since all numbers are less than 2 × 3 × 5 × 7 × 11 × 13 × 17, then there are at most 6 primes divisible buy a_i. With a simple preprocesses, we can find their maximum and so easily we can find these (at most 6) primes fast. If their amount is x, then there are exactly 2^x good numbers that a_i is divisible by them (power of each prime should be either 0 or 1).

So we can perform each query in O(2⁶)

Time complexity: $\text{[math]}$ .

547D - Майк и рыба

Consider a bipartite graph. In each part (we call them first and second part) there are L = 2 × 10⁵ vertices numbered from 1 to L. For each point (x, y) add an edge between vertex number x from the first part and vertex number y from the second part.

In this problem, we want to color edges with two colors so that the difference between the number of blue edges connected to a vertex and the number of red edges connected to it be at most 1.

Doing such thing is always possible.

We prove this and solve the problem at the same time with induction on the number of edges :

If all vertices have even degree, then for each component there is an Eulerian circuit, find it and color the edges alternatively_ with blue and red. Because graph is bipartite, then our circuit is an even walk and so, the difference between the number of blue and red edges connected to a vertex will be 0.

Otherwise, if a vertex like v has odd degree, consider a vertex like u that there is and edge between v and u. Delete this edge and solve the problem for the rest of the edges (with the induction definition) and then add this edge and if the number of red edges connected to u is more than the blue ones, then color this edge with blue, otherwise with red.

You can handle this add/delete edge requests and find odd vertices with a simple set. So,

Time complexity: $\text{[math]}$

547E - Майк и друзья

call(i, j) = match(s_jins_i) which match(tins) is the number of occurrences of t in s.

Concatenate all strings together in order (an put null character between them) and call it string S. We know that $\text{[math]}$ .

Consider N = 5 × 10⁵. Consider Consider for each i, S_{x_i}s_{x_i + 1}...s_{y_i} = s_i (x_i + 1 = y_i + 2).

Also, for i - th character of S which is not a null character, consider it belongs to s_{w_i}.

Calculate the suffix array of S in $\text{[math]}$ and show it by f₁, f₂, ..., f_|S| (we show each suffix by the index of its beginning).

For each query, we want to know the number of occurrences of s_k in S_{x_l}...s_{y_r}. For this propose, we can use this suffix array.

Consider that we show suffix of S starting from index x by S(x).

Also, for each i < |S|, calculate lcp(S(f_i), S(f_i + 1)) totally in $\text{[math]}$ and show it by lc_i.

For each query, consider f_i = x_k, also find minimum number a and maximum number b (using binary search and sparse table on sequence lc) such that a ≤ i ≤ b and min(lc_a, lc_a + 1, ..., lc_i - 1) ≥ |s_k| and min(lc_i, lc_i + 1, ..., lc_b - 1) ≥ |s_k|.

Finally answer of this query is the number of elements in w_a, w_a + 1, ..., w_b that are in the interval [l, r].

This problem is just like KQUERY. You can read my offline approach for KQUERY here. It uses segment tree, but you can also use Fenwick instead of segment tree.

This wasn't my main approach. My main approach uses aho-corasick and a data structure I invented and named it C-Tree.

Time complexity: $\text{[math]}$

C++ Code by PrinceOfPersia ( $\text{[math]}$ )

C++ Code by Haghani (Suffix array construction in $\text{[math]}$ and the rest in $\text{[math]}$ )