542.md (12216B)
1 Source: https://codeforces.com/blog/entry/17697 2 3 ## [542A - Place Your Ad Here](/contest/542/problem/A "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 4 5 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. 6 7 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 *b**j* then there exists a commercial overlapping our window and the value is equal to the (*r**i* - *l**i*)·*c**i*. 8 9 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 *r**i*, let's assign in some data structure (like segment tree) the value *r**i* - *l**i* in point *l**i*. While passing through the end of a window, let's calculate answer for it as a maximum on segment [*a**j*, *b**j*]. By doing this, we consider all commercials inside the window. 10 11 We can process partially intersecting commercials in the similar way. While passing the right end of the commercial *r**i* let's put the value *r**i* in the point *l**i* in our data structure. While passing through the right end of a window *b**j* let's calculate the answer for it as a maximum on the segment [*a**j*, *b**j*] minus *a**j*. 12 13 Among all answers for all commercials we need to choose the largest one. So we have the solution in . 14 15 **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! 16 17 ## [542B - Duck Hunt](/contest/542/problem/B "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 18 19 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. 20 21 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*][·]. 22 23 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*]. 24 25 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. 26 27 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. 28 29 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. 30 31 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). 32 33 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! 34 35 ## [542C - Idempotent functions](/contest/542/problem/C "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 36 37 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. 38 39 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*(*c*1, *c*2, ..., *c**m*) where *c**i* 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*))), ...). 40 41 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. 42 43 **Challenge**. What is the maximum possible answer for this task? (Answer: [first](http://oeis.org/A000793) [second](http://oeis.org/A000793/b000793.txt)) 44 45 [542D - Superhero's Job](/contest/542/problem/D "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 46 47 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*(*p*1*k*1*p*2*k*2... *p**m**k**m*) = *J*(*p*1*k*1)*J*(*p*2*k*2)... *J*(*p**m**k**m*) = (*p*1*k*1 + 1)(*p*2*k*2 + 1)... (*p**m**k**m* + 1). Let's use this knowledge in order to solve the task with dynamic programming. 48 49 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 (*p**k* + 1) divides *A*. 50 51 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 . 52 53 **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 ) 54 55 **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! 56 57 ## [542E - Playing on Graph](/contest/542/problem/E "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 58 59 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. 60 61 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. 62 63 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). 64 65 ## [542F - Quest](/contest/542/problem/F "VK Cup 2015 - Round 3 (unofficial online mirror, Div. 1 only)") 66 67 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. 68 69 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. 70 71 The complexity of such solution is *O*(*n*2*T*). 72 73 **Challenge** Improve the solution above to  and then to 