315.md (3512B)
1 Source: https://codeforces.com/blog/entry/7905 2 3 [315A - Sereja and Bottles](/contest/315/problem/A "Codeforces Round 187 (Div. 2)") 4 Just check for each bottle, can I open it with another. In this task can pass absolutely any solutions. 5 6 [315B - Sereja and Array](/contest/315/problem/B "Codeforces Round 187 (Div. 2)") 7 We will support all of the elements in the array, but also we will supprt additionally variable add: how much to add to all the elements. Then to add some value to every element we simply increase the add. In the derivation we deduce the value of the array element + add. When you update the item we put to a value, value that you need to put minus the current value of add. 8 9 [314A - Sereja and Contest](/contest/314/problem/A "Codeforces Round 187 (Div. 1)") 10 Note that if we remove some of the participants, we never remove the participants with lower numbers as theirs amount will only increase. So just consider the sequence of all the participants, and if the participant does not fit we delete him. 11 12 [314B - Sereja and Periods](/contest/314/problem/B "Codeforces Round 187 (Div. 1)") 13 It is clear that we can use greedy algorithm to look for the number of occurrences of the 2nd string in the first string, but it works too slow. To speed up the process, you can look at the first line of the string that specifies the second period. And the answer is divided into how many string you need to set the second string. Next, we consider our greedy algorithm. We are going by the first string, till we find the first character of the second string, then the second, third and so on until the last, then again find the first, second, and so the cycle. It is clear that if we stand in the same twice in a state in which the positions in the first string corresponds to one character string that determines the period and the position of the second string are the same, then we obtain the period. When we find this period, we can just repeat it as many times as possible. 14 15 To better understand, I advise you to read any accepted solution. 16 17 [314C - Sereja and Subsequences](/contest/314/problem/C "Codeforces Round 187 (Div. 1)") 18 It is clear that we need to calculate the sum of the products of elements of all the different non-decreasing subsequences of given sequence. Let's go through the sequence from left to right and maintain the array q[i]: what means the sum of all relevant sub-sequences, such that their last element is equal to i. Clearly, if the next number is x, then you need to put q[x] = sum (q[1] + q[2] + ... + q[x]) * x + x. The answer to the problem is the sum of q[i]. To find all the amounts you can use Fenwick tree. 19 20 [314D - Sereja and Straight Lines](/contest/314/problem/D "Codeforces Round 187 (Div. 1)") 21 Roll all at 45 degrees using the transformation: (x, y) -> (x ', y'): x '= x + y, y' = x-y. Next you need to place two lines parallel to the coordinate axes. Sort the points by the first coordinate. Next, we use a binary search for the answer. May we have fixed a number, you now need to check whether it is enough or not. Note that now we need to put two strips of width 2 * fixed amount that they would have to cover all the points. Suppose that some point should be close to the left side of the vertical strip, then for all points that do not belong to the strip we find the minimum and maximum second coordinate. If the difference between the found coordinates no more then 2 * fixed quantity, the strip can be placed, otherwise — no. 22 23 soon...