It is needed just to implement actions described in statement. You had to read data and to calculate number of members of team, which were sure about the solution, for every task. If this number is greater than one, the answer must be increased by one.
Let's see, what will be the last number of array after i iterations. After the first iteration it will be an - 1–an (and total number of elements will be decreased by one). After the second iteration the last number will be an - 2–an - 1 + an. It is not hard to see, that after n - 1 iterations remain a1–a2 + a3–a4 + ... + ( - 1)n + 1·an. In a such way, our task is to put numbers from 1 to l in array so, that sum of numbers in odd positions minus sum of numbers in even positions will equal to given d. This means sum of numbers in odd positions must be equal . But the minimal sum can be , and the maximal — .
Because of this we should choose a2·k so, that s fits the boundaries. Constrains allow to do it in a such manner. Firstly, put ones on the even positions. If s > maxv after that, the answer is - 1. Otherwise, let's increase each a2·k by one until s = minv. If we put l in all even positions and s < minv, than answer is - 1 too. After we put numbers on even positions, let's write 1 in all odd positions, and while sum of this elements is less than s increase each one by fitting value.
One of the main observations, needed to solve this problem, is that the second number in answer always coincides with someone aj. Let's see why it is true. Suppose, the second number of the answer is aj + d for someone j and aj + d ≠ ai for all i. This means, we increased some numbers, which is less than aj, so that they became equal to aj, and then all this numbers and some numbers, which is equal to aj, we increased to aj + d. But if we didn't increase all this numbers to aj + d and remain they equal to aj, we'd perform less operations and the answer would be better.
Due to this fact we can solve problem in a such manner. Sort array in non-decreasing order. Iterate over ai and calculate, what is the maximal number of ai we can obtain. For maximizing first number of answer, we must increase some lesser numbers to ai and perform not greater than k operations. It is obvious that firstly we should increase such aj that ai–aj is minimal. So, if we can solve problem in O(n2), we would iterate j from i to 0 and increase aj to ai, while we could. But the solution must be faster, and we will use binary search. We will brute the number of numbers, which we must do equal to ai. Suppose we fix cnt this value. Now we have to check if we can do cnt numbers equal to ai by not greater than k operations. For doing this, let’s calculate . If this value not greater than k, we can do it. For calculating sum quickly, we can save prefix sums and than si - cnt + 1, i = si–si–cnt. Finally we solved this problem in O(n·logn).
The main subtask of this problem is to check whether we can observe the center of face of parallelepiped from point p = (x, y, z). Let’s see the case, when the face belongs to plane z = z1. For performing all calculations in integer numbers, multiply all coordinates x, y, z, x1, y1, z1 by 2. Take the point and normal to plane, containing the fixed face, which is directed out of interior of parallelepiped, that is . Also take vector . If undirected angle between this vectors is less than 90 degrees, we can observe a from p. For checking this we can use scalar product. If scalar product of and is strictly greater than zero, than that angle is fitting.
In this problem you should find the number of simple paths between some pair of vertices in vertex cactus. If you learn the structure of these graphs, it is not hard to see, that if we’ll squeeze each cycle in one vertex, we get a tree. So let’s squeeze all cycles in source graph and get this tree. Also every vertex of this tree we’ll mark, if it is squeezed cycle (let’s call this vertices 1-vertices) or single vertex in source graph (this vertices we’ll call 0-vertices).
Then, we’ll do the following to find the number of paths between vertices a and b in source graph. Suppose c is a vertex, corresponding to a in obtained tree (it can be a single vertex or a vertex, corresponding to a squeezed cycle with a), and d is a vertex, corresponding to b. Let’s denote deg is the number of 1-vertices in path from c to d in tree. Than it is easy to understand, that the answer for query is , because every cycle (1-vertex) increase the number of possible ways twice (you can go from one vertex to other by two ways in cycle).
It means that we need to count the number of 1-vertex on the path from one vertex to other in tree quickly to answer a query. We can do it in a following way. Hang our tree for one vertex, which we’ll call a root. Denote for every vertex cntv is the number of 1-vertex on the way to the root (including root and vertex itself). Suppose we want to find the number of 1-vertex on the path from a to b. Denote c is the least common ancestor of vertices a and b. Than number of 1-vertex on the way from a to b is equal to cnta + cntb–2·cntc, if c is 0-vertex and cnta + cntb–2·cntc + 1, if c is 1-vertex. The least common ancestor can be found by standard method — binary method recovery. Finally we have O(m + k·logn) solution.