514.md (3811B)
1 Source: https://codeforces.com/blog/entry/16398 2 3 ## [514A - Chewbaсca and Number](/contest/514/problem/A "Codeforces Round 291 (Div. 2)") 4 5 **Author:** [Rebryk](/profile/Rebryk "Expert Rebryk") 6 7 It is obvious that all the digits, which are greater than 4, need to be inverted. The only exception is 9, if it's the first digit. 8 9 **Complexity:**  10 11 ## [514B - Han Solo and Lazer Gun](/contest/514/problem/B "Codeforces Round 291 (Div. 2)") 12 13 **Author:** [Antoniuk](/profile/Antoniuk "Candidate Master Antoniuk") 14 15 Let's run through every point, where the stormtroopers are situated. If in current point stormtroopers are still alive, let's make a shot and destroy every stormtrooper on the same line with gun and current point. 16 17 Points (*x*1, *y*1), (*x*2, *y*2), (*x*3, *y*3) are on the same line, if (*x*2 - *x*1)(*y*3 - *y*1) = (*x*3 - *x*1)(*y*2 - *y*1). 18 19 **Complexity:**  20 21 ## [514C - Watto and Mechanism](/contest/514/problem/C "Codeforces Round 291 (Div. 2)") 22 23 **Author:** [Rebryk](/profile/Rebryk "Expert Rebryk") 24 25 While adding a string to the set, let's count its polynomial hash and add it to an array. Then let's sort this array. Now, to know the query answer, let's try to change every symbol in the string and check with binary search if its hash can be found in the array (recounting hashes with  complexity). If the hash is found in the array, the answer is "YES", otherwise "NO". 26 27 **Complexity:** , where *L* is total length of all strings. 28 29 ## [514D - R2D2 and Droid Army](/contest/514/problem/D "Codeforces Round 291 (Div. 2)") 30 31 **Author:** [Rebryk](/profile/Rebryk "Expert Rebryk") 32 33 To destroy all the droids on a segment of *l* to *r*, we need to make  shots, where *cnt*[*i*][*j*] — number of *j*-type details in *i*-th droid. Let's support two pointers — on the beginning and on the end of the segment, which we want to destroy all the droids on. If we can destroy droids on current segment, let's increase right border of the segment, otherwise increase left border, updating the answer after every segment change. Let's use a queue in order to find the segment maximum effectively. 34 35 **Complexity:**  36 37 ## [514E - Darth Vader and Tree](/contest/514/problem/E "Codeforces Round 291 (Div. 2)") 38 39 **Author:** [Antoniuk](/profile/Antoniuk "Candidate Master Antoniuk") 40 41 It's easy to realize that , where *dp*[*i*] is number of vertices, which are situated on a distance *i* from the root, and *cnt*[*j*] is number of children, which are situated on a distance *j*. Answer . 42 43 Let the dynamics condition 44 45  46 47 Let's build a transformation matrix of 101 × 101 size 48 49  50 51 Now, to move to the next condition, we need to multiply A by B. So, if matrix *C* = *A*·*B**x* - 100, then the answer will be situated in the very right cell of this matrix. For *x* < 100 we'll find the answer using dynamics explained in the beginning. 52 53 In order to find *B**k* let's use binary power. 54 55 **Complexity:** 