Hello everyone,

I'm trying to make a graph using matplotlib.pyplot and subprocess, but I get the following error:

Traceback (most recent call last):
    File "subprocess.py", line 2, in <module>
        import matplotlib.pyplot as plt
    File "/usr/lib/pymodules/python2.7/matplotlib/__init__.py", line 105, in <module>
        import os, re, shutil, subprocess, sys, warnings
    File "/home/igor/Documentos/subprocess.py", line 2, in <module>
        import matplotlib.pyplot as plt
    File "/usr/lib/pymodules/python2.7/matplotlib/pyplot.py", line 20, in <module>
        from matplotlib import _pylab_helpers, interactive
ImportError: cannot import name interactive

Error in sys.excepthook:

Traceback (most recent call last):
    File "/usr/lib/python2.7/dist-packages/apport_python_hook.py", line 66, in apport_excepthook
        from apport.fileutils import likely_packaged, get_recent_crashes
    File "/usr/lib/python2.7/dist-packages/apport/__init__.py", line 1, in <module>
        from apport.report import Report
    File "/usr/lib/python2.7/dist-packages/apport/report.py", line 12, in <module>
        import subprocess, tempfile, os.path, urllib, re, pwd, grp, os
    File "/home/igor/Documentos/subprocess.py", line 2, in <module>
        import matplotlib.pyplot as plt
    File "/usr/lib/pymodules/python2.7/matplotlib/pyplot.py", line 20, in <module>
        from matplotlib import _pylab_helpers, interactive
ImportError: cannot import name _pylab_helpers

If I try to do a graph not using subprocess (just plotting 2 arrays as axes), I don't get this problem.

Can someone help me?

Hi everyone,

This problem of spoj is same as this problem of Codeforces.

I have submitted same code on both [In codeforces & In spoj this code] but I am getting AC on CF and WA on spoj.

Can anyone help me? Any help will be well appreciated.

Hi everyone,

Many users were saying that they are not able to connect with editorial & asking to publish it on CF blog. So I am publishing it at CF blog. I hope everyone will like it.

Hello everyone

Editorial of all problems are not in English. This is translation of all problems in English. I hope everyone will like it

A. MORNING RUN

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.

B.Context Advertising

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.

C.Memory for Arrays

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.

D.Tennis Rackets

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.

E.Sheep

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.

296A — Yaroslav and Permutations

Note that after applying the operations of the exchange, we can get any permutation of numbers. Not difficult to understand that the answer is "YES", if you can place a single number that it would not stand in the neighboring cells. Thus, if a some number is meeted C times, it must fulfill the condition C <= (n +1) / 2. 296B — Yaroslav and Two Strings We solve the inverse problem: count the number of ways to make comparable pair. To start count the number of ways to make the first line of less than equal to the second. This number equals the number of ways to do this for each item individually as they are position independent. Let's count the same amount, but when the second line-less equal to the first. And similarly to count the number of ways to make two lines equal. For each character values ​​can be considered as a simple cycle. Now we take the value of 10 to the number of question marks in the input file and subtract the answer to the inverse problem, it will be the answer. 295A — Greg and Array In order to add the value of d in the interval [x, y] is sufficient to have an array of values ​​of b and put b [x] + = d b [y +1] — = d Next in a single pass through the array of easily reduced the numbers. We apply this method twice: first for the query, and then operations (knowing how much time we will fulfill it.) 295B — Greg and Graph

To solve the problem, we must thoroughly understand the principle of the Floyd algorithm. A general view of the Floyd algorithm: for (k = 1; k <= n; k + +) for (i = 1; i <= n; i + +) for (j = 1; j <= n; j + +) a [i] [j] = min (a [i] [j], a [i] [k] + a [k] [j]); That is, at each step, we try to flow the way across the top of K. We will not remove the top, and add (going from the end). At each step, we will try to flow the way between all the nodes through the new. Thus we get a solution that works in cubic time. 295C — Greg and Friends

Note that at each step we are interested in only the position of the boat (number of banks) and the number of people 50 and 100 weight on each shore. With that number of people on one side is completely determined by the other. To find the minimum number of crossings will be used wave algorithm based on this condition. To find the number of ways to add just the sum of all transitions in the state transition will move all the way from one state to another by multiplying the number of ways to choose the people who need to move from one state to another. 295D — Greg and Caves

We use the dynamic programming: dp [i] [j] — how many ways there are to construct a figure that the line will be exactly i j columns of black cells are occupied, and everything in between. In this case, the shape should not decrease (in other words, we take only the upper part of the figure). How to make the transition? Note that dp [i] [j] = 1 + dp [i-1] [2] * (j-1 2) + ... + Dp [i-1] [l] * (j-l +1) + ... + Dp [i-1] [j]. We rewrite it: dp [i] [j] = 1 + dp [i-1] [2] * j + ... + Dp [i-1] [l] * j + ... + Dp [i-1] [j] * j — dp [i-1] [2] * 1 — dp [i-1] [3] * 2 — ... — Dp [i-1] [j] * (j-1). Clearly, if the make partial sum, the data value is considered as very simple. How to calculate the full response: we will sort out the maximum number of suitable t (indicated in the condition). Now, the only difference is that the following line should contain strictly fewer columns. That is, we have a similar transition, with -1 term. Also note that fixing the "foundation" we must multiply the number of ways for a number of ways to place it on the plane, that is the basis of width j, we can put (m-j +1) ways. 295E — Yaroslav and Points

Learn how to solve the problem of finding the sum of the distances between points. If paint, what happens when you add one point, then we get the formula: x_i * (2 * in) Where x_i — sorted coordinates, and n is the total number of points. Let us learn to know the answers to the two segments of points to know the answer to their association. It is clear that for the calculation of such information need only add two response and adding the sum of the first coordinate set multiplied by a certain number, and and add the sum of the second set of coordinates multiplied by some, perhaps another number. Thus knowing the answers to some segments of the overall response. We will use the root decomposition or Cartesian tree for the storage of such segments. It is not difficult to understand that the insertion and deletion is done quickly enough for these structures. For example, for the root decomposition can be every time just cut and paste the desired point in the intervals, and if the set was contain long stretches or many segments, then simply reconstruct it again. Asymptotics of the solution does not change.