Task A. Div2.
It's easy to see that number x can appear in column i only once — in row x / i. For every column i, let's check that x divides i and x / i ≤ n. If all requirements are met, we'll update the answer.
The complexity is O(n)
Source
Task B. Div2.
Let's consider two cases: n > m and n ≤ m.
If n > m, let's look at prefix sums. By pigeonhole principle, there are two equals sums modulo m. Assume Slmodm = Srmodm. Then the sum on segment [l + 1, r] equals zero modulo m, that means the answer is definitely "YES".
If n ≤ m, we'll solve this task using dynamic programming in O(m2) time. Assume can[i][r] means if we can achieve the sum equal to r modulo m using only first i - 1 items. The updates in this dynamic programming are obvious: we either take number ai and go to the state can[i + 1][(r + ai) mod m] or not, then we'll get to the state can[i + 1][r].
The complexity is O(m2).
Source
Task A. Div1.
If Petya didn't ask pk, where p is prime and k ≥ 1, he would not be able to distinguish pk - 1 and pk.
That means, he should ask all the numbers pk. It's easy to prove that this sequence actually guesses all the numbers from 1 to n
The complexity is O(N1.5) or O(NloglogN) depending on primality test.
Source
Task B. Div1.
Let's look at the answer. It's easy to notice, that centers of that tree must turn into centers after applying the permutation. That means, permutation must have cycle with length 1 or 2 since there're at most two centers.
If permutation has cycle with length 1, we can connect all the other vertices to it.
For example, let's look at the permutation (4, 2, 1, 3). 2 is a cycle with length 2, so let's connect all the other vertices to it. The resulting tree edges would be (1, 2), (2, 3), (2, 4).
If answer has two centers, let's remove the edge between them. The tree will split into two connected parts. It's easy to see that they will turn into each other after applying permutation. That means, all cycles should be even.
It's easy to come up with answer with these restrictions. Let's connect vertices from the cycles with length 2. Then, let's connect vertices with odd position in cycles to first of these and vetices with even cycles to second one.
For example, let's consider permutation (6, 5, 4, 3, 1, 2). There are two cycles: (3, 4) и (1, 6, 2, 5). We add edge (3, 4), all other vertices we connect to these two, obtaining edges (1, 3), (6, 4), (2, 3), (5, 4).
The complexity is O(N).
Source
Task C. Div1.
Let's split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let's number them from left to right. We're going to pass through points rectangle by rectangle. Inside the rectangle we're going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it's odd.
Let's calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we're passing 1000 rectangles from 0 to 106, 109 in total. By x-coordinate we're spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.
The complexity is O(n * log(n))
Source
Task D. Div1.
Let's optimize the first solution that comes to mind: O(m * dmax), let's calculate can[t][v] — can we get to the vertice v, while passing exactly t edges.
Now, it's easy to find out that the set of edges we are able to go through changed only m times. Let's sort these edges in increasing order of di, that means for each i di ≤ di + 1. Let's calculate can[t][v] only for t = di. We can calculate can[di + 1] using can[di] by raising the adjacency matrix to the di + 1 - di power and applying it to can[di].
Next step is to fix an edge with maximal di on our shortest path, let it be i. We know all the vertices we can be at moment di, so we need to calculate the shortest path to n - 1 using edges we can go through. We can even use Floyd algorithm to calculate that.
The complexity of this solution is O(m * n3 * log(dmax)) and it's not enough.
Next observation is that adjacency matrix contains only zeroes or ones, so we can multiply these matrixes using bitsets in O(n3 / 32).
This makes complexity O(m * n3 * log(dmax) / 32), which gets accepted.
Source
Task E. Div1.
Let's solve an easier task first: independent of bipartivity, the color of edge changes.
Then we could write a solution, which is pretty similar to solution of Dynamic Connectivity Offline task in O(nlog2n).
Let's consider only cases, where edges are not being deleted from the color graph. Then, we could use DSU with storing parity of the way to the parent along with parent. Now we can find parity of the path to the root by jumping through parents and xoring the parities. Also, we can connect two components by accurately calculating the parity of the path from one root to another.
Now edges are being deleted. For each edge and each color we know the segments of requests, when this edge will be in the graph of specified color. Let's build a segment tree on requests, in each vertex of the tree we store list of edges which exist on the subsegment. Every segment will be split into log parts, so, totally there would be n * log small parts.
Now we can dfs this segment tree with DSU. We get inside the vertex, apply all the requests inside it, go through the children and revert DSU to initial state. We also answer requests in leafs of the segment tree.
Let's return to initial task. We can't use this technique, because we don't know the exact segments of edge existence.
Instead, let's do following. Initially we add each edge right until the first appearance of this edge in requests. Now, when we're in some leaf, we found out which color this edge would be right until the next appearance of this edge. So, let's update this edge on that segment.
For each leaf we're going to make an update at most once, so the complexity is O(nlog2n).
Source
If anything is unclear or bad-written, ask any questions.