igdor99's blog

By igdor99, 4 years ago, translation, , 580A - Kefa and First Steps

Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.

Asymptotics — O(n).

Solution

580B - Kefa and Company

At first we sort all friends in money ascending order. Now the answer is some array subsegment. Next, we use the method of two pointers for finding the required subsegment.

Asymptotics — O(n log n).

Solution

580C - Kefa and Park

Let's go down the tree from the root, supporting additional parameter k — the number of vertices in a row met with cats. If k exceeds m, then leave. Then the answer is the number of leaves, which we were able to reach.

Asymptotics — O(n).

Solution

580D - Kefa and Dishes

Asymptotics — O(2n * n2).

Solution

580E - Kefa and Watch

At first, we calculate the hash for all line elements depending on their positions. That is, the hash of the number k, standing on the i-th position will be equal to gi * k, where g is the base of the hash. We construct the segment tree of sums, which support a group modification, for all hashes. Thus, we can perform queries for modification in O(log n). It remains to deal with the queries of the second type. Let us assume, that we want to process the query 2 l r d. Obviously, the substring from l to r have a d-period, if a substring from l + d to r is equal to substring from l to r - d. We can find out the sum of hashes at the subsegment with the help of the sums tree, so we can compare the two strings in O(log n).

Asymptotics — O(m log n).

Solution Tutorial of Codeforces Round #321 (Div. 2) Tutorial of Codeforces Round #321 (Div. 2) cf,