Editorial Codeforces #354 round div.2

676A - Nicholas and Permutation

All what you need to solve this problem — find the positions of numbers 1 and n in the given array. Let's this positions equal to p1 and pn, then the answer is the maximum of 4 values:

Asymptotic behavior O(n).

676B - Pyramid of Glasses

The restrictions in this problem allow to simulate the process. Let the volume of one wineglass equals to 2n conventional units. So the volume of the champagne surpluses which will stream to bottom level will always integer number. So let's pour in the top wineglass q * 2n units of champagne, and then we have following case: if in the current wineglass is more champagne than its volume, let's make surplus = Vtek - 2n, and add surplus / 2 of champagne in each of the two bottom wineglasses.

Asymptotic behavior O(n2).

676C - Vasya and String

This problem can be solved with help of two pointers. Let the first pointer is l and the second pointer is r. Then for every position l we will move right end r until on the substring slsl + 1... sr it is possible to make no more than k swaps to make this substring beautiful. Then we need to update the answer with length of this substring and move l to the right.

Asymptotic behavior O(n * alphabet).

676D - Theseus and labyrinth

It is easy to understand that we have only 4 states of the maze. How to solve this problem if there is no any buttons? It is just bfs on the maze (on the graph). Because of buttons we need to add to graph 3 additional levels and add edges between this levels. After that we need to run bfs on this graph and find the length of the minimum path if such exists.

Asymptotic behavior O(n * m).

676E - The Last Fight Between Human and AI

In this problem we have two main cases: k = 0,  k ≠ 0.

1. Case when k = 0. Then the division of the polynomial to the x - k depends only of the value of a0. If a0 is already known then we need to compare it with zero. If a0 = 0 then the human wins, otherwise the human loses. If ai is not known then win who make the move.

2. Case when k ≠ 0. Here we have two cases: all coefficients already known. Then we need to check x = k — is it the root of the given polynomial. Otherwise who will make the last move will win. Let we know all coefficient except one. Let this coefficient is the coefficient before xi. Let C1 is the sum for all j ≠ i  ajk j and C2 = k i ≠ 0. Then we have the equation ai * C2 =  - C1 which always have the solution. If the human will make the last move he need to write the root to the place of the coefficient, otherwise computer will write any number, but not the root.

Asymptotic behavior O(n).