398.md (13915B)
1 Source: https://codeforces.com/blog/entry/10686 2 3 Please write here if you had written some comments about any suggestions or questions on the announcement. There are a bunch of notification emails but I couldn't read most of them :( 4 5 Here are the final top 100 : [Div1](https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQIDAA&url=http%3A%2F%2Fwebcache.googleusercontent.com%2Fsearch%3Fq%3Dcache%3A1RF3QO-_JXoJ%3Acodeforces.com%2Fcontest%2F398%2Fstandings%2B%26cd%3D1%26hl%3Dko%26ct%3Dclnk%26gl%3Dkr&ei=u6YUU9-HGYXEkgWNqIHICA&usg=AFQjCNFkij08MpvPcSG2HI4LDa_FK0COLA&sig2=RI29yARCrh2DimTBQSmfGw&bvm=bv.61965928,d.dGI), [Div2](https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC0QIDAA&url=http%3A%2F%2Fwebcache.googleusercontent.com%2Fsearch%3Fq%3Dcache%3ARm3K-hziD8QJ%3Acodeforces.com%2Fcontest%2F399%2Fstandings%2B%26cd%3D1%26hl%3Dko%26ct%3Dclnk%26gl%3Dkr&ei=sKYUU6-KFMbQlAXtzIHABQ&usg=AFQjCNHwmP4LqOrHIo0ELTh9cXnhmY0jWw&sig2=5lJH4564SjPuel1PElvTdQ&bvm=bv.61965928,d.dGI). Congrats to the winners! 6 7 (These links are all from google search cache, so it may be disappear) 8 9 --- 10 11 First of all, we are sorry to make this round unrated. This is an unexpected incident, and I believe that everyone in Codeforces would understand that. And second, we're sorry for estimating the difficulties of the problems wrong. 12 13 * Actually, I thought that somebody would get Accepted on [398A - Cards](/contest/398/problem/A "Codeforces Round 233 (Div. 1)") within 5 minutes. But there wasn't any submissions during the first 4 minutes, and many people got wrong answer on pretests! I think almost everybody who solved this got at least one wrong answer.. I'm really sorry for measuring A easy. I think what [cgy4ever](/profile/cgy4ever "International Master cgy4ever") said is right — it would be better not asking to print the sequence. 14 * At first, I purposed [398C - Tree and Array](/contest/398/problem/C "Codeforces Round 233 (Div. 1)") as B(!!) because ainta solved it very easily than I expected. (I could hardly solve this, and thought it must be at least D, before I heard [ainta](/profile/ainta "Master ainta")'s solution.) We're sorry for giving this problem the same score with [398B - Painting The Wall](/contest/398/problem/B "Codeforces Round 233 (Div. 1)"), which was much easier than [398C - Tree and Array](/contest/398/problem/C "Codeforces Round 233 (Div. 1)"). Next time I'll remember that [ainta](/profile/ainta "Master ainta") is really a genius :) 15 * Congrats to four people who solved [398C - Tree and Array](/contest/398/problem/C "Codeforces Round 233 (Div. 1)") during the contest! : [cgy4ever](/profile/cgy4ever "International Master cgy4ever"), [Shef](/profile/Shef "International Master Shef"), [SillyHook06](/profile/SillyHook06 "International Master SillyHook06"), and [Qwaz](/profile/Qwaz "Candidate Master Qwaz"). 16 * We are surprised that [Petr](/profile/Petr "International Grandmaster Petr") solved [398E - Sorting Permutations](/contest/398/problem/E "Codeforces Round 233 (Div. 1)") during the contest! Even though he implemented by Java, his solution is faster than ours :p Congratulations to him! 17 * Actually, we purposed an another problem for Div1-E, but the same problem popped out at OpenCup last Sunday, so we couldn't use that. Thanks to [Gerald](/profile/Gerald "Master Gerald"), who helped us preparing a new problem in such a short time. By the way, can you guess what problem was that? :D 18 * ... 19 20 --- 21 22 #### [399A - Pages](/contest/399/problem/A "Codeforces Round 233 (Div. 2)") — Author : [.o.](/profile/.o. "Grandmaster .o.") 23 24 You can solve this problem by just following the statement. First, print `<<` if *p* - *k* > 1. Next, iterate all the integers from *p* - *k* to *p* + *k*, and print if the integer is in [1..*n*]. Finally, print `>>` if *p* + *k* < *n*. 25 26 * Time complexity: *O*(*n*). 27 * Code : [5926588](/contest/399/submission/5926588 "Submission 5926588 by .o.") 28 29 #### [399B - Red and Blue Balls](/contest/399/problem/B "Codeforces Round 233 (Div. 2)") — Author : [xtalclr](/profile/xtalclr "Master xtalclr") 30 31 Change the blue balls to bit 1, and blue balls to bit 0. Interpret the stack as an integer represented in binary digits. Now, one may see that a single operation decreases the integer by 1, and will be unavailable iff the integer becomes zero. So the answer will be 2*a*1 + 2*a*2 + ... + 2*a**k* where the (*a**i* + 1)-th (1 ≤ *i* ≤ *k*) ball is blue in the beginning. 32 33 * Time complexity: *O*(*n*) 34 * Code : [5926598](/contest/399/submission/5926598 "Submission 5926598 by .o.") 35 36 #### [398A - Cards](/contest/398/problem/A "Codeforces Round 233 (Div. 1)") — Author : [.o.](/profile/.o. "Grandmaster .o.") 37 38 Let the number of `o` blocks *p*, and the number of `x` blocks *q*. It is obvious that |*p* - *q*| ≤ 1 and *p*, *q* ≤ *n*. So we can just iterate all *p* and *q*, and solve these two problems independently, and merge the answer. 39 40 1. Maximize the value of *x*12 + *x*22 + ... + *x**p*2 where *x*1 + *x*2 + ... + *x**p* = *a* and *x**i* ≥ 1. 41 42 * Assign *a* - *p* + 1 to *x*1, and assign 1 to *x*2, *x*3, ..., *x**p*. 43 * The value is (*a* - *p* + 1)2 + (*p* - 1). 44 45 2. Minimize the value of *y*12 + *y*22 + ... + *y**q*2 where *y*1 + *y*2 + ... + *y**q* = *b* and *y**i* ≥ 1. 46 47 * For all , assign  to *y**i*. 48 * For all , assign  to *y**j*. 49 * The value is . 50 51 The proof is easy, so I won't do it. With this, we can solve the problem. We can print *y*1 `x`s, and then *x*1 `o`s, ... 52 53 * Time complexity: *O*(*n*). 54 * Code : [5926607](/contest/398/submission/5926607 "Submission 5926607 by .o.") 55 * Bonus: Is there any solution faster than *O*(*n*)? We tried to use ternary search, but we couldn't prove that was correct. 56 57 #### [398B - Painting The Wall](/contest/398/problem/B "Codeforces Round 233 (Div. 1)") — Author : [ainta](/profile/ainta "Master ainta") 58 59 This can be solved by dynamic programming. Let *T*[*i*, *j*] the expected time when *i* rows and *j* columns doesn't have any painted cells inside. 60 61 Let's see all the cases. If we carefully rearrange the order of rows and columns, we can divide the wall into 4 pieces. 62 63  64 65 1. Choose a cell in rectangle 1. The size of this rectangle is *i* × *j*. The expectation value is *T*[*i* - 1, *j* - 1]. 66 2. Choose a cell in rectangle 2. The size of this rectangle is *i* × (*n* - *j*). The expectation value is *T*[*i* - 1, *j*]. 67 3. Choose a cell in rectangle 3. The size of this rectangle is (*n* - *i*) × *j*. The expectation value is *T*[*i*, *j* - 1]. 68 4. Choose a cell in rectangle 4. The size of this rectangle is (*n* - *i*) × (*n* - *j*). The expectation value is *T*[*i*, *j*]. 69 70 Merging these four cases, we can get: 71 72 *T*[*i*, *j*] = 1 + {*T*[*i* - 1, *j* - 1] × *i* × *j* + *T*[*i* - 1, *j*] × *i* × (*n* - *j*) + *T*[*i*, *j* - 1] × (*n* - *i*) × *j* + *T*[*i*, *j*] × (*n* - *i*) × (*n* - *j*)} / *n*2 73 74 Moving the *T*[*i*, *j*] on the right to the left, we can get the formula which can be used to calculate the value *T*[*i*, *j*]. There are some corner cases, like *i* = 0 or *j* = 0, but it can be simply handled. 75 76 * Time complexity: *O*(*n*2) 77 * Code : [5926617](/contest/398/submission/5926617 "Submission 5926617 by .o.") 78 79 #### [398C - Tree and Array](/contest/398/problem/C "Codeforces Round 233 (Div. 1)") — Author : [.o.](/profile/.o. "Grandmaster .o.") 80 81 There are two intended solutions. One is easy, and the other is quite tricky. 82 83 **Easy Solution** 84 85 Make a tree by the following method. 86 87 * For all , make an edge between vertex *i* and  with weight 1. 88 * For all , make an edge between vertex *i* and *i* + 1 with weight . 89 90 You can see that  are all good pairs. In addition, (1, 3) is also a good pair. So we can print the answer. 91 92 But, if *n* = 5, this method doesn't work because (1, 3) is not a good pair. In this case, one may solve by hand or using random algorithm. 93 94 * Time complexity: *O*(*n*) 95 * Code: [5926624](/contest/398/submission/5926624 "Submission 5926624 by .o.") 96 * Bonus I: Is there any method to make more than  good pairs? 97 * Bonus II: Is there any method that the maximum weight is relatively small and make at least  good pairs? 98 99 **Tricky Solution** 100 101 If you got stuck with the problem, one can run any random algorithm that solves small cases, and merge these cases. With this approach, we can even limit the weight to a very small constant! 102 103 But I think this is not a good solution, so I won't mention about unless anybody wants to know the details. I came up with this solution, and tried to purpose this as D. It seems all the 6 people who passed pretests during the contest didn't use this solution :) 104 105 * Time complexity: ??? 106 * Code : [5926632](/contest/398/submission/5926632 "Submission 5926632 by .o.") 107 108 #### [398D - Instant Messanger](/contest/398/problem/D "Codeforces Round 233 (Div. 1)") — Author : [.o.](/profile/.o. "Grandmaster .o.") 109 110 Let *x**i* an integer representing the state of the i-th user. If user i is online, *x**i* = 1, otherwise, *x**i* = 0. Also, let *S**i* the set consisting of i-th friends. 111 112 One can see that the queries become like this: 113 114 * Online/Offline: change the value of *x**i* to 1 - *x**i*. 115 * Add: add *u* to set *S**v*, and *v* to set *S**u*. 116 * Delete: delete *u* from set *S**v*, *v* from set *S**u*. 117 * Count: calculate . 118 119 Let's use sqrt-decomposition to perform these queries. Let user *u* *heavy* if |*S**u*| ≥ *C*, or *light* otherwise. Also, we will define some arrays and sets: 120 121 * *H**u* is a set that stores friends with user *u* who are heavy users. 122 * *O*[*u*] stores the sum of . 123 124 If the Online/Offline(*u*) query is given, 125 126 * If *u* is a light user: for all , change the value of *O*[*v*]. It takes *O*(|*S**u*|) time. 127 * Otherwise: just update the state of itself. 128 129 If the Add(*u*, *v*) query is given, 130 131 * If vertex *u* becomes heavy if we add this edge, for all , add *v* into *H**w* and update the value of *O*[*w*]. This can be done in *O*(*C*). 132 * If vertex *u* is still light even if we add the edge, update *O*[*v*]. This can be done in constant time. 133 * If vertex *u* is heavy (after the operations above), update *H**v*. 134 * Add *u* to set *S**v*, and *v* to set *S**u*. 135 136 If the Delete(*u*, *v*) query is given, 137 138 * Delete *u* from set *S**v*, and *v* from set *S**u*. 139 * Update the value of *O*[*], *H**u* and *H**v*. Because for all |*H**w*| ≤ *E*| / *C*, this can be done in *O*(|*E*| / *C*). 140 141 If the counting query is given,  will be the answer. Because |*H**u*| ≤ |*E*| / *C*, it will take *O*(|*E*| / *C*) time. 142 143 So for each query, *O*(|*E*| / *C*) or *O*(*C*) time is required. To minimize the time, . 144 145 * Time complexity:  146 * Code : [5926635](/contest/398/submission/5926635 "Submission 5926635 by .o.") 147 148 We can also solve this by dividing the queries into  parts. For each block, use *O*(*n* + *m* + *q*) time to build the online & offline state and the answer table for each vertices. For each query, you can use  time to get the answer. If you want more details, please ask in the comments. 149 150 * Time complexity:  151 * Code : [5926640](/contest/398/submission/5926640 "Submission 5926640 by .o.") 152 153 #### [398E - Sorting Permutations](/contest/398/problem/E "Codeforces Round 233 (Div. 1)") — Author : [xtalclr](/profile/xtalclr "Master xtalclr"), [eyTns](/profile/eyTns "Expert eyTns"), and great help of [Gerald](/profile/Gerald "Master Gerald") 154 155 [Here](//codeforces.com/blog/entry/11108) is the draft solution. 156 157 --- 158 159 Feel free to ask of or discuss about the solutions! Unfortunately, I don't know how to read or write Russian, so if you ask me in Russian, I can't response to it. (also, I think the Russian editorial won't be available..) Sorry for that.