375.md (8924B)
1 Source: https://codeforces.com/blog/entry/10084 2 3 [376A - Lever](/contest/376/problem/A "Codeforces Round 221 (Div. 2)") 4 5 writer: [boleyn.su](/profile/boleyn.su "Master boleyn.su") 6 7 O(n): 8 9 Let mid = position of ^ 10 11 Let value(x) = x if x is a digit , 0 otherwise. 12 13 Let sum = value(i-th char)*(i-mid) 14 15 If sum = 0 then answer = balance 16 17 Else if sum<0 then answer = left 18 19 Else answer = right 20 21 [376B - I.O.U.](/contest/376/problem/B "Codeforces Round 221 (Div. 2)") 22 23 writer: [oGhost](/profile/oGhost "Expert oGhost") 24 25 O(n^4): 26 27 Let f[i][j] = how many money i owes j 28 29 #It can be proved we only need to loop n times. 30 31 Loop n times do: 32 33 ``` 34 For i,j,k in [1..n] 35 36 If f[i][j]>0 and f[j][k]>0 then 37 38 Let delta = min (f[i][j], f[j][k]) 39 40 Decrease f[i][j] and f[j][k] by delta 41 42 Increase f[i][k] by delta 43 ``` 44 45 Answer will be sum{f[i][j]} 46 47 O(m+n): 48 49 Let owe[i] = 0 for all i 50 51 #Suppose there is an agnecy to help people with debts. 52 53 #If you owe someone, you give money to the agency. 54 55 #If someone owes you, you get money from the agency. 56 57 For each ai, bi, ci 58 59 ``` 60 Increase owe[ai] by ci 61 62 Decrease owe[bi] by ci 63 ``` 64 65 Ansewr will be sum{owe[i]|owe[i]>0} 66 67 [375A - Divisible by Seven](/contest/375/problem/A "Codeforces Round 221 (Div. 1)") 68 69 writer: [oGhost](/profile/oGhost "Expert oGhost") 70 71 O(n): 72 73 Because permutation of 1, 6, 8, 9 can form integers that mod 7 equals 0, 1, 2, 3, 4, 5, 6. 74 75 So you can construct answer like this: nonzero digits + a permutation of 1, 6, 8, 9 + zeros. 76 77 [375B - Maximum Submatrix 2](/contest/375/problem/B "Codeforces Round 221 (Div. 1)") 78 79 writer: [oGhost](/profile/oGhost "Expert oGhost") 80 81 O(n*m): 82 83 #We can get right[i][j] by O(n*m) dp. 84 85 Let right[i][j] = how many continuous 1s is on cell (j, i)'s right. 86 87 Let answer = 0 88 89 For all column i 90 91 ``` 92 Sort right[i] #You can use O(n) sorting algorithm 93 94 For j in [1..n] 95 96 If right[i][j]*(n-j+1) > answer then answer = right[i][j]*(n-j+1) 97 ``` 98 99 [375C - Circling Round Treasures](/contest/375/problem/C "Codeforces Round 221 (Div. 1)") 100 101 writer: [whd](/profile/whd "Expert whd") 102 103 #T = number of treasures, B = number of booms 104 105 O(n*m*2^(T+B)): 106 107 #State(i, j, ts, bs) means: 108 109 # 1. You are at cell (i, j) 110 111 # 2. If the i-th bit of ts is 0 i-th treasure cross even edges of current path, otherwise odd edges. 112 113 # 3. If the i-th bit of bs is 0 i-th boom cross even edges of current path, otherwise odd edges. 114 115 Let dis[i][j][ts][bs] = min step to go to reach state (i, j, ts, bs). 116 117 Then we can use bfs algorithm to calculate dis. 118 119 The answer will be max{value(ts) — dis[Si][Sj][ts][0]} 120 121 [375D - Tree and Queries](/contest/375/problem/D "Codeforces Round 221 (Div. 1)") 122 123 writer: [whd](/profile/whd "Expert whd") 124 125 O(nlogn) or O(nlog^2n): 126 127 Use binary search tree and merge them by rank. 128 129 Use binary search tree that supports O(n) merging to get O(nlogn) solution. 130 131 O(n*sqrt(n)): 132 133 Dfs the tree to transform the problem to: 134 135 ``` 136 Given a[i], query [l,r] k. 137 ``` 138 139 To solve this problem: 140 141 ``` 142 Build sqrt(n) bucket, put query [l,r] into (l/sqrt(n)+1)-th bucket 143 144 For each bucket 145 146 For thoese queries whose r is also in the bucket (l/sqrt(n) equals r/sqrt(n)), a brute-froce O(n) solution exists. 147 148 For thoes queries whose r is not in the same bucket, let we sort them by l. We will get l[i[1]]<=l[i[2]]<=..<=l[i[k]]<=r[i[k]]<=r[i[k-1]]<=..<=r[i[1]](do not forget we get l[] and r[] by dfs the tree!). Solving them can be done in O(n) too. 149 150 Since we only have O(sqrt(n)) buckets, the total time is O(n*sqrt(n)). 151 ``` 152 153 [375E - Red and Black Tree](/contest/375/problem/E "Codeforces Round 221 (Div. 1)") 154 155 writer: [boleyn.su](/profile/boleyn.su "Master boleyn.su") 156 157 This problem can be solved by integer programming: 158 159 ``` 160 min sum{c[i]*x[i]} 161 162 subject to 163 164 sum{A[i][j]*x[j]} >= 1 for all i 165 166 sum{x[i]} = R 167 168 x[i] = 0 or 1 for all i 169 170 where 171 172 c[i] = 1 if node i is black, 0 otherwise 173 174 A[i][j] = 1 if distance between i and j is no greater than X, 0 otherwise 175 176 R = number of red nodes. 177 ``` 178 179 As it is known, integer programming is NP-hard. 180 181 Thus, this cannot be the solution. 182 183 But we can prove the following linear programing's solution is same as the integer programming's. 184 185 ``` 186 min sum{c[i]*x[i]} 187 188 subject to 189 190 sum{A[i][j]*x[j]} >= 1 for all i 191 192 sum{x[i]} <= R 193 194 x[i] >= 0 for all i 195 196 where 197 198 c[i] = 1 if node i is black, 0 otherwise 199 200 A[i][j] = 1 if distance between i and j is no greater than X, 0 otherwise 201 202 R = number of red nodes. 203 ``` 204 205 And the known fastest algorithm to solve linear programming is O(n^3.5). 206 207 But in fact due to the property of this problem, using simplex algorithm to solve linear programming is even faster. I think it can be O(n^3), but I have no proof. 208 209 So just use simplex to solve the linear programming problem above. 210 211 **The tutorial is not finished yet. More details will be added later.** 212 213 **UPD** 214 215 Thanks to Codeforces users, a lot of details supposed to be added can be found in comments. I am adding something that is not clearly explained in the comments or something that I want to share with you. 216 217 Div1C: 218 219 There are few questions about this one. So I am explaining it more clearly. 220 221 #State(i, j, ts, bs) means: 222 223 # 1. You are at cell (i, j) 224 225 # 2. If the i-th bit of ts is 0 i-th treasure cross even edges of current path, otherwise odd edges. 226 227 # 3. If the i-th bit of bs is 0 i-th boom cross even edges of current path, otherwise odd edges. 228 229 Let dis[i][j][ts][bs] = min step to go to reach state (i, j, ts, bs). 230 231 Then we can use bfs algorithm to calculate dis. 232 233 About the bfs algorithm: 234 235 ``` 236 We know dis[Si][Sj][0][0] = 0. 237 238 For state(i, j, bs, ts) we can goto cell (i-1, j), (i+1, j), (i, j-1) and (i, j+1). Of course, we cannot go out of the map or go into a trap. So suppose we go from cell (i, j) to cell (ni, nj) and the new state is (ni, nj, nts, nbs). We can see if a treasure is crossing through the edge (i, j) - (ni, nj), if i-th treasure is, then the i-th bit of nts will be 1 xor i-th bit of ts, otherwise, the i-th bit of nts and ts will be same. The same for nbs. 239 240 We can reach state (ni, nj, nts, nbs) from (i, j, ts, bs) in one step, so we just need to start bfs from state(Si, Sj, 0, 0) to get the min dis of all state. 241 ``` 242 243 The answer will be max{value(ts) — dis[Si][Sj][ts][0]} 244 245 My submission: [5550863](/contest/375/submission/5550863 "Submission 5550863 by ruc_acme") 246 247 Div1D: 248 249 To our surprise, there seems to be many different solutions to Div1D, which is very good. In fact, we thought about changing this problem so that only online algorithm will be accepted, but we didn't have much time to change it. I guess if we only accept online algorithm, the problem will be less interesting becasue we might not have so many different solutions. So, not changing it is a good decision. 250 251 However, it may(some solution is hard to change to solve the online-version, so I use 'may') be quite simple to solve the online-version of this problem if you have solved the offline-version. You just need to use persistent data structure when implementing binary search trees. You can get more detail from [wiki](https://en.wikipedia.org/wiki/Persistent_data_structure). 252 253 Div1E: 254 255 The meaning of the integer programming: 256 257 ``` 258 We use x[i] to stand whether node i is red or not. So we have: 259 260 x[i] = 0 or 1 for all i 261 262 There is a beautiful tree, for each node, exists an red node whose distance to this node is no more than X. So we have: 263 264 sum{A[i][j]*x[j]} >= 1 for all i 265 266 There are only R red node. So we have: 267 268 sum{x[i]} = R 269 270 And we need to minimize the swap number, and in fact the swap number equals to number of nodes that changed from black to red. So we need to minimize: 271 272 sum{c[i]*x[i]} 273 ``` 274 275 After changing it to linear programming: 276 277 ``` 278 Firstly, it is obvious that the solution of the linear programming will not be worse than integer programming, because integer programming has stronger constraint. 279 280 So we only need to show the solution of the linear programming will not be better than integer programming. 281 282 To prove this, we need to show for an optimal solution, there will be an solution which is as good as it and all x[i] is either 0 or 1. 283 284 1. Because for "sum{A[i][j]*x[j]} >= 1 for all i", there is no need to make some x[i] > 1. It is obvious that if the solution has some x[i] > 1, we can increase x[i] for nodes that are red in the first place, so that there will not be any x[i] > 1 and this solution is as good as the old one. 285 286 2. We need to prove in an optimal solution, making some x[i] not being an integer will not get btter solution. It is really hard to decribe it. So just leave you a hint: use the property of trees to prove and consider leaves of the tree. 287 ``` 288 289 My submission: [5523033](/contest/375/submission/5523033 "Submission 5523033 by ruc_acme") 290 291 There is a nice DP solution too, check this submission [5516578](/contest/375/submission/5516578 "Submission 5516578 by Touma_Kazusa") by [Touma_Kazusa](/profile/Touma_Kazusa "Candidate Master Touma_Kazusa").