codeforces-scrape

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

629.md (6747B)


      1 Source: https://codeforces.com/blog/entry/43227
      2 
      3 ### [Problem A](//www.codeforces.com/contest/629/problem/A):
      4 
      5 Consider that we have *row**i* chocolates in the *i*'*th* row and *col**i* chocolates in the *i*'*th* column.
      6 
      7 The answer to the problem would be: ![](https://espresso.codeforces.com/d884d83c5456e2d5a3e7d29dd2f5cffb8f97e8e4.png). It is obvious that every pair would be calculated exactly once (as we have no more than one chocolate in the same square)
      8 
      9 Time Complexity: *O*(*n*2)
     10 
     11 [C++ Solution](http://beepaste.ir/view/056fea5b)
     12 
     13 ### [Problem B](//www.codeforces.com/contest/629/problem/B):
     14 
     15 Consider that we have *boy**i* males in the *i*'*th* day of the year and *girl**i* females in the *i*'*th* day of the year. These arrays can be filled easily when you are reading the input (See the code). Then for the *i*'*th* day of the year, we could have 2 * *min*(*boy**i* , *girl**i*) people which could come to the party. The answer would be maximum of this value between all days *i* (1 ≤ *i* ≤ 366)
     16 
     17 Time Complexity: *O*(366**n*)
     18 
     19 [C++ Solution](http://beepaste.ir/view/8876646e)
     20 
     21 Bonus: Try to solve this problem with *O*(*n*). For each interval given in the input, you don't need to iterate from day *a**i* to day *b**i*. This idea is used to solve problem [276C](//codeforces.com/problemset/problem/276/C).
     22 
     23 ### [Problem C](//www.codeforces.com/contest/629/problem/C):
     24 
     25 This problem can be solved with dynamic programming:
     26 
     27 1. Calculate *dp**i*, *j* : How many sequences of brackets of length *i* has balance *j* and intermediate balance never goes below zero (They form a prefix of a valid sequence of brackets).
     28 
     29 2. For the given sequence of length *n* calculate the resulting balance *a* and the minimum balance *b*.
     30 
     31 3. Try the length of the sequence added at the beginning *c* and its balance *d*. If  - *b* ≤ *d* then add *dp**c*, *d* × *dp**m* - *n* - *c*, *d* + *a* to the answer.
     32 
     33 Time complexity: *O*((*n* - *m*)2)
     34 
     35 [C++ Solution](http://beepaste.ir/view/bafe3bd2)
     36 
     37 ### [Problem D](//www.codeforces.com/contest/629/problem/D):
     38 
     39 First of all, we calculate the volume of each cake: *v**i* = π × *h**i* × *r**i*2.
     40 
     41 Now consider the sequence *v*1, *v*2, *v*3, ..., *v**n* : The answer to the problem is the maximum sum of elements between all increasing sub-sequences of this sequence. How do we solve this? First to get rid of the decimals we can define a new sequence *a*1, *a*2, *a*3, ..., *a**n* such that ![](https://espresso.codeforces.com/e9011de6fac3edba63a0c478359cbec47ffde369.png)
     42 
     43 We consider *dp**i* as the maximum sum between all the sequences which end with *a**i* and
     44 
     45 *dp**i* = ![](https://espresso.codeforces.com/f931dd9358fc3263266f7f23432f24d95d709a60.png)
     46 
     47 The answer to the problem is: π × *max**i* = 1*n**dp*[*i*]
     48 
     49 Now how do we calculate ![](https://espresso.codeforces.com/e526e97d172b815b886335503d5ea9d80cb8a9bf.png) ? We use a max-segment tree which does these two operations: 1. Change the *i*'*t* member to *v*. 2. Find the maximum value in the interval 1 to *i*.
     50 
     51 Now we use this segment tree for the array *dp* and find the answer.
     52 
     53 Consider that *a*1, *a*2, *a*3, ..., *a**n* is sorted. We define *b**i* as the position of *a**i*. Now to fill *dp**i* we find the maximum in the interval [1, *b**i*) in segment and we call it *x* and we set the *b**i* th index of the segment as *a**i* + *x*. The answer to the problem would the maximum in the segment in the interval [1,n]
     54 
     55 Time complexity: *O*(*nlgn*)
     56 
     57 Thanks to [ATofighi](/profile/ATofighi "Candidate Master ATofighi") who helped a lot for writing the editorial of problem D.
     58 
     59 [C++ Solution](http://beepaste.ir/view/279d0c61)
     60 
     61 ### [Problem E](//www.codeforces.com/contest/629/problem/E):
     62 
     63 First of all, we assume that the tree is rooted! For this problem, first we need to compute some values for each vertex *u*: *qd**u* and *qu**u*, *cnt**u* , *par**u*, *i* and *h**u*. *qd**u* equals to the expected value of length of paths which start from vertex *u*, and ends in *u*’s subtree and also has length at least 1. *qu**u* equals to the expected value of length of paths which start from vertex *u*, and not ends in *u*’s subtree and also has length at least 1. to calculate this values we can use one dfs for *qd*, and one other dfs for *qu*. \ *cnt**u* is the number of vertices in *u*’s subtree except *u*, *par**u*, *i* is the 2*i* ‘th ancestor of *u* and finally *h**u* is the height of the vertex *u*. \ in first dfs (lets call it dfsdown) we can calculate *qd*, *cnt* and *par* array with this formulas:
     64 
     65 ![](https://espresso.codeforces.com/f18a3af40118dccf596c729445d04967562b32ce.png) ![](https://espresso.codeforces.com/f4ebd0f8d0fd11c07e9421487a8e6004770f0016.png)
     66 
     67 for ecah $v$ as child of *u* and *par**u*, *i* = *par**par**u*, *i* - 1, *i* - 1
     68 
     69 in second dfs (lets call it dfsup) we calculate *qu* using this formula (for clearer formula, I may define some extra variables):
     70 
     71 there are two cases:
     72 
     73 *u* is the only child of its parent: let
     74 
     75 ![](https://espresso.codeforces.com/020c7664a47ca699a0fe73e0365d6bcc9856975d.png)
     76 
     77 then
     78 
     79 ![](https://espresso.codeforces.com/51d9d46132d03522dac55bc7ece66f7b3cba0400.png)
     80 
     81 \
     82 
     83 *u* is not the only child of its parent: let
     84 
     85 ![](https://espresso.codeforces.com/c3be36fc7fe4731582c33a9a758aa74f63a3f574.png) ![](https://espresso.codeforces.com/5177ca163b1e0f9b3c5417264226de68ce17f417.png) ![](https://espresso.codeforces.com/20078ea114472955a682088ecc47b102268d1adf.png) ![](https://espresso.codeforces.com/256e0e33f914e97660a46447a97ec7aca5038173.png)
     86 
     87 then
     88 
     89 ![](https://espresso.codeforces.com/55296f989e85dae16dade9465899c9b50d53db03.png)
     90 
     91 now we should process the queries. For each query *u* and *v*, we have to cases: one of the vertices is either one of the ancestors of the other one or not! In the first case, if we define *w* the vertex before *u* (*u* is assumed to be the vertex with lower height). In the path from *v* to *u*, the answer is
     92 
     93 ![](https://espresso.codeforces.com/de1f033bf63417a8708025c18ec5b2aa7a39ae7a.png)
     94 
     95 .
     96 
     97 In the second case, if we assume *w* = *LCA*(*u*, *v*), then answer is
     98 
     99 ![](https://espresso.codeforces.com/b427c63920a5fa1c06417249ad050d67e9ab98c4.png)
    100 
    101 To check if *u* is one of ancestors of *v*, you can check if their *LCA* equals to *u* or you can use dfs to find out their starting and finishing time. *u* is an ancestor of *v* if the interval of starting and finishing time of *v* is completely inside starting and finishing time of *u*
    102 
    103 The time complexity for the whole solution is *O*(*n* + *mlgn*) (*O*(*n*) for dfs and *O*(*lgn*) for each query so *O*(*mlgn*) for queries!).
    104 
    105 [C++ Solution](http://beepaste.ir/view/7ae24ede)