672A - Summer Camp

This one is a simple brute force problem, we will construct our array. Adding numbers between 1 and 370 will be enough. After construction we just have to print n-th element of array.

672B - Different is Good

We observe that in a good string all letters must be different, because all substrings in size 1 must be different. So if size of string is greater than 26 then answer must be  - 1 since we only have 26 different letters.

Otherwise, Let's suppose we have k different letters in string sized n, in our string k elements must be stay as before, all others must be changed. So will be (n — k). Here is the code.

671A - Recycling Bottles

Let's solve the problem when Adil and Bera in the same coordinate with bin. Then answer will be , let's say T to this value. If Adil will take i-th bottle and Bera will take j-th bottle (i ≠ j), then answer will be T + distance(Adil, Bottle_i) - distance(Bin, Bottle_i) + distance(Bera, Bottle_j) - distance(Bin, Bottle_j).

Because for all bottles but the chosen ones we have to add 2  *  distance(bottle,  bin).

For example if we choose a bottle i for Adil to take first then we have to add distance(Adil,  Bottle_i) + distance(Bottle_i,  Bin).

In defined T we already count 2 * distance(Bottle_i,  Bin) but we have to count distance(Adil, Bottle_i) + distance(Bottle_i,  Bin) for i.

So we have to add distance(Adil,  Bottle_i)-distance(Bottle_i,  Bin) to T.

Because 2 * distance(Bin,  Bottle_i)+distance(Adil,  Bottle_i)-distance(Bin,  Bottle_i) is equal to distance(Adil,  Bottle_i)+distance(Bottle_i,  Bin).

Lets construct two arrays, a_i will be distance(Adil, Bottle_i) - distance(Bin, Bottle_i), and b_j will be distance(Bera, Bottle_j) - distance(Bin, Bottle_j).

We will choose i naively, after that we have to find minimum b_j where j is not equal to i. This one easily be calculated with precalculations, let's find optimal opt1 for Bera, also we will find second optimal opt2 for Bera, if our chosen i is equal to opt1 then Bera will go opt2, otherwise he will go opt1.

Don't forget to cases that all bottles taken by Adil or Bera!

Here is the code.

671B - Robin Hood

We observe that we can apply operations separately this means first we will apply all increase operations, and after will apply all decrease operations, vice versa. We will use following algorithm.

We have to apply following operation k times, add one to minimum number in array. We will simply binary search over minimum value after applying k operation. Let's look how to check if minimum will be great or equal to p. If is less or equal to k then we can increase all elements to at least p. In this way we can find what will be minimum value after k operations.

Let's say this minimum value to m. After we find it we will increase all numbers less than m to m. But there may be some operations we still didn't apply yet, this number can be at most n - 1, otherwise minimum would be greater than m because we can increase all numbers equal to m by one with this number of increases. Since minimum has to be same we just have to increase some elements in our array that equal to m.

We will use same algorithm for decreasing operations. Finally we will print max element — min element in final array. Overall complexity will be O(nlogk).

Here is the code.

Solution with another approach code.

671C - Ultimate Weirdness of an Array

If we calculate an array H where H_i is how many (l - r)s there are that f(l,  r)  ≤  i, then we can easily calculate the answer.

How to calculate array H. Let's keep a vector, v_i keeps all elements indexes which contain i as a divisor — in sorted order. We will iterate over max element to 1. When we are iterating we will keep another array next, Let's suppose we are iterating over i, next_j will keep leftmost k where f(j,  k)  ≤  i. Sometimes there is no such k, then next_j will be n + 1. H_i will be equal to , because if we choose p as l, r must be at least next_p, so for l we can choose n-next_p+1 different r s.

Let's look how we update next array when we iterate i to i - 1.

Let v_i be b₁, b₂, b₃...b_k. Note that our l - r must be cover at least k - 1 of this indexes. l must less or equal to b₂. So we have to maximize all next_p with n + 1 where p > b₂. Otherwise If l ≥ b₁ + 1 then r must be at least b_k, that's we will maximize all next_p's where b₁ < p ≤ b2 with b_k. And finally for all next_p's where (1 ≤ p ≤ b₁) we have to maximize them with b_k - 1. Observe that next array will be monotonic  -  in non decreasing order  -  after all operations. So we can easily make our updates with a segment tree that can perform following operations:

 - Returns rightmost index i where next_i is less than some k.

 - Returns sum of all elements in next array.

 - Can assign some k to all elements between some l and r.

If all update and queries performed in O(logn) then overall complexity will be O(nlogn), we can also apply all this operations with STL set in same complexity.

Code with set structure: link

Code with segment tree: link

671D - Roads in Yusland

I want to thank GlebsHP, i originally came up with another problem similar to it, GlebsHP suggested to use this one in stead of it.

Let's look for a optimal subset of paths, paths may intersect. To prevent from this let's change the problem litte bit. A worker can repair all nodes between u_i and some k, where k is in the path between u_i and v_i with cost c_i, also paths must not intersect. In this way we will never find better solution from original problem and we can express optimal subset in original problem without any path intersections in new problem.

Let's keep a dp array, dp_i keeps minimum cost to cover all edges in subtree of node i, also the edge between i and parent_i. How to find answer of some i. Let's choose a worker which u_j is in the subtree of i and v_j is a parent of node i. Then if we choose this worker answer must be c_j + (dp_k where k is child of a node in the path from u_j to i for all k's). Of course we have to exclude nodes chosen as k and in the path from u_j to i since we will cover them with j-th worker. We will construct a segment tree by dfs travel times so that for all nodes, workers which start his path in subtree of this node can be reached by looking a contiguous segment in tree. In node i, segment will keep values what will be dp_i equal to if we choose this worker to cover path between u_j and parent_i. We will travel our tree with dfs, in each i after we calculated node i's children dp's we will update our segment in following way, add all workers to segment where u_j = i with value c_j + (sum of node i's children dp's). For all workers v_j equal to i, we must delete it from segment, this is assigning inf to it. The only thing we didn't handle is what to do with workers under this node. Imagine all updates in subtree of node k where k is a child of node i. We have to increase all of them by (sum of node i's children dp's-dp_k). After applying all of this operations answer will be minimum value of workers start their path from a node in subtree of i in segment tree.

Overall complexity will be ((n + m)logm).

Please look at the code to be more clear.

671E - Organizing a Race

Intended solution was . Here is Zlobober's code: Link.

O(n²) Solution

Let cost(l,  r) be minimum cost to make l-r suitable for a race. In task we have to find such l-r that cost(l,  r)  ≤  k and r-l+1 is maximum.

How to calculate cost(l,  r): Let's look at how we do our increases to make race from l to r (first stage) possible. Greedily we will make our increases in right as much as possible. So if we run out of gas in road between i and i+1 we will add just enough gasoline to G_i. After make first stage possible we will add gasoline to r just enough to make second stage possible. This solution will be O(n³).

Let's find next_i, next_i will keep leftmost j that we can't reach with current gasoline, we will also keep need_i that keeps how many liter gasoline we have to add to next_i-1. After applying this increase city next_i will be reachable from i, cars will be consumed all of their gasoline just before taking gasoline in city next_i.

How to find it: We will keep an array pre where pre_i  =  pre_i - 1 + G_i-W_i. If pre_j-pre_i - 1 < 0 then we can't reach to j + 1. If we find leftmost j (j ≥ i) where pre_j is strictly smaller than pre_i then next_i will be equal to j and need_i will be equal to pre_j-pre_i - 1.

Building tree: Let's make a tree where next_i is father of node i. In dfs travel, when we are in a node i all increases will be made to make all first stages possible from i to all j's, now we will keep an array suff where suff_i  =  suff_i - 1 + G_i-W_i - 1. So when we are increasing a city u's G_u we have to increase all suff values from u to n. We will also keep another array cost, cost_j will keep the cost to make stage 1 possible from i to j+1. Increases will be nearly same, for u we will increase all v's costs v ≥ u. So when we reach a node i we will apply increases to make first stage possible between i ans next_i. When we are done with this node, we will revert increases.

Last part: Now we have to find rightmost j for all i's. Let's look at whether it is possible or not for a j. We can check it in O(1). First cost_j - 1 must be less or equal to k, also maximum(suff_k i ≤ k < j)-(suff_j-delta_j) + (cost_j-delta_j)  ≤  k. delta_j keeps how many increases we apply to node j. We will decrease them since direct increases in j are made for j+1, we don't need to keep delta array since it will not effect expression. Also observe that the only thing changes in expression is maximum(suff_k i ≤ k < j). In this way problem can be solved in O(n²). Both sqrt dec. solutions are using the same idea. Main solution will be posted soon.

How to Reduce it to O(nlog²n)

Let p_i be cost_i-suff_i. As we said before this value will never change.

Let's keep a segment tree. In each node we will keep such values. Assume this node of segment covers between l and r. We will keep such ind1, ind2 and mx_suff.

ind1 will keep minimum p_j's index where l ≤ j ≤ r.

ind2 will keep minimum (maximum{suff_{l≤ k < j}}+p_j)'s index where mid + 1 ≤ j ≤ r this means we have to choose j from this nodes right child.

mx_suff will keep maximum{suff_l≤k≤r}.

We also have to keep values for ind1 and ind2 (p_ind1 and (maximum{suff_{l≤ k < ind2}}+p_ind2)).

How to update them: In a update we will increase some some suffixes cost_i and suff_i values. So ind1 will be same for each node. For every covered node mx_suff will increase by k (k is increase value in update). Tricky part is how to update ind2. Let's define a function relax(). relax(u) calculates ind2 value for node u. Note that for relax function to work all nodes in subtree of u must be calculated already. We will call relax function after calculating this nodes children. We will come to relax function later.

How to query: We can use pretty much same function as relax. We have to query find values for a l-r segment. We will keep an extra value in function, let's call it t. If this node covers segment a-b then t will keep maximum{suff_{l≤ k < a}}}. If this node doesn't intersect with l-r segment we will return worst values (for example for mx_suff value we will return -inf). Let's look what to do when this node is covered by l-r. If mx_suff value of this node's left child is greater or equal to t then ind2 value will be same. So if maximum{suff_{l≤ k < ind2}}+p_ind2) is lower or equal to k for this node answer is ind2, it is greater than k then we will go this nodes left child to calculate answer. If mx_suff value of this node's left child is lower than t value then (maximum{suff_{l≤ j < mid}}) will equal to t for each j. So we just have to rightmost j that p_j  ≤  k - t in subtree of this node. This can be calculated in O(logn) time. We didn't look at right child yet, so we will go to right child again with same t value. What to do when this node intersects with l-r and l-r doesn't cover it. We will go both children, first to left, after we will update t value for right child by mx_suff value returned from left child. We will lazy prop to push values.

Other condition: In node l we have to query between l and r, r is rightmost index that cost_r - 1 < k. Since cost values are monotonic this r can be found easily in O(logn).

Relax function can be calculated nearly same as query. But this will work in O(logn), since we just have to go exactly one child, since we don't interested in rightmost values.