Once again we apologize for making mistakes during preparation.

887A - Div. 64

Author: .tx.

If the string contains no ones then the answer is "NO" as the remainig number must be positive. Otherwise we can find the leftmost one and check if it is followed by at least six zeroes.

Solution.

887B - Cubes for Masha

Author: .tx.

The answer is always less or equal to 98. We can go through numbers from 1 to 99 and find the first one which we cannot make using cubes.

Solution.

887C - Solution for Cube

Author: .tx.

The amount of variants of input data for which the answer is "YES" is not more than 12 without considering rearrangement of colours. They all could be written in an array.

The alternative solution is writing a function of rotating a specific edge of the cube and checking if it is solved.

Solution. Denisson

Solution. .tx

887D - Ratings and Reality Shows

Author: .tx.

We can create two arrays of prefix sums of events given in input. The first one on values (a, b) and the second one on values (c, d). The answer is either 0 or the moment of time right after an event occured. Let's use the method of two pointers. One pointer will indicate an event V after which we want to participate in the talk show and the other one at the moment of time right after its influence ends. Then we can participate in the talk show if the minimum of prefix sums on values (c, d) from elements between pointers is not less than the difference of prefix sums on values (a, b) and (c, d) from element V. Also we must check that Izabella's rating doesn't become negative before participating in the talk show or during its peroid of influence.

Solution. Denisson

Solution. .tx

887E - Little Brother

Authors: .tx, Denisson.

The center of required circle is on a perpendicular to the middle of the segment AB where A and B are two points from the input. If a circle with the center on the segment AB and the radius equal to half of its length satisfies the conditions then it is the answer. Otherwise we can find on which side relative to AB the center of the circle is. Every drawn circle blocks a continious interval of allowed values for the requierd circle. The limits of this interval can be found by using binary search. Now we have to find the least allowed value for the radius. It can be done, for example, by using method of scanning line.

Solution. Denisson

Solution. .tx

Solution. cdkrot

887F - Row of Models

Author: Denisson.

For every element of an array a_i we can check x elements on its right. If there are no elements less than a_i we will mark it as "-1" and call it "bad". If there is exactly one element then make an edge from a_i to this element. Otherwise swapping elements of the array will never make a_i "bad". If there are no "bad" elements in the array then the answer is "YES". Otherwise we should find the leftmost "bad" element in the array bad. X elements after it are not less than itself. All elements before it are also not less than itself because otherwise an element less than bad would be "bad" too. Swapping bad with an element in suffix also makes no sense because its place will be taken by lesser element and the position will remain "bad". Thus, swapping bad with other element of the array makes no sense. The only way to satisfy the conditions is to swap one of x elements after bad with other element in the remaining suffix without considering a segment with length x after bad. Let's try to do it obviously. Then the following conditions must be satisfied. Consider choosing an element y in the remaining suffix. Then the swap can be the answer if y < bad. Also suffix after y and the segment between y and the segment with length x after bad must not contain "bad" elements. An element, which we swap y with, from the segment with length x after bad must be less than any adress on y. Also we need to check that after the swap on the right side of y we can find an element less than itself no further than x.

Time: O(n) or O(nlogn).

Solution. Denisson

Solution. Denisson