codeforces-scrape

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

437.md (10036B)


      1 Source: https://codeforces.com/blog/entry/12513
      2 
      3 ### [437A - The Child and Homework](/contest/437/problem/A "Codeforces Round 250 (Div. 2)")
      4 
      5 We enumerate each choice *i*, and then enumerate another choice *j* (*j* ≠ *i*), let *cnt* = 0 at first, if choice *j* is twice longer than *i* let *cnt* = *cnt* + 1, if choice *j* is twice shorter than *i* let *cnt* = *cnt* - 1. So *i* is great if and only if *cnt* = 3 or *cnt* =  - 3.
      6 
      7 If there is exactly one great choice, output it, otherwise output C.
      8 
      9 ### [437B - The Child and Set](/contest/437/problem/B "Codeforces Round 250 (Div. 2)")
     10 
     11 We could deal with this by digits.
     12 
     13 Because *lowbit*(*x*) is taking out the lowest 1 of the number *x*, we can enumerate the number of the lowest zero.
     14 
     15 Then, if we enumerate *x* as the number of zero, we enumerate *a* as well, which *a* × 2*x* is no more than *limit* and *a* is odd. We can find out that *lowbit*(*a* × 2*x*) = 2*x*.
     16 
     17 In this order, we would find out that the *lowbit*() we are considering is monotonically decresing.
     18 
     19 Because for every two number *x*, *y*, *lowbit*(*x*) is a divisor of *lowbit*(*y*) or *lowbit*(*y*) is a divisor of *lowbit*(*x*).
     20 
     21 We can solve it by greedy. When we enumerate *x* by descending order, we check whether 2*x* is no more than *sum*, and check whether there is such *a*. We minus 2*x* from *sum* if *x* and *a* exist.
     22 
     23 If at last *sum* is not equal to 0, then it must be an impossible test.
     24 
     25 Why? Because if we don't choose a number whose *lowbit* = 2*x*, then we shouldn't choose two numbers whose *lowbit* = 2*x* - 1. (Otherwise we can replace these two numbers with one number)
     26 
     27 If we choose one number whose *lowbit* = 2*x* - 1, then we can choose at most one number whose *lowbit* = 2*x* - 2, at most one number whose *lowbit* = 2*x* - 3 and so on. So the total sum of them is less than 2*x* and we can't merge them into *sum*.
     28 
     29 If we don't choose one number whose *lowbit* = 2*x* - 1, then it's just the same as we don't choose one number whose *lowbit* = 2*x*.
     30 
     31 So the total time complexity is *O*(*limit*).
     32 
     33 ### [437C - The Child and Toy](/contest/437/problem/C "Codeforces Round 250 (Div. 2)")
     34 
     35 The best way to delete all n nodes is deleting them in decreasing order of their value.
     36 
     37 Proof:
     38 
     39 Consider each edge (*x*, *y*), it will contribute to the total cost *v**x* or *v**y* when it is deleted.
     40 
     41 If we delete the vertices in decreasing order, then it will contribute only *min*(*v**x*, *v**y*), so the total costs is the lowest.
     42 
     43 ### [437D - The Child and Zoo](/contest/437/problem/D "Codeforces Round 250 (Div. 2)")
     44 
     45 First, there is nothing in the graph. We sort all the areas of the original graph by their animal numbers in decreasing order, and then add them one by one.
     46 
     47 When we add area *i*, we add all the roads (*i*, *j*), where *j* is some area that has been added.
     48 
     49 After doing so, we have merged some connected components. If *p* and *q* are two areas in different connected components we have merged just then, *f*(*p*, *q*) must equals the *v**i*, because they are not connected until we add node *i*.
     50 
     51 So we use Union-Find Set to do such procedure, and maintain the size of each connected component, then we can calculate the answer easily.
     52 
     53 ### [437E - The Child and Polygon](/contest/437/problem/E "Codeforces Round 250 (Div. 2)")
     54 
     55 In this problem, you are asked to count the triangulations of a simple polygon.
     56 
     57 First we label the vertex of polygon from 0 to *n* - 1.
     58 
     59 Then we let *f*[*i*][*j*] be the number of triangulations from vertex *i* to vertex *j*. (Suppose there is no other vertices and there is an edge between *i* and *j*)
     60 
     61 If the line segment (*i*, *j*) cross with the original polygon or is outside the polygon, *f*[*i*][*j*] is just 0. We can check it in *O*(*n*) time.
     62 
     63 Otherwise, we have ![](https://espresso.codeforces.com/cd021ec11471d2e96e550197f14b7ed32598ef89.png), which means we split the polygon into the triangulation from vertex *i* to vertex *k*, a triangle (*i*, *k*, *j*) and the triangulation from vertex *k* to vertex *j*. We can sum these terms in *O*(*n*) time.
     64 
     65 Finally,the answer is *f*[0][*n* - 1]. It's obvious that we didn't miss some triangulation. And we use a triangle to split the polygon each time, so if the triangle is different then the triangulation must be different, too. So we didn't count some triangulation more than once.
     66 
     67 So the total time complexity is *O*(*n*3), which is sufficient for this problem.
     68 
     69 ### [438D - The Child and Sequence](/contest/438/problem/D "Codeforces Round 250 (Div. 1)")
     70 
     71 The important idea of this problem is the property of ![](https://espresso.codeforces.com/f52a9a86d828a54c4bc7e70dc407e45e8e5464a6.png).
     72 
     73 Let ![](https://espresso.codeforces.com/01fcef8ed7875640ef4a70baddf087c44f736315.png).
     74 
     75 So, ![](https://espresso.codeforces.com/723ba854fea00c3c303168b6beca0f0ad92d379a.png).
     76 
     77 If *k* = 0, ![](https://espresso.codeforces.com/519ac0bfebb222cc5ec15eae5af1727aaba7558a.png) remains to be *x*.
     78 
     79 If *k* ≠ 0, ![](https://espresso.codeforces.com/97e68da714cb78d73fc6a647b6cf1976f617e925.png).
     80 
     81 We realize every time a change happening on *x*, *x* will be reduced by at least a half.
     82 
     83 So let the energy of *x* become ![](https://espresso.codeforces.com/ee4a3a0619035aa41f38857c6f5316afd2872d22.png). Every time when we modify *x*, it may take at least 1 energy.
     84 
     85 The initial energy of the sequence is ![](https://espresso.codeforces.com/40af9ccb6321f81c20dcca850299efedb91d60e0.png).
     86 
     87 We use a segment tree to support the query to the maximum among an interval. When we need to deal with the operation 2, we modify the maximum of the segment until it is less than *x*.
     88 
     89 Now let's face with the operation 3.
     90 
     91 Every time we modify an element on the segment tree, we'll charge a element with ![](https://espresso.codeforces.com/df33797b004364f28f002fa451f34554cb4113ab.png) power.
     92 
     93 So the total time complexity is : ![](https://espresso.codeforces.com/2e7edf1c79084ec9674d2d068fd714c42ccaaeee.png).
     94 
     95 By the way, we can extend the operation 3 to assign all the elements in the interval to the same number in the same time complexity. This is an interesting idea also, but a bit harder. You can think of it.
     96 
     97 ### [438E - The Child and Binary Tree](/contest/438/problem/E "Codeforces Round 250 (Div. 1)")
     98 
     99 Let *f*[*s*] be the number of good vertex-weighted rooted binary trees whose weight exactly equal to *s*, then we have:
    100 
    101 *f*[0] = 1
    102 
    103 ![](https://espresso.codeforces.com/2ffa90fc3d1bec461fdc113e99375ca4d887807e.png)
    104 
    105 Let F(z) be the generating function of f. That is, ![](https://espresso.codeforces.com/3a9c82ad8da47e99e5f3fa2bb22fe407465b1361.png)
    106 
    107 And then let ![](https://espresso.codeforces.com/dfaf23736ca4c69d769c2de93dcadd75c9bdfc2e.png)
    108 
    109 So we have:
    110 
    111 *F*(*z*) = *C*(*z*)*F*(*z*)2 + 1
    112 
    113 `` + 1'' is for *f*[0] = 1.
    114 
    115 Solve this equation we have:
    116 
    117 ![](https://espresso.codeforces.com/a7f84986b750ad586ebe7ddc8ea1fef8759d94cd.png)
    118 
    119 So the remaining question is: how to calculate the multiplication inverse of a power series and the square root of a power series?
    120 
    121 There is an interesting algorithm which calculate the inverse of a power series *F*(*z*):
    122 
    123 We use *f*(*z*) ≡ *g*(*z*) (*mod* *z**n*) to denote that the first *n* terms of *f*(*z*) and *g*(*z*) are the same.
    124 
    125 We can simply calculate a formal power series *R*1(*z*) which satisfies *R*1(*z*)*F*(*z*) ≡ 1 (*mod* *z*1)
    126 
    127 Next, if we have *R**n*(*z*) which satisfies *R**n*(*z*)*F*(*z*) ≡ 1 (*mod* *z**n*), we will get:
    128 
    129 (*R**n*(*z*)*F*(*z*) - 1)2 ≡ 0 (*mod* *z*2*n*)
    130 
    131 *R**n*(*z*)2*F*(*z*)2 - 2*R**n*(*z*)*F*(*z*) + 1 ≡ 0 (*mod* *z*2*n*)
    132 
    133 1 ≡ 2*R**n*(*z*)*F*(*z*) - *R**n*(*z*)2*F*(*z*)2 (*mod* *z*2*n*)
    134 
    135 *R*2*n*(*z*) ≡ 2*R**n*(*z*) - *R**n*(*z*)2*F*(*z*) (*mod* *z*2*n*)
    136 
    137 We can simplely use Fast Fourier Transform to deal with multiplication. Note the unusual mod 998244353 (7 × 17 × 223 + 1), thus we can use Number Theoretic Transform.
    138 
    139 By doubling *n* repeatedly, we can get the first *n* terms of the inverse of *F*(*z*) in ![](https://espresso.codeforces.com/4b2fa1e3d3d43bd9f28ff6c3140f816dc0e0621a.png) time. It's because that ![](https://espresso.codeforces.com/7b282e6b4f0439ca16ead5faa172634059ad190c.png)
    140 
    141 We can just use the idea of this algorithm to calculate the square root of a power series *F*(*z*):
    142 
    143 We can simply calculate a power series *S*1(*z*) which satisfies *S*1(*z*)2 ≡ *F*(*z*) (*mod* *z*2*n*)
    144 
    145 Next, if we have *S**n*(*z*) which satisfies *S**n*(*z*)2 ≡ *F*(*z*) (*mod* *z**n*), we will get:
    146 
    147 (*S**n*(*z*)2 - *F*(*z*))2 ≡ 0 (*mod* *z*2*n*)
    148 
    149 *S**n*(*z*)4 - 2*S**n*(*z*)2*F*(*z*) + *F*(*z*)2 ≡ 0 (*mod* *z*2*n*)
    150 
    151 *S**n*(*z*)2 - 2*F*(*z*) + *F*(*z*)2*S**n*(*z*)- 2 ≡ 0 (*mod* *z*2*n*)
    152 
    153 4*F*(*z*) ≡ *S**n*(*z*)2 + 2*F*(*z*) + *F*(*z*)2*S**n*(*z*)- 2 (*mod* *z*2*n*)
    154 
    155 4*F*(*z*) ≡ (*S**n*(*z*) + *F*(*z*)*S**n*(*z*)- 1)2 (*mod* *z*2*n*)
    156 
    157 ![](https://espresso.codeforces.com/9493649af1762dc0b41b5eb32c70253e71abd3c6.png)
    158 
    159 So, ![](https://espresso.codeforces.com/68ad3cf8beffd54efcd97c06926c8999e35c893a.png)
    160 
    161 By doubling *n* repeatedly, we can get the first *n* terms of the square root of *F*(*z*) in ![](https://espresso.codeforces.com/4b2fa1e3d3d43bd9f28ff6c3140f816dc0e0621a.png) time.
    162 
    163 That's all. What I want to share with others is this beautiful doubling algorithm.
    164 
    165 So the total time complexity of the solution to the original problem is ![](https://espresso.codeforces.com/c915fd0b8237f7fb583b177943556ae9cc422670.png).
    166 
    167 [My code](http://ideone.com/uQYLfQ)
    168 
    169 There is an algorithm solving this problem using divide and conquer and Fast Fourier Transform, which runs in ![](https://espresso.codeforces.com/0b7cf0d33b8a7f7e0c6378bc50ec672d86acc8e2.png). See [the C++ code](http://ideone.com/TQ4lh8) and [the Java code](http://ideone.com/BNaVHv) for details.