Hello everyone
Editorial of all problems are not in English. This is translation of all problems in English. I hope everyone will like it
We were asked to find the expected value of meetings between the runners. How to do that? As the first step, expected value is lineal, so we can split the initial problems into the different ones: find the expected value of meetings between the fixed pair of runners. We will solve these problems. To do that we need to make some observations:
Let x be the distance between the two runners and they run face to face for infinite amount of time (probability of that obviously equals to 0.5·0.5 = 0.25). Then the first meeting will happen at time , the next one — , the next — and so on. Let us assume that every run ran for l time units. Then if two runners meet — they meet exactly two times. The probability of the meeting equals to 0.5, because in two cases they run in the same direction and in two cases in the different ones.
We will build our solution based on these two observations. As the first step let us represent t as t = k·l + p, where 0 ≤ p < l. Then each runner will run k full laps. What does that mean? Because we have pairs of runners, then in those k laps each pair will have 2k meetings with probability equals to 0.5. So, we need to add to the answer.
Now we need to take into account p seconds of running. Let us assume that the distance between two runners is x and they run towards each other. Then they will meet if , or x ≤ 2t. They will meet once more if , ir x ≤ 2t - l. They cannot meet more than twice, because p < l.
Let us fix one of the runners, then using binary search we can find all other runners at distance no more than x from the fixed one. Let us choose x as x = 2t, and then the number of runners at the distance no more than x stands for the number of runners which meet with the fixed one at least once. If x = 2t - l, we will find the number of runners which meet with the fixed one exactly two times. Multiplying these numbers by 0.25 — probability of the meeting, and add it to the answer.
The complexity of this solution is . We can reduce it using two pointers method.
We were asked to find the maximal number of words we can fit into the block of size r × c. Let's first solve such problem: what is the maximal number of consecutive words which can fit in a row of lenth c, if the first word has index i. We can solve it using binary search or moving the pointer. Now let us build a graph, where vertices are the words and there is a directional edge between i and j, if words from i to j - 1 fit in one row of length c, but words from i to j don't. The weight of the edge is j - i. The we have the following problem: we need to find the path of length k, which has the maximal weight. Easy to solve it with complexity saving weights of all the paths with lengthes equal to the powers of two, or in O(n) time using dfs.
The other problems competitors faced — that we were asked to print the whole text, not only the length.
We were asked to find the maximal number of arrays we can fit into the memory. A small observation first, let the answer be k, then one of the optimal solutions fits the k smallest arrays into the memory. We can assume that we have arrays of size 1 and we want to arrange the memory for the maximal arrays as possible. Then, if we have odd-sized chunks, then when placing an array of size 1 in such a region, we get a chunk of even size. On the other hand, if placed on a ground array the same size, the parity does not change and if the area is not to be taken by a single array of size 1, that in the end there is at least one free cell. Hence, it is advantageous to place the arrays of size 1 for odd sized memory locations. Let's do it while we can. There are three possible situations:
1 We are out of odd-sized chunks.
2 We are out of arrays of size 1.
3 We ran out and odd-sized chunks, and arrays of size 1.
Let's start with the first case. Suppose we were arrays of size 1, but no more odd-sized chunks. In the optimal solution beneficial to continue to place arrays of size 1. Thus, if we place them in the memory areas even size, we change the parity of the memory size, but as described above, it may lead to the fact that at the end of at least one cell at a free memory location. From this we can conclude that the size of the arrays disadvantageous place one by one at site. Advantageous to combine them into arrays of size 2 and placed together. Let's do it. After that, we divide all the numbers by 2 and arrive at the original task.
In the second case, if we divide all immediately available on the number of integer 2, and solve the original problem, the answer is we do not worsen.
The third case is similar to the second.
It should be noted that after the reduction of the problem to the same, we need to remember that it is always advantageous to place those arrays that have been collected from the greatest number of arrays.
The complexity of this solution is.
Participants are required to find the number of obtuse triangles in the vertex data that satisfy certain conditions. Just note that the author's solution has the complexity of O (n2), but has a number of optimizations, so that the solution is placed in the TL with a large margin.
Each obtuse triangle has exactly one obtuse angle. Because of the symmetry of the problem without loss of generality, we can fix the side and assume that an obtuse angle is adjacent to this side. Then, we need to calculate the answer for only one hand, and in the end multiply it by 3.
Since each side symmetric, we can consider only half the side, and then multiplied the answer by 2.
We introduce coordinates so that the apex of the triangle A has coordinates (0,0). Vertex B (0) and C (2,0). Then find the coordinates of each of the points on the sides, and write the cosine theorem. Obtain a certain ratio, which guarantees that the triangle is obtuse. One of its possible forms as follows: If 1 ≤ i, j, k ≤ n — number of points on the fixed sides, obtuse triangle if and only if: f (i, j, k) = 2i2 — i (n + 1 ) + 2j (n + 1) — ij — k (i + j) <0. Note that the increases, so we can use the method of moving the pointer to iterate k. Then simply iterate from i to m + 1, then m + j from 1 to as long as the upper limit for k does not exceed n — m + 1, and the results will be summarized.
Note that all the results you need to do in the type int, which significantly speeds up the decision.
Proposed to solve this problem greedily. We follow the following algorithm. Create for each segment and 2 marks Positionv MaximalPositionv.
Positionv — corresponds to the position of v in the desired permutation.
MaximalPositionv — is the maximum allowable position of v in the current month. moment.
Suppose we also have a counter count is initially equal to 0 and the set of vertices of untreated S. We will act according to the following algorithm.
Binary search looking for the minimum possible distance between the most remote connections sheep. For a fixed distance K check whether there is a permutation.
Sort all segments ascending ri.
Positioni = 0, 1 ≤ i ≤ n, MaximalPositioni = n, 1 ≤ i ≤ n, current = 1, count = 0.
Run count = count + 1, Positioncurrent = count, remove the current from S, if S - empty, the required permutation found.
Loop through all the segments that are connected with the current, and update MaximalPositionv = min (MaximalPositionv, Positioncurrent + K)
We build the set S (count, j) = {v | MaximalPositionv ≤ count + j}. If for all j ≥ K - count + 1, we have | S (count, j) | ≤ j then go to step 7, otherwise we conclude that the desired permutation does not exist.
We are looking for the minimum j such that | S (count, j) | = j. Choosing out the top with the smallest ri and take it as the new current, go to step 4.Please justify the time of the presented algorithm. We fix the distance K (all iterations will be fixed K).
Note that steps 4 through 7 in the worst case are performed exactly n times (each time the size of S is reduced to 1). Each of the steps can be implemented so that it runs in O (n). The most difficult step — a step 6. But note that we do not need to explicitly construct these sets, it is sufficient to know only their size. And we can do it in linear time, as there are simply considering such elements as MaximalPositionv = i. We denote this number by Ci — then the size of the set S (count, j) is equal to C1 + C2 + ... + Ccount + j, it is easy to calculate using the array of partial sums.
Now we justify the correctness of the algorithm. If the algorithm is set up the position for all the vertices, then it is obvious that it has the desired permutation. Suppose that the algorithm terminates its execution before we have placed all the items we show that there is no required permutation. There algorithm finished its execution, this means that a count (naymenshee consider this count), that there is j0, that | S (count, j0) |> j0 in this step. We show that | S (count, k) |> k. We prove this by contradiction. Suppose this is not the case. From the definition of count, we have | S (count — 1, j) | ≤ j for all j ≥ k — count + 2. Then, | S (count, j) | = | S (count — 1, j + 1) | — 1 ≤ j for all j ≤ k — 1. Thus, S (count, j) = S (count, k) for k ≤ j <n — count = | S (count, j) | = | S (count, k) | ≤ j. As a result, | S (count, n — count) | = n — count. Then | S (count, j) | ≤ j for all j, hence we have a contradiction. Hence, the algorithm preraschaet its work in step 6, | S (count, k) |> k. This means that there is at least k + 1 node that has not yet been assigned to a position after the vertex that was marked as count. Hence, one of the vertices S (count, k) must be at least a Position count + k + 1. But all vertices S (count, k) are connected to at least one vershinoy with Position ≤ count. Therefore, we conclude that there is no iskomomy reshuffle.
Comments (0)
