623.md (9052B)
1 Source: https://codeforces.com/blog/entry/23278 2 3 [624A - Save Luke](/contest/624/problem/A "AIM Tech Round (Div. 2)") 4 5 Width of free space is decreasing by *v*1 + *v*2 per second. It means that it'll decrease from *L* to *d* in  seconds. The moment when width gets a value of *d* is the last when Luke is alive so *t* is the answer. 6 7 [624B - Making a String](/contest/624/problem/B "AIM Tech Round (Div. 2)") 8 9 Sort array in descending order. 10 11 Iterate over all letters, First letter is added *c*1 = *a*1 times, each other letter is added *c**i* = *min*(*a**i*, *c**i* - 1). Don't forget that if some letter is not added at all, then all next letters are not added too. 12 13 [623A - Graph and String](/contest/623/problem/A "AIM Tech Round (Div. 1)") Note that all vertices "b" are connected with all other vertices in the graph. Find all such vertices and mark them as "b". Now we need to find any unlabeled vertex *V*, mark it with "a" character. Unlabeled vertices connected with *V* should be also labeled as "a". All other vertices we can label as "c" 14 15 Finally we need to check graph validity. Check that all vertices "a" are only connected with each other and "b" vertices. After that we need to perform a similar check for "c" vertices. 16 17 [623B - Array GCD](/contest/623/problem/B "AIM Tech Round (Div. 1)") 18 19 At least one of ends (*a*1 or *a**n*) is changed by at most 1. It means that if gcd > 1 then it divides on of prime divisors of either *a*1 - 1, *a*1, *a*1 + 1, *a**n* - 1, *a**n* or *a**n* + 1. We will iterate over these primes. 20 21 Suppose prime *p* is fixed. For each number we know that it's either divisible by *p* or we can pay *b* to fix it or it should be in the subarray to change for *a* 22 23 We can use dynamic programming dp[number of numbers considered][subarray to change not started/started/finished] = minimal cost 24 25 Complexity is *O*(*Nd*) = *O*(*Nlog*(*max*(*a**i*)), where *d* is the number of primes to check. 26 27 [623C - Electric Charges](/contest/623/problem/C "AIM Tech Round (Div. 1)") 28 29 First of all consider cases where all points are projected to the same axis. (In that case answer is difference between maximum and minimum of this coordinate). 30 31 Now consider leftmost and rightmost points among projected to *x* axis. Let *x**L* and *x**R* are their *x*-coordinates. Notice that points with x-coordinate *x**L* ≤ *x* ≤ *x**R* may also be projected to *x*-axis and that will not increase the diameter. So, if we sort all points by *x*-coordinate, we may suppose that points projected to *x*-axis form a continuous subarray. 32 33 We will use a binary search. Now we will need to check if it's possible to project point in a such way that diameter is <= M. 34 35 Let's fix the most distant by *x*-coordinate point from 0 that is projected to *x*-axis. It may be to the left or to the right of 0. This cases are symmetrical and we will consider only the former one. Let *x**L* < 0 be its coordinate. Notice that one may project all points such that 0 ≤ *x* - *x**L* ≤ *M* and |*x*| ≤ |*x**L*| to the *x* axis (and it'll not affect the diameter) and we have to project other points to *y*-axis. Among all other points we should find the maximum and minimum by *y* coordinate. Answer is "yes (*diam* ≤ *M*)" if *y**max* - *y**min* < = *M* and distance from (*x**L*, 0) to both (0, *y**max*) and (0, *y**min*) is not greater than M. 36 37 Let's precalculate maximums and minimums of *y* coordinates on each prefix and suffix of original (sorted) points array. Now iterate over left border of subarray of points projected to *x*-axis and find the right border using binary search or maintain it using two-pointers technique. 38 39 So we've got one check in *O*(*M*) or  and entire solution in  or  40 41 [623D - Birthday](/contest/623/problem/D "AIM Tech Round (Div. 1)") 42 43 Let's denote *q**i* = 1 - *p**i*. 44 45 Main idea: first of all guess each friend once, then maximize probability to end game on current step. Let's simulate first 300000 steps, and calculate . , where *k**i* — how many times we called *i*-th friend (). 46 47 Expectation with some precision equals . So it is enough to prove that: 48 49 1) Greedy strategy gives maximum values for all *Pr*(*t*). 50 51 2) On 300000 step precision error will be less than 10- 6. 52 53 Proof: 54 55 1) Suppose, that for some *t* there exists set *l**i* (), not equal to set produced by greedy algorithm *k**i*, gives the maximum value of *Pr*(*t*). Let's take some *k**a* < *l**a* and *k**b* > *l**b*, it is easy to prove tgat if we change *l**b* to *l**b* + 1, *l**a* to *l**a* - 1, then new set of *l**i* gives bigger value of *Pr*(*t*), contradiction. 56 57 2) *q**i* ≤ 0.99. Let's take set , it gives probability of end of the game not less than optimal. Then *Pr*(*t*) ≥ (1 - 0.99*t* / 100)100 ≥ 1 - 100·0.99*t* / 100. Precision error does not exceed . It could be estimated as sum of geometric progression. If *N* ≥ 300000 precision error doesn't exceed 10- 7. 58 59 [623E - Transforming Sequence](/contest/623/problem/E "AIM Tech Round (Div. 1)") 60 61 First observation is that if the sequence of prefix xors is strictly increasing, than on each step *a**i* has at least one new bit comparing to the previous elements. So, since there are overall *k* bits, the length of the sequence can't be more than *k*. So, if *n* > *k*, the answer is 0. 62 63 Let's firstly solve the task with *O*(*k*3) complexity. We calculate *dp*[*n*][*k*] — the number of sequences of length *n* such that *a*1|*a*2|... |*a**n* has *k* bits. The transition is to add a number with *l* new bits, and choose those *k* bits which are already in the prefix xor arbitrarily. So, *dp*[*n* + 1][*k* + *l*] is increased by *dp*[*n*][*k*]·2*k*·*C**k* + *l**l*. The last binomial coefficient complies with the choice these very *l* bits from *k* + *l* which will be present in *a*1|*a*2|... |*a**n* + 1. 64 65 Note now that the transition doesn't depend on *n*, so let's try to use the idea of the binary exponentiation. Suppose we want to merge two dynamics *dp*1[*k*], *dp*2[*k*], where *k* is the number of bits present in *a*1|*a*2|... |*a**left* and *b*1|... |*b**right* correspondingly. Now we want to obtain *dp*[*k*] for arrays of size *left* + *right*. The formula is: 66 67  68 69 Here *l* corresponds to the bits present in the xor of the left part, and for each number of the right part we can choose these *l* bits arbitrarily. Rewrite the formula in the following way: 70 71  72 73 So, we can compute *dp*[*k*] for all *k* having multiplied two polynomials  and . We can obtain the coefficients of the first polynomial from the coefficients of the second in . So, we can compute this dynamic programming for all lengths — powers of two, in , using the fast Fourier transform. In fact, it is more convenient to compute  using the same equation. After that, we can use the same merge strategy to compute the answer for the given *n*, using dynamics for the powers of two. Overall complexity is . 74 75 We decided to ask the answer modulo 109 + 7 to not let the participants easily guess that these problem requires FFT :) So, in order to get accepted you had to implement one of the methods to deal with the large modulo in polynomial multiplication using FFT. Another approach was to apply Karatsuba algorithm, our realisation timed out on our tests, but [EvenImage](/profile/EvenImage "Legendary Grandmaster EvenImage") somehow made it pass :)