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  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  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 , 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 . 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  , 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  ) 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  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  blocks, each containing  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  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  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  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 . 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  numbers and  blocks. 172 173 So the total time complexity if  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  180 181 (The missing picture on Div. 1E) 182 183 If you don't like it, just skip it please.