542A - Place Your Ad Here
Let's fix the TV channel window and look for a commerical having the largest intersection with it. There are four types of commercials: lying inside the window, overlapping the window and partially intersecting the window from the left and from the right.
It's easy to determine if there is overlapping commercial: it's enough to sort commercials in increasing order of the left end and then while iterating over them from left to right, keep the minimum value of a right end of a commercial. If when we pass the window j and see that current value of the maximum right end is no less than bj then there exists a commercial overlapping our window and the value is equal to the (ri - li)·ci.
Among all commercials that lie inside our window we need the longest one. It can be done by similar but a bit harder manner. Let's use sweepline method. While passing through the end of the commercial ri, let's assign in some data structure (like segment tree) the value ri - li in point li. While passing through the end of a window, let's calculate answer for it as a maximum on segment [aj, bj]. By doing this, we consider all commercials inside the window.
We can process partially intersecting commercials in the similar way. While passing the right end of the commercial ri let's put the value ri in the point li in our data structure. While passing through the right end of a window bj let's calculate the answer for it as a maximum on the segment [aj, bj] minus aj.
Among all answers for all commercials we need to choose the largest one. So we have the solution in 
.
Challenge. What if there are weights not only on windows, but on commercials also, and those weights are multiplied with the intersection length? You can solve this task in 
and get a virtual medal!
542B - Duck Hunt
First of all, let's say that ducks stay still and the one that moves is the hunter. Let's define the value F[x][s] as the minimum number of ducks among having the right end no further than x, that we can't shot if the last shot was in the point s. In particular, the value F[x][s] includes all ducks located inside the segment [s + 1, x]. Values F[x][s] for s > x let's consider as undefined.
Let's look on F[x] as on a function of s. This function is defined on all s from 0 to x inclusive. The key idea is in investigating how F[x + 1][·] differs from F[x][·].
Let's first suppose that in point x + 1 there is no end of the duck. Then in definition of F[x + 1][·] we consider the same set of the ducks as for the definition f F[x][·]. That means that all values F[x][s] for s ≤ x are the same for F[x + 1]. Let's understand what happens with F[x + 1][x + 1]. It's easy to see that the shot in point x + 1 can't kill any of the ducks that end no further than x + 1 (since we just supposed that there are no ducks ending in exactly x + 1). So, F[x + 1][x + 1] = min F[x + 1][0... x + 1 - r] = min F[x][0... x + 1 - r].
Now let's suppose that in point x + 1 the duck [l, x + 1] ends. In this case we can say that all values of F[x + 1][0... l - 1] should be increased by 1 (since at the moment of shot in point s < l the duck [l, x + 1] can't be killed yet). From the other hand, all values F[x + 1][l... x + 1] remain the same since the last shot kills the newly added duck.
Now let's understand how to implement all this stuff. Function F[x][·] is piecewise constant, so it can be stored in a Cartesian tree as a sequence of pairs (beginning of segment, value on segment). Such storage allows us to easily add 1 on prefix and take minimum on prefix of a function.
Now let's think that F[x][·] is defined on all posistive values but the values F[x][s] for s > x do not satisfy the definition of F[x][s] above. In other words, let's just suppose that the lats segment in structure F[x] is infinite in right direction.
Let's sweep with the variable x. The function F[x + 1][·] changes in comparsion to F[x][·] very rarely For example, the value F[x + 1][x + 1] is almost always the same as F[x][x + 1] (that is equal to F[x][x] as said above). Indeed, if we suppose that there is no duck ending in x + 1 then F[x][x] = min(F[x][0... x - r]) and F[x + 1][x + 1] = min(F[x + 1][0... x + 1 - r]) = min(F[x][0... x + 1 - r]) ≤ min(F[x][0... x - r]). So, there is an interesting event only if value F[x][x - r + 1] is smaller than the whole prefix before it. On the other hand, the value min(F[x][0... x - r]) can't increase more than n times by 1 (each time when we pass through the right end of the duck) and so, it also can't decrease more then n times (since it is a non-negative value).
So, the events "we passed through the right end of the duck" and "we should non-trivially calculate F[x][x]" are in total linear. Each of them can be processed in O(1) operation with Cartesian tree, that gives as totally an solution. Whooray!
542C - Idempotent functions
In order to solve this task it's good to understand how does the graph corresponding the function from {1, ..., n} to itself looks. Let's consider a graph on vertices 1, ..., n with edges from vertex i to the vertex f(i). Such graph always looks like a set of cycles with several trees leading to that cycles. How should the graph look like for function to be the idempotent? It's easy to see that in such graph all cycles should be of length 1 and all vertex that are not cycles of length 1 (i. e. all not fixed points) should immediatly lead to some fixed point.
So, we should satisfy two conditions. First, all cycles should become of length 1 — in order to do that k should be divisible by lcm(c1, c2, ..., cm) where ci are the lengths of all cycles. Second, all vertices not lying on cycles should become leading to the vertices lying on cycles. In other words, k should be no less than the distance from any vertex x to the cycle it goes into (or, that the same, the length of pre-period in the sequence f(x), f(f(x)), f(f(f(x))), ...).
So, are task is about finding the smallest number k divisible by A that is no less than B, it is not hard at all.
Challenge. What is the maximum possible answer for this task? (Answer: first second)
First step is to understand the properties of a Joker function. It's important property is that it is multiplicative: J(ab) = J(a)J(b) for (a, b) = 1, so we can write the value of function knowing the factorization of an argument: J(p1k1p2k2... pmkm) = J(p1k1)J(p2k2)... J(pmkm) = (p1k1 + 1)(p2k2 + 1)... (pmkm + 1). Let's use this knowledge in order to solve the task with dynamic programming.
Let's denote as P the set of prime p such that the multiple including it may appear in A = J(x). There are not that many such primes: each divisor d of number A can correspond no more than one such prime, namely, the one whose power the number d - 1 is (if it is a prime power at all). Let's calculate the set P and also remember for each prime number p in it in which powers k the value (pk + 1) divides A.
Now we can calculate value D[p][d] that is equal to the number of ways to get a divisor d of a number A as a product of brackets of first p primes in set P. Such value can be caluclated by using dynamic programming in time 
where 
is the number of divisors of A (as it was shown above that 
). So, overall complexity of the solution is 
.
Challenge. How the behaves when A increases? What is the maximum values of over all A ≤ 1012? (The answer: 
. Nice estimate that is not an exact asymptotic, though, is that 
)
Challenge. What is the maximum answer in this task? If you are able to create a test with answer larger than million, a great respect from me!
542E - Playing on Graph
First, if the original graph isn't bipartite then the answer is (-1). Indeed, any odd cycle, while being contracted by the pair of vertices, always produces an odd cycle of smaller size, so at some point we will get a triangle that blocks us from doing anything.
From the other way, each bipartite component can be contracted in order to get a chain whose length is a diameter of the component. Suppose that the pair of vertices (a, b) is a diamater of some connected component. Then, by contracting all vertices located on the same distance from a we can achieve the chain we want.
The last step is that the answer fror the original graph is the sum of the answers for all the connected components since we can attach all of them together. So, the answer is the sum of diameters of all connected components if all of them are bipartite, otherwise answer is -1. Solution has the complexity O(E + VE) (The first summand is checking for being bipartite, the second one is calculation diameters by running BFS from each vertex).
542F - Quest
This task can be solved in lot of ways. The most straightforward is DP. The task can be seen in the following way. We want some set of vertices as leaves and for each potential leaf we know the upper bound for its depth and its cost.
Let's sweep over the tree from down to up. Let's calculate the value D[h][c] that is the maximum possible cost that we can achieve if we stay on the level h and have c vertices on it. For transition let's fix how many leaves of the deepness exactly h we will take (it's easy to see that among them we should task several greatest). Suppose we will take k of them. Then from this state we can move to D[h - 1][⌈(c + k) / 2⌉]. The answer will be located in D[0][1] because when we are on the level 0 we should have the only vertex that is the root of the tree.
The complexity of such solution is O(n2T).
Challenge Improve the solution above to 
and then to 
About challange of problem A.
There are two cases.
We will choose two intervals [L1, R1], [L2, R2] where L1 ≤ L2 ≤ R2 ≤ R1. Lets find maximum value of this : (R2 - L2)C1C2, where C1, C2 are coefficients. To handle this case just use a segment tree which stores (R2 - L2)C2's and use same sweep algorithm. This part is O(NlogN).
This case is much more tricky. Again we will choose two intervals [L1, R1] and [L2, R2] where L1 ≤ L2 ≤ R1 ≤ R2. Then we will find the maximum value of this : (R1 - L2)C1C2. Imagine a 2D range tree that every node stores a segment tree and every node in segment tree stores a convex hull trick structure.:). We will insert lines y = mx + n where m = C1 and n = C1R1 to point (L1, R1) into the range tree. Building 2D range tree will be O(N(logN)2) and each query will be O((logN)2)(if we use two pointers technique in each convex hull trick structure)
Yes, exactly. Cool!
I'm pretty sure I've seen problem C elsewhere before.
From solution of B, " In particular, the value F[x][s] includes all ducks located inside the segment [x + 1, s]. " I think you meant [s+1, x], am I right?
Yes, that was a mistype. Thanks.
Awesome problems! I liked the solution to E very much! Can anyone recommend some similar problems?
"Let's denote as P the set of prime p such that the multiple including it may appear in A = J(x). There are not that many such primes: each divisor d of number A can correspond no more than one such prime, namely, the one whose power the number d - 1 is (if it is a prime power at all). "
How to calculate this set P (in problem D)? Doesn't it take lots of time to check if d-1 is a power of a prime? And this has to be done for all divisors d of A..
About checking probability : Miller-Rabin algorithm with T tests runs in
(assuming all arithmetic operations take O(1), which is true since A ≤ 1012) and makes an error with probability less than 4 - T. If T = 13 probability of error is basically non-existent.
So to check whether d - 1 = pk, where p is prime and
, you can iterate over possible values o k (there is 
of them), calculate 
somehow (in doubles, for example), check whether it is integer and prime.
How do we check whether it is prime? We just precalculate all primes up to 106. If integer we are asked about is greater than 106, we run Miller-Rabin test else we return precalculated answer.
For any d we will run Miller-Rabin test only once: if k ≥ 2 then
, so total time we need is about 
if we use fast exponentiation for integers.
It is not necessary to use Miller-Rabin test. It's enough to just run normal factorization algo. It's pretty obvious that it can work efficiently since it almost impossible to create test where all divisors are pk + 1, but one can even prove an upper bound for this algo that shows that it works fast.
It works in
. Divide divisors in two groups: those who are small than 
and those who are larger than 
. Then you can estimate this sum as 
.
First
summands are 
totally.
Last
summands can be rewritten as 
. It is about a billion, but if you substitute better estimation for 
instead just 
in last sum, then you'll see that it is even smaller: 
.
Could someone explain why: "Indeed, if we suppose that there is no duck ending in x + 1 then F[x][x] = min(F[x][0... x - r])" is true? Isn't this only the case if there is no duck ending at x?
EDIT: This is for problem B.