codeforces-scrape

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

483.md (10006B)


      1 Source: https://codeforces.com/blog/entry/14417
      2 
      3 ## [483A - Counterexample](/contest/483/problem/A "Codeforces Round 275 (Div. 2)")
      4 
      5 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit")
      6 
      7 This problem has two possible solutions:
      8 
      9 1. Let's handle all possible triples and check every of them for being a counterexample. This solution works with asymptotics *O*(*n*3*logA*)
     10 2. Handle only a few cases. It could be done like this:
     11 
     12 ```
     13   if (l % 2 != 0)
     14       l++;
     15    
     16   if (l + 2 > r)
     17     out.println(-1);
     18   else
     19     out.println(l + " " + (l + 1) + " " + (l + 2));
     20 ```
     21 
     22 Jury's solution: [8394832](/contest/483/submission/8394832 "Submission 8394832 by gridnevvvit")
     23 
     24 ## [483B - Friends and Presents](/contest/483/problem/B "Codeforces Round 275 (Div. 2)")
     25 
     26 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit")
     27 
     28 Jury's solution is using binary search. First, you can notice that if you can make presents with numbers 1, 2, ..., *v* then you can make presents with numbers 1, 2, ..., *v*, *v* + 1 too. Let *f*(*v*) be the function returning true or false: is it right, that you can make presents with numbers 1, 2, ..., *v*. Let *f*1 be the number of numbers divisible by *x*, *f*2 — the number of numbers divisible by *y*, and *both* — number of numbers divisible by *x* and by *y* (as soon as *x* and *y* are primes, it is equivalent to divisibility by *x*·*y*). Then to first friend at first we shold give *f*2 - *both* numbers, and to second friend *f*1 - *both* numbers. Then we must check, could we give all other numbers divisible neither by *x* nor by *y*.
     29 
     30 This solution works with ![](https://espresso.codeforces.com/9040a33098f83986b0de64475c66584fbfdf0e22.png)
     31 
     32 Jury's solution: [8394846](/contest/483/submission/8394846 "Submission 8394846 by gridnevvvit")
     33 
     34 ## [483C - Diverse Permutation](/contest/483/problem/C "Codeforces Round 275 (Div. 2)") / [482A - Diverse Permutation](/contest/482/problem/A "Codeforces Round 275 (Div. 1)")
     35 
     36 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit")
     37 
     38 Let's see, what's the solution for some *k* = *n* - 1:
     39 
     40 1 10 2 9 3 8 4 7 5 6
     41 
     42 At the odd indexes we placed increasing sequence 1, 2, 3 .., at the even — decreasing sequence *n*, *n* - 1, *n* - 2, ... First, we must get the permutation the way described above, then get first *k* numbers from it, and then we should make all other distances be equal to 1.
     43 
     44 This solution works with *O*(*n*).
     45 
     46 Jury's solution: [8394876](/contest/483/submission/8394876 "Submission 8394876 by gridnevvvit")
     47 
     48 ## [483D - Interesting Array](/contest/483/problem/D "Codeforces Round 275 (Div. 2)") / [482B - Interesting Array](/contest/482/problem/B "Codeforces Round 275 (Div. 1)")
     49 
     50 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit")
     51 
     52 We will solve the task for every distinct bit. Now we must handle new constraint: *l*[*i*], *r*[*i*], *q*[*i*]. If number *q*[*i*] has 1 in bit with number *pos*, then all numbers in segment [*l*[*i*], *r*[*i*]] will have 1 in that bit too. To do that, we can use a standard idea of adding on a segment.
     53 
     54 Let's do two adding operation in *s*[*pos*] array — in position *l*[*i*] we will add 1, and in posiotion *r*[*i*] + 1 — -1. Then we will calculate partial sums of array *s*[*pos*], and if *s*[*pos*][*i*] > 0 (the sum on prefix length *i* + 1), then bit at position *pos* will be 1, otherwise — 0.
     55 
     56 After that, you can use segment tree to check satisfying constraints.
     57 
     58 Jury's solution: [8394894](/contest/483/submission/8394894 "Submission 8394894 by gridnevvvit")
     59 
     60 ## [483E - Game with Strings](/contest/483/problem/E "Codeforces Round 275 (Div. 2)") / [482C - Game with Strings](/contest/482/problem/C "Codeforces Round 275 (Div. 1)")
     61 
     62 Problem author [gridnevvvit](/profile/gridnevvvit "Candidate Master gridnevvvit")
     63 
     64 Let's handle all string pairs and calculate the *mask* mask, which will have 1-bits only in positions in which that strings have the same characters. In other words, we could not distinguish these strings using positions with submask of mask *mask*, then we must add in *d*[*mask*] 1-bits in positions *i* и *j*. This way in *d*[*mask*] we store mask of strings, which we could not distinguish using only positions given in mask *mask*. Using information described above, we can easily calculate this dynamics.
     65 
     66 Now, when we have array *d* calculated, it is not hard to calculate the answer. Let's handle some mask *mask*. Now we should try to make one more question in position *pos*, which is equal to adding one more 1-bit in *mask* in position *pos*. After that we may guess some strings, they are 1-bits in mask `s = d[mask] ^ d[mask | (1 << pos)]`. Then you have to calculate number of bits in *s* quickly and update the answer.
     67 
     68 Jury's solution: [8394918](/contest/483/submission/8394918 "Submission 8394918 by gridnevvvit")
     69 
     70 ## [482D - Random Function and Tree](/contest/482/problem/D "Codeforces Round 275 (Div. 1)")
     71 
     72 Problem author [RoKi](/profile/RoKi "Candidate Master RoKi")
     73 
     74 Let's calculate *d*[*v*][*p*] dynamics — the answer for vertex *v* with size of parity *p*.
     75 
     76 At first step to calculate this dynamic for vertex *v* we should count all different paintings of a subtree visiting all children in increasing order of their numbers. By multiplying this number by 2 we will get paintings visiting children in decreasing order. Now some paintings may count twice. To fix that, let's have a look on a some subtree of a vertex *v*.
     77 
     78 Consider all the parities of children subtrees visited by our function (0 or 1). First thing to note is that among these parities exist two different values, the subtree will have different paintings with different ordering (you can prove it yourself). Otherwise, all our children sizes have the same parity.
     79 
     80 If all sizes are even, this subtree will be counted twice. Otherwise, if sizes are odd, we are interested only in odd count of visited subtrees. This way, we must subtract from our dynamic the number of ways to paint any number of children with even subtree sizes and odd number of children with odd subtree sizes.
     81 
     82 Jury's solution: [8394936](/contest/482/submission/8394936 "Submission 8394936 by gridnevvvit")
     83 
     84 ## [482E - ELCA](/contest/482/problem/E "Codeforces Round 275 (Div. 1)")
     85 
     86 Problem author [danilka.pro](/profile/danilka.pro "Master danilka.pro")
     87 
     88 Let's split all *M* requests in ![](https://espresso.codeforces.com/39c23d0135ed36518dedf4933ac1665afa47f339.png) blocks containing ![](https://espresso.codeforces.com/39c23d0135ed36518dedf4933ac1665afa47f339.png) requests each. Every block will be processed following way:
     89 
     90 First using dfs we need to calculate ![](https://espresso.codeforces.com/d79aced41b56c77f8770e3df4dcbd64809388de0.png) for every vertex *v*, where *u* is every ancestor of *v*, *size**i* — size of subtree of vertex *i*, including itself. This value shows how will the answer change after removing or adding vertex *v* as child to any other vertex, furthermore, answer will change exactly by *path**v*·*size**v* (decreasing or increasing).
     91 
     92 Then we will calculate *ch**v* the same way — the number of all possible vertex pairs, which have LCA in vertex *v*. This value shows how the answer changes after changing *V**v* — if *V**v* changes by *dV**v*, answer changes by *ch**v*·*dV**v*.
     93 
     94 Then mark all vertexes, which occur in our block at least once (in worst case their number is ![](https://espresso.codeforces.com/4480f7985e3ad6d48f8d7ee30559e20ec977874c.png)). Next, mark every vertex being LCA of some pair of already marked vertexes, using DFS. We can prove that final number of these vertexes is at most ![](https://espresso.codeforces.com/1e4827e6f263e447ee9252ab4cf0915d42aa3715.png). After all this we got 'compressed' tree, containing only needed vertexes. Parent of vertex *i* in compressed tree we will call vertex numbered *P**i*.
     95 
     96 On the image above example of this 'compression' way is given. Vertexes colored red are vertexes in request block, blue — vertexes marked after LCA, dotted line — *P**v* → *v* edges in compressed tree.
     97 
     98 ![Example of compressed tree](/predownloaded/bd/d2/bdd29831ecc0ae3f8a14002b0de45cf26aa2ade3.png)
     99 
    100 On such compressed tree we need to calculate one new value *C**v* for every vertex *v* — the size of a vertex, lying on a way from *P**v* to *v* after *P**v* on main (non-compressed) tree (son of a *P**v* vertex in main tree).
    101 
    102 Now we should process request on changing parent of vertex *v* from *p**v* to *u* on a compressed tree. The answer will change by *path**v*·*size**v*. Now for every vertex *i*, lying on a way from root to *P**v* vertex, two values will change: *size**i* will be decreased by *size**v*, but *ch**i* will be decreased by *size**v*·(*size**i* - *C**t*), (*P**t* = *i*), but *path**i* will stay unchanged. For every other vertex *j* only *path**j* will be changed: it will be decreased by ![](https://espresso.codeforces.com/a36a3cfa6e6a0b49c76d6f1b52428addac3c28cc.png). After that, we got compressed subtree where subtree of a vertex *v* is missing. Next, doing the same way as above, all values are changed considering that *v* (and all it's subtree) is a children of a vertex *u*. Do not forget to change *C**v* too.
    103 
    104 Let's see, how the value-changing request of a vertex *v* is to be processed. As described above, the answer will be changed by *ch**v*·*dV**v*. For every vertex *i* lying in vertex *v* subtree only *path**i* will be changed (it could be easy done using *C**to* values), all other values stay unchanged.
    105 
    106 This solution has ![](https://espresso.codeforces.com/03c5957e57b3dea9f6303a0163964c98ea682fcc.png) complexity, but in *N* = *M* case it has to be ![](https://espresso.codeforces.com/63364b2e896bd50f82216d1a378bb4c0c0f5f799.png).
    107 
    108 Авторское решение: [8394944](/contest/482/submission/8394944 "Submission 8394944 by gridnevvvit")