codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

397.md (8969B)


      1 Source: https://codeforces.com/blog/entry/10713
      2 
      3 ### [Div2-A](https://codeforces.com/contest/397/problem/A)
      4 
      5 Create an array *used* of 100 elements. i-th element for the segment (*i*, *i* + 1).
      6 
      7 For every student except Alexey set *used*[*i*]  =  *true* for each segment (*i*,  *i*  +  1) in the segment of that student. After that for each subsegment (*i*,  *i*  +  1) of Alexey's segment add 1 to result if *used*[*i*]  =  *false*.
      8 
      9 ### [Div2-B](https://codeforces.com/contest/397/problem/B)
     10 
     11 First of all, calculate how many *L*'s we can bring so that the result will not exceed *N*. It's ![](https://espresso.codeforces.com/3809fe7a17223dcae4c2c8b5e1f5a49567fe18f9.png).
     12 
     13 Now, if *R*·*K*  ≥  *N* we may increase any of *K* numbers by 1. At some moment sum will be equal to *N* becase sum of *K* *R*'s is greater than *N*. So answer in this case is `YES`.
     14 
     15 If *R*·*K*  <  *N*, we can't get *K* or less numbers because their sum is less than *N*. But we can't get more than *K* numbers too, because their sum is more than *N*. So answer is `NO`.
     16 
     17 Complexity: `O(1)` for every query. Overall complexity: O(t).
     18 
     19 ### [Div1-A](https://codeforces.com/contest/396/problem/A)/[Div2-C](https://codeforces.com/contest/397/problem/C)
     20 
     21 Let's factorize all *n* numbers into prime factors. Now we should solve the problem for every prime independently and multiply these answers. The number of ways to split *p**k* into *n* multipliers, where *p* is prime, is equal to *C*(*k*  +  *n*  -  1,  *n*  -  1) (it can be obtained using the method of stars and bars, you can read about it here, choose 'combinatorics'). So we have a solution that needs ![](https://espresso.codeforces.com/76b9bb9308c3d5fb103eee63dc8fe564f76298a0.png) time.
     22 
     23 ### [Div1-B](https://codeforces.com/contest/396/problem/B)/[Div2-D](https://codeforces.com/contest/397/problem/D)
     24 
     25 First of all, let's consider *n*  +  1  =  *p* is prime. Then we can prove by induction that the answer is ![](https://espresso.codeforces.com/aa26f4bbcff751ff69aa8b0c1330914b84c97968.png). Base for *p*  =  3 is obvious. If this equality holds for *p*, and *q* is the next prime, then answer for *q* is equal to answer for *p* plus *q*  -  *p* equal summands ![](https://espresso.codeforces.com/a6640311d508ebd16efdc02009a3195d224f3065.png), that is ![](https://espresso.codeforces.com/3d46c621bd9e9ea082f98fc1bb8f04fd321acb7f.png), that's we wanted to prove.
     26 
     27 Next using that the distance between two consecutive primes not exceeding 109 does not exceed 300, we can find the answer as a sum of the answer for the maximal prime not exceeding *n* and several equal summands ![](https://espresso.codeforces.com/a6640311d508ebd16efdc02009a3195d224f3065.png). We see that the denominator is a divisor of 2*pq*, which fits in `long long`.
     28 
     29 ### [Div1-C](https://codeforces.com/contest/396/problem/C)/[Div2-E](https://codeforces.com/contest/397/problem/E)
     30 
     31 We can write all vertices in the list in order of *dfs*, then the descendants of the vertex from a segment of this list. Let's count for every vertex its distance to the root *level*[*v*].
     32 
     33 Let's create two segment trees *st*1 and *st*2. If we are given a query of the first type, in *st*1 we add *x*  +  *level*[*v*]·*k* to the segment corresponding to the vertex *v*, in *st*2 we add *k* to the segment corresponding to the vertex *v*.
     34 
     35 If we are given a query of the second type, we write `st1.get(v) - st2.get(v) * level[v]`.
     36 
     37 The complexity is `O(qlogn)`.
     38 
     39 You can use any other data stucture that allows to add to the segment and to find a value of an arbitrary element.
     40 
     41 Also there exists a solution using Heavy-Light decomposition.
     42 
     43 ### [Div1-D](https://codeforces.com/contest/396/problem/D)
     44 
     45 Let's prove a useful fact: sum of number of invertions for all permutations of size *k* is equal to ![](https://espresso.codeforces.com/a53c7fcade4022e9125a6054a53f8a149767ac65.png). The prove is simple: let's change in permutation *p* for every *i* *p**i* to *k*  +  1  -  *p**i*. Then the sum of number of invertions of the first and the second permutations is ![](https://espresso.codeforces.com/5e746b3c3880cdf778e95df37e0455e334eff6bb.png), and our conversion of the permutation is a biection.
     46 
     47 Now we suppose that we are given a permutation of numbers from 0 to *n*  -  1.
     48 
     49 Let's go at *p* from left to right. What permutations are less than *p*?
     50 
     51 * Permutations having first number less than *p*0. If the first number is *a*  <  *p*0, than in every such permutation there are a inversions of form (first element, some other element). So in all permutations beginning with *a* there are *a*·(*n*  -  1)! inversions of this from. Moreover, there are inversions not including the first element, their sum is *sumAll*[*n*  -  1]. Then, counting sum for all *a* we have ![](https://espresso.codeforces.com/c68d69828a44f5ddb72afa8c25d989fa72cdb2a1.png) inversions.
     52 * Permutations beginning with *p*0. At first, we should count the number of inversions, beginning in *p*0. There are *cnt*·*p*0 of this form, where *cnt* is the number of permutations beginning with *p*0 and not exceeding *p*. Then we should count the inversions not beginning in the beginning. But it is the same problem! The only exception is that if *p*1  >  *p*0, there are *p*1  -  1 available numbers less than *p*1, but not *p*1. So we get a solution: go from left to right, keep already used numbers in Fenwick tree, and then solve the same problem, assuming that the first number is not *p**i* but *p**i* - (the number of used numbers less than *p**i*).
     53 
     54 The last we should do is to count the number of permutations not exceeding the suffix of *p* and beginning the same. It can be precomputed, if we go from right to left. In this case we should do the same as in the first part of solution, but consider that the minimal number is a number of already used numbers less than current.
     55 
     56 ### [Div1-E](https://codeforces.com/contest/396/problem/E)
     57 
     58 We will describe an algorithm and then understand why it works.
     59 
     60 For every prime we will maintain a list of intervals. At the first moment for every *p**i* we add in its list interval [0;*a**i*), other primes have an empty list.
     61 
     62 Then we go from big primes to small. Let's consider that current prime is *p*. If in its list there exists an interval [*x*;*y*), $x < k, y > k$, we divide it into two parts [*x*;*k*) and [*k*;*y*).
     63 
     64 Then for every interval [*x*;*y*), *x*  ≥  *k* (in fact, in this case *x*  =  *k*) we add to the answer for *p* *y*  -  *x*. For intervals, where *y*  ≤  *k*, we add to list of every prime divisor of *p*  -  1 invterval [*x*  +  1,  *y*  +  1). If *p*  -  1 has some prime if more than first power, we should add this segment several times.
     65 
     66 After that we should conduct a "union with displacement" operation for every prime which list was changed. If in one list there are 2 invervals [*x*,  *y*), [*z*,  *t*) so that *y*  ≤  *z*  >  *x*, we replace them with one interval [*x*,  *y*  +  *t*  -  *z*) (so we added *t*  -  *z* to the right border of the first interval). Then we go to next (lesser) *p*.
     67 
     68 Why does it works? If we take function φ one time, for every prime *p* which divides *n*, *n* is divided by *p* and multiplied by *p*  -  1 (or, the same, by all prime divisors *p*  -  1 in corresponding powers).
     69 
     70 Now we can observe that intervals in lists contains the numbers of iterations, when the number contains the corresponding prime number. Bigger primes do not affect smaller, so we can process them earlier. If after *i*-th iteration the number contains prime number *p*, after *i*  +  1-th iteration it contains prime divisors of *p*  -  1, and we add segments in accordance with this. The k-th iteration is the last, so the existence of the interval [*k*,  *x*) means that after *k*-th iteration we have (*x*  -  *k*)-th power of this prime. From this it is clear why we unite the intervals if that way.
     71 
     72 Why does it work fast?
     73 
     74 1. Because we precalculated the minimal prime divisor of each number up to *MAXPRIME* using linear Eratosthenes sieve. (Well, it's not necessary)
     75 2. Because for each prime there's no more than ![](https://espresso.codeforces.com/2a139b6ac25ec4b168df3ffe1cfab7644bbcef84.png) intervals, because for each [*a*,  *b*) range ![](https://espresso.codeforces.com/686e039e5b596d288441051c069eaa5669f0f2a2.png). Practically there is no more than 6 segments at once.
     76 
     77 Any questions about the editorial are welcome! Especially the English one :)
     78 
     79 This post was restored from google cache, and I have edited formula once again. If you notice some mistake, please send be a private message.