codeforces-scrape

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

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").