365.md (7871B)
1 Source: https://codeforces.com/blog/entry/9657 2 3 That's a part of final editorial. I'm sorry for delay. Please, report me about mistakes and unclear moments in solutions and in my english. 4 5 **A div2** 6 7 Task was to find the least digit, that is not contained in the given number and compare with given *k*. 8 9 **B div2** 10 11 Good sequence may contain only zeroes or contain some positive number. In the second case such a sequence is not longer than sequence {0, 1, 1, 2, 3, 5, 8, ..., *x*, *y*} where *y* > 109 and *x* ≤ 109. That's possible to find it using dummy algorithm. In the first case you may use binary search of two pointers. 12 13 **A div1** 14 15 Let's notice that sum in the rectangle (*x*1, *y*1, *x*2, *y*2) is *sum*(*x*1, *x*2)·*sum*(*y*1, *y*2). Where *sum*(*l*, *r*) = *s**l* + *s**l* + 1 + ... + *s**r*. Then, we have to calc *sum*(*l*, *r*) for every pair (*l*, *r*) and count how many segments give us sum *x* for any possible x (0 ≤ *x* ≤ 9·|*s*|). In the end we should enumerate sum on segemnt [*x*1, *x*2] and find . There is corner case *a* = 0. 16 17 **B div1** 18 19 We may assume that John may exchange any subset of his items *x* to any other subset *y*, such as *s*(*x*) + *d* ≥ *s*(*y*) (it does not matter if *x* intersects *y*). We can find all possible sums in subset of elements of the given set of items using standard dp (knapsack problem). John should always exchange all his current set of items to another, because if he had exchanged some subset of *x* (current set) *z* to *y*, we can say that he had exchanged *x* to . So, we have to find shortest sequence of sets *a*, such as *s*(*a**i* + 1) - *d* ≥ *s*(*a**i*) for any possible *i* and *a*0 = {}. This subtask could be solved using following greedy algorithm. *a**i*, *i* > 0 is maximal correct sum such as *a**i* ≤ *a**i* - 1 + *d*. Consider optimal answer *c* and our answer *a*. Let *k* is the first position where *a**k* ≠ *c**k* obiviously *a**k* > *c**k* (because *a**k* selected as maximal as possible). Then consider *q* such as *q**i* = *c**i* for *i* ≠ *k* and *q**k* = *a**k*. *q* is either optimal. Applying similar operations we will obtain *a*. So, *a* is optimal. 20 21 **C div1** 22 23 We expected many unproved, but tested solutions. I think that careful prove of my solution with pen and paper is very difficult. So I will use some statistic-based facts. 24 25 1. Consider the set of divisors of number *k*. One can check that it's beautiful set. 26 2. If factorisation of *k* has the form  where α*i* ≥ 3 and *p**i* is distinct primes, set of divisors of *k* which is less than  is also beautiful. 27 3. How to prove item 2? Consider set *A* of pairs of divisors of *k* (*a**i*, *b**i*) such as *a**i*·*b**i* = *k* and *a**i* < *b**i*. Obiviously (if *k* is not complete square) any divisor will be contained only in one pair. It's easy too see that . Consider some element of factorisation of *k* *p*α such as  and it is not true that . Let *f*(*x*) is maximal number *s* such as . *f*(*a**i*) + *f*(*b**i*) = α. For every *q* such as  numbers *q*, *q*·*p*, ..., *q*·*p*α will be divisors of *k*. That implies that  where *d* is number of divisors of . So in  pairs both numbers are divisible by *p*. So set {*a*0, ..., *a*|*A*|} is beautiful. 28 4. But there are some pairs with *f*(*a**i*) = α.  is equivalent approval. 29 5. It's always possible to find such *k* as number of it's divisors is bigger than 2·*w* where *w* is number of elements in required set. You may write following dp to find it. 30 6. *dp*[*i*][*j*] is minimal *k* which is constructed of first *i* primes ans has *j* divisors.  31 7. About 10 primes is enough to cover all *k*. 32 8. Now we can construct beautiful sets with more than *k* elements. 33 9. Using item 4 we will understand that constructed answer is very beautiful (about 60% of elements divisible by every possible *p*) and we can always delete extra elements. 34 35 Last items is not strict, but one can check it with his computer. 36 37 **D div1** 38 39 1. Consider random element *a**r* of *a*. With probabillity   where *g* is ghd of *a*. 40 2. Let *x**i* = *gcd*(*a**i*, *a**r*). There are no more than *d* distinct *x**i* where *d* is number of divisors of *a**r*. 41 3. We can find number of *a**i* such as  for every *k* in *O*(*d*2). (*D* is set of divisors of *a**r*) 42 4. Repeat item 1 *x* times we will get correct solution with probabillity 1 - 2- *x*. 43 44 There is the way to solve this problem *O*(*n*·*plog* + *d*·2*plog*) for iteration where *plog* is the maximal number of distinct primes in factorisation of *a**r*. 45 46 **E div1** 47 48 1. Let's find number of rectangles whick consist *k* ones and intersect  in cartesian coordinate system. 49 2. It's possible to do it in *n*2·*k*. We need to find closest *k* ones on the top and on the bottom of the  and enumareate all segments [*l*, *r*] such as 1 ≤ *l* ≤ *r* ≤ *n* and find closest *k* ones on the top and on the bottom of the segments merging results for rows. 50 3. If we have *k* closest ones on the top and on the bottom of the segment we will find number of rectangles consists *k* ones and cross  on [*l*, *r*] in *O*(*k*). 51 4. Then we should find number of rectangles, which don't cross . Let's rotate table by 90 degrees, solve similar problem for two halfs of the table and so on. 52 5.  for square-shaped tables. 53 54  55 56 At the picture 1 two closest ones on the top (black cells) lying on the 4'th and 2'nd horizontals. Closest ones on the bottom lying on the 5'th and 7'th. Then if *k* = 2 there are zero correct rectangles with two "ones" on the tom. There are four rectangles which consist one "one" on the top and one "one" on the bottom. You can see how segment grows up at the pictures 2, 3 and 4. Every time you should merge closest *k* ones of the added row with closest *k* ones of the current segment.