codeforces-scrape

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

896.md (11739B)


      1 Source: https://codeforces.com/blog/entry/56135
      2 
      3 [897A — Scarborough Fair](//codeforces.com/contest/897/problem/A) By [webmaster](/profile/webmaster "International Grandmaster webmaster")
      4 
      5 For every *i* in range [*l*, *r*], if *c**i* is *c*1 then change it into *c*2...
      6 
      7 Because *n*, *m* are all very small, *O*(*nm*) can easily pass it.
      8 
      9 PS. You can use binary search tree to solve it in ![](https://espresso.codeforces.com/326000bf060a23fb55002815ec5ddbda3af5d06d.png) time.
     10 
     11 [897B — Chtholly's request](//codeforces.com/contest/897/problem/B) By [webmaster](/profile/webmaster "International Grandmaster webmaster")
     12 
     13 The *k*-th smallest zcy number is *conn*(*str*(*k*), *rev*(*str*(*k*))), where *str* denotes the decimal representation of a positive integer as a string, *conn* denotes the concatenation two strings, and *rev* denotes the reverse of a string.
     14 
     15 Then go over the smallest *k* such numbers and sum them up to obtain the answer.
     16 
     17 [896A — Nephren gives a riddle](//codeforces.com/contest/896/problem/A) By [webmaster](/profile/webmaster "International Grandmaster webmaster")
     18 
     19 *f*(*n*) = *str*1 + *f*(*n* - 1) + *str*2 + *f*(*n* - 1) + *str*3.
     20 
     21 First we can compute the length of *f*(*n*) for all possible *n*.
     22 
     23 For a pair of (*n*, *k*), we can easily determine which part the *k*-th character is in.
     24 
     25 If it's in *f*(*n* - 1), we can solve the problem recursively.
     26 
     27 The complexity of this algorithm is *O*(*n*), which is sufficient to pass all tests.
     28 
     29 Obviously, *length*(*f*(*n*)) ≥ *length*(*f*(*n* - 1))·2, so *length*(*f*(60)) ≥ *k**max*.
     30 
     31 It means that for all *n* > 60, the *k*-th character of *f*(*n*) can only be in *str*1 or the first *f*(*n* - 1).
     32 
     33 Then we can answer a query in ![](https://espresso.codeforces.com/b7e36f0b637350e6eed80abb99091111907028ca.png) time.
     34 
     35 [896B — Ithea Plays With Chtholly](//codeforces.com/contest/896/problem/B) By [dogther](/profile/dogther "Candidate Master dogther")
     36 
     37 As the initial sheet "has already" in a non-decreasing order (although it has no numbers), what we should do is just "maintain" this order.
     38 
     39 We use a simple method to do so: find the first sheet whose number is strictly greater than the given number (or it's an empty sheet) and replace it with the new number.
     40 
     41 For each round, we either replace an existing number with a strictly smaller one, or fill in an empty sheet. The first case will happen at most *c* - 1 times for each sheet, and the second case will happen only once for each sheet. Thus in total, we will modify a sheet for at most *c* times. Thus, the total rounds won't be more than *n* × *c*.
     42 
     43 To pass all the tests, we only need to maintain 2 similar sequences, one non-decreasing from the first and one non-increasing from the last, which makes a total round of ![](https://espresso.codeforces.com/95e9bd2593d7a43f3dcbc8dd9a15489f2fc0ede3.png), precisely, and use binary search or brute force to complete the "finding" process.
     44 
     45 [896C — Willem, Chtholly and Seniorious](//codeforces.com/contest/896/problem/C) By [ODT](/profile/ODT "Candidate Master ODT")
     46 
     47 This is an interesting algorithm which can easily deal with many data structure problems------if the data is random...
     48 
     49 I initially named it as "Old Driver Tree" ( Which is my codeforces ID ).
     50 
     51 (But now I call it Chtholly Tree~).
     52 
     53 We can find that there is an operation that makes a range of number the same.
     54 
     55 We can use an interval tree (std::set is enough) to maintain every interval that consists of the same number.
     56 
     57 And for operation 2, we destory all the intervals in range [*l*, *r*] , and put in a new interval [*l*, *r*] into the interval tree.
     58 
     59 For operations 1, 3, 4, we can brute-forcely walk on the tree, find every interval in range [*l*, *r*], and do the required operation on it.
     60 
     61 Proof of time complexity:
     62 
     63 We suppose that we have a randomly selected range [*l*, *r*] now, and we randomly choose which operation it is, suppose that there are *x* intervals in this range.
     64 
     65 1/4 possibility we use *O*(*x*) time to erase *O*(*x*) nodes.
     66 
     67 2/4 possibility we use *O*(*x*) time to erase nothing.
     68 
     69 1/4 possibility we use *O*(*x*) time to erase nothing and add 2 new nodes into the tree.
     70 
     71 So we are expected to use *O*(*x*) time to erase *O*(*x*) nodes.
     72 
     73 By using interval tree to maintain, the time complexity of this problem is ![](https://espresso.codeforces.com/326000bf060a23fb55002815ec5ddbda3af5d06d.png).
     74 
     75 If operation 3 and 4 are changed into output the sum of *a**i* for every *i* range [*l*, *r*], it seems that the time complexity may change into ![](https://espresso.codeforces.com/0eeb9bc4e1bee300d944bb08caf76ee34257e240.png) , but I do not know how to prove it...
     76 
     77 [Solution using map](//codeforces.com/contest/896/submission/32917976)
     78 
     79 [896D — Nephren Runs a Cinema](//codeforces.com/contest/896/problem/D) By [dogther](/profile/dogther "Candidate Master dogther")
     80 
     81 First let's consider a simpler problem that there are no customers with VIP cards and there are no 50-*yuan* notes left. For convinence, we suppose that *n* is an even number. The situation that *n* is an odd number will be similar.
     82 
     83 By defining points (number of customers currently, number of 50-*yuan* note left) on a 2d-plane, the answer to our second question is the ways of drawing lines from (0,0) to (n,0), such that two adjacent points' y-axis have a difference of 1, and that all the points are above the x-axis.
     84 
     85 The total routes will be *C**n**n* / 2, but some of them are invalid. Consider another route starting from (0,-2).
     86 
     87 For each invalid way in the previous route, consider the first point (x,y) that y<0 (y=-1).
     88 
     89 By creating a symmetry route with y=-1 for the route before this point, this route will become exactly one route starting from (0,-2), and every route starting from (0,-2) will become an invalid route in a similar way.
     90 
     91 So the number of invalid routes is *C**n**n* / 2 - 1 (that is the number of routes from (0,-2) to (n,0)). Thus the answer will be *C**n**n* / 2 - *C**n**n* / 2 - 1.
     92 
     93 Similarly if there are [l,r] 50-*yuan* notes left, the answer will be *C**n**n* / 2 - *r* / 2 - *C**n**n* / 2 - *l* / 2 - 1.
     94 
     95 Now let's enumerate how many customers are there with VIP cards. If there are *i* of them, the answer will time a factor *C**n**i*.
     96 
     97 One last question is about the modulo number. First separate it into forms like (*p*1*a*1) * (*p*2*a*2)... where *p*1... are primes. We can calculate how many factor *p**i* are there in (*j*!), and the modulo value of the remaining ones.
     98 
     99 Each time we take out a facter *p**i* in (*j*!), and it becomes some product of numbers that are not divisble by *p**i* as well as a remaining part (*j* / *p**i*)!. For example, we want to calculate the number of factor 3 in (16!), and the product of numbers that are not divisble by 3 in (16!) mod (3^2). Then we have:
    100 
    101 16! = (1 * 2 * 4 * 5 * 7 * 8 * 10 * 11 * 13 * 14 * 16) * (1 * 2 * 3 * 4 * 5) * (3^5)
    102 
    103 The first part are not divisble by 3, so we can calculate their value (mod 3^2) in advance, the second part is a smaller problem (5!), so we can solve it recursively. For the number of factor 3, just add 5 in this case and solve it recursively.
    104 
    105 After calculating how many factor *p**i* in (*j*!) and the modulo value of the remaining ones, we can calculate the combnation numbers correctly. Finally use Chinese Remainder Algorithm to combine them.
    106 
    107 [896E — Welcome home, Chtholly](//codeforces.com/contest/896/problem/E) By [ODT](/profile/ODT "Candidate Master ODT")
    108 
    109 I'm really sorry for letting the brute force algorithm pass the tests...
    110 
    111 My code uses about 600ms, in order to let some algorithms with large constant or larger time complexity ( like ![](https://espresso.codeforces.com/b07604f054399a625303fd7e90960fee85ddfe36.png) ) pass, I set the time limit to 3000ms.
    112 
    113 The most naive brute forces uses about 8000ms to 9000ms, I added some tricks and the fastest can pass the tests in 5600ms.
    114 
    115 In all the contests I've attended, pragma GCC was not allowed to be used...
    116 
    117 But on codeforces, this can optimize brute force algorithm from 5600ms to about 2500ms...
    118 
    119 ![](/predownloaded/86/70/8670a3ea4f7b25a9a7f6eb60e81ba24eac22a75c.png)
    120 
    121 Thanks to [MrDindows](/profile/MrDindows "International Grandmaster MrDindows") and [Shik](/profile/Shik "International Grandmaster Shik") for teaching me this lesson...
    122 
    123 My solution to this problem:
    124 
    125 Split the array into ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) blocks, each containing ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) numbers.
    126 
    127 In each block, for example block *x*, use *f*[*x*][*v*] to represent the number of *v* in block *x*.
    128 
    129 For each number *i*, *belong*[*i*] is the the block that *i* is in.
    130 
    131 We need to maintain each number in the block.
    132 
    133 This can be maintained by using DSU or linked list.
    134 
    135 By maintaining this, we can get the value of every number in a block in ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) time.
    136 
    137 Notice that this two operations are the same:
    138 
    139 1.For every number that is bigger than *x*, decrease it by *x*
    140 
    141 2.Decrease every number by *x*, and for every number that is less than 1, increase it by *x*
    142 
    143 For operation 1:
    144 
    145 We get the value of each number in block *belong*[*l*] and *belong*[*r*] using the DSU or linked list, then for every number that should change, we change them.
    146 
    147 Then we build block *belong*[*l*] and *belong*[*r*] up again.
    148 
    149 For blocks numbered from *belong*[*l*] + 1 to *belong*[*r*] - 1:
    150 
    151 If *x* × 2  ≤  max value in block *p* We merge all the numbers in range [1, *x*] to [*x* + 1, *x* × 2], and add *x* to *tag*[*p*] , *tag*[*p*] means that all the numbers in block *p* has decreased by *tag*[*p*].
    152 
    153 If *x* × 2 ![](https://espresso.codeforces.com/53f45764513797856b9b3b0b917637b2b252e1d5.png) max value in block *p* We merge all the numbers in range [*x* + 1, *maxvalue*] to [1, *maxvalue* - *x*].
    154 
    155 For operation 2:
    156 
    157 We get the value of each number in block *belong*[*l*] and *belong*[*r*] using the DSU or linked list.
    158 
    159 We only need to traverse all the numbers in blocks *belong*[*l*] and *belong*[*r*], and traverse all the blocks between *belong*[*l*] and *belong*[*r*].
    160 
    161 For block *i* in range [*l*, *r*], *f*[*i*][*x* + *tag*[*i*]] is the number of *x* in block *i*, so we just need to add this into the answer
    162 
    163 Proof of time complexity:
    164 
    165 There are ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) blocks.
    166 
    167 The difference between the max number and the min number in each block is initially *n*. So the sum of this in every block is ![](https://espresso.codeforces.com/67f26d6009f546a310a98fbf8147408b75c1862f.png).
    168 
    169 For each operation 1, we use *O*(*x*) time or *O*(*max* - *x*) time to make the difference of max and min element *O*(*x*) or *O*(*max* - *x*) smaller.
    170 
    171 For each operation 2, we traverse ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) numbers and ![](https://espresso.codeforces.com/b6fe01d5e3a5421bdfe09a9587278b0b7c17e786.png) blocks.
    172 
    173 So the total time complexity if ![](https://espresso.codeforces.com/5b130447f22ef8d80bd9c5ed1b20c11c7e8807ae.png)
    174 
    175 There seems to be another algorithm with the same time complexity, and has a smaller constant, but I couldn't prove its complexity so I used this algorithm instead.
    176 
    177 [My solution](//codeforces.com/contest/896/submission/32920862)
    178 
    179 ![](/predownloaded/6e/a1/6ea1f4df654befe2c6f3ad9ae73fb8f692f0f333.png)
    180 
    181 (The missing picture on Div. 1E)
    182 
    183 If you don't like it, just skip it please.