652.md (14168B)
1 Source: https://codeforces.com/blog/entry/43986 2 3 ### [652A - Gabriel and Caterpillar](/contest/652/problem/A "Educational Codeforces Round 10") 4 5 The problem was suggested by [unprost](/profile/unprost "Expert unprost"). 6 7 Let's consider three cases. 8 9 1. *h*1 + 8*a* ≥ *h*2 — in this case the caterpillar will get the apple on the same day, so the answer is 0. 10 2. The first condition is false and *a* ≤ *b* — in this case the caterpillar will never get the apple, because it can't do that on the first day and after each night it will be lower than one day before. 11 3. If the first two conditions are false easy to see that the answer equals to . 12 13 **C++ solution** 14 15 ``` 16 int h1, h2; 17 int a, b; 18 19 bool read() { 20 return !!(cin >> h1 >> h2 >> a >> b); 21 } 22 23 void solve() { 24 if (h1 + 8 * a >= h2) 25 puts("0"); 26 else if (a > b) { 27 int num = h2 - h1 - 8 * a, den = 12 * (a - b); 28 cout << (num + den - 1) / den << endl; 29 } else 30 puts("-1"); 31 } 32 ``` 33 34 Also this problem can be solved by simple modelling, because the heights and speeds are small. 35 36 Complexity: *O*(1). 37 38 ### [652B - z-sort](/contest/652/problem/B "Educational Codeforces Round 10") 39 40 The problem was suggested by [Smaug](/profile/Smaug "Pupil Smaug"). 41 42 Easy to see that we can *z*-sort any array *a*. Let  be the number of even positions in *a*. We can assign to those positions *k* maximal elements and distribute other *n* - *k* elements to odd positions. Obviously the resulting array is *z*-sorted. 43 44 **C++ solution** 45 46 ``` 47 const int N = 1010; 48 49 int n, a[N]; 50 51 bool read() { 52 if (!(cin >> n)) return false; 53 forn(i, n) assert(scanf("%d", &a[i]) == 1); 54 return true; 55 } 56 57 int ans[N]; 58 59 void solve() { 60 sort(a, a + n); 61 62 int p = 0, q = n - 1; 63 forn(i, n) 64 if (i & 1) ans[i] = a[q--]; 65 else ans[i] = a[p++]; 66 assert(q + 1 == p); 67 68 forn(i, n) { 69 if (i) putchar(' '); 70 printf("%d", ans[i]); 71 } 72 puts(""); 73 } 74 ``` 75 76 Complexity: *O*(*nlogn*). 77 78 ### [652C - Foe Pairs](/contest/652/problem/C "Educational Codeforces Round 10") 79 80 This is one of the problems suggested by Bayram Berdiyev [bayram](/profile/bayram "Expert bayram"), Allanur Shiriyev [Allanur](/profile/Allanur "Expert Allanur"), Bekmyrat Atayev [Bekmyrat.A](/profile/Bekmyrat.A "Expert Bekmyrat.A"). 81 82 Let's precompute for each value *x* its position in permutation *pos**x*. It's easy to do in linear time. Consider some foe pair (*a*, *b*) (we may assume *pos**a* < *pos**b*). Let's store for each value *a* the leftmost position *pos**b* such that (*a*, *b*) is a foe pair. Denote that value as *z**a*. Now let's iterate over the array *a* from right to left and maintain the position *rg* of the maximal correct interval with the left end in the current position *lf*. To maintain the value *rg* we should simply take the minimum with the value *z*[*lf*]: *rg* = *min*(*rg*, *z*[*lf*]). And finally we should increment the answer by the value *rg* - *lf* + 1. 83 84 **C++ solution** 85 86 ``` 87 const int N = 300300; 88 89 int n, m; 90 int p[N]; 91 pt b[N]; 92 93 bool read() { 94 if (!(cin >> n >> m)) return false; 95 forn(i, n) { 96 assert(scanf("%d", &p[i]) == 1); 97 p[i]--; 98 } 99 forn(i, m) { 100 int x, y; 101 assert(scanf("%d%d", &x, &y) == 2); 102 x--, y--; 103 b[i] = pt(x, y); 104 } 105 return true; 106 } 107 108 int pos[N]; 109 vector<int> z[N]; 110 111 void solve() { 112 forn(i, n) pos[p[i]] = i; 113 forn(i, n) z[i].clear(); 114 forn(i, m) { 115 int x = pos[b[i].x], y = pos[b[i].y]; 116 if (x > y) swap(x, y); 117 z[x].pb(y); 118 } 119 120 li ans = 0; 121 int rg = n; 122 nfor(i, n) { 123 forn(j, sz(z[i])) rg = min(rg, z[i][j]); 124 ans += rg - i; 125 } 126 cout << ans << endl; 127 } 128 ``` 129 130 Complexity: *O*(*n* + *m*). 131 132 ### [652D - Nested Segments](/contest/652/problem/D "Educational Codeforces Round 10") 133 134 The problem was suggested by Alexey Dergunov [dalex](/profile/dalex "Candidate Master dalex"). 135 136 This problem is a standard two-dimensional problem that can be solved with one-dimensional data structure. In the same way a lot of other problems can be solved (for example the of finding the maximal weighted chain of points so that both coordinates of each point are greater than the coordinates of the predecessing point). Rewrite the problem formally: for each *i* we should count the number of indices *j* so that the following conditions are hold: *a**i* < *a**j* and *b**j* < *a**j*. Let's sort all segments by the left ends from right to left and maintain some data structure (Fenwick tree will be the best choice) with the right ends of the processed segments. To calculate the answer for the current segment we should simple take the prefix sum for the right end of the current segment. 137 138 So the condition *a**i* < *a**j* is hold by sorting and iterating over the segments from the right to the left (the first dimension of the problem). The condition *b**j* < *a**j* is hold by taking the prefix sum in data structure (the second dimension). 139 140 **C++ solution** 141 142 ``` 143 const int N = 1200300; 144 145 int n; 146 pair<pti, int> a[N]; 147 148 bool read() { 149 if (!(cin >> n)) return false; 150 forn(i, n) assert(scanf("%d%d", &a[i].x.x, &a[i].x.y) == 2), a[i].y = i; 151 return true; 152 } 153 154 int t[N]; 155 vector<int> ys; 156 157 inline void inc(int i, int val) { 158 for ( ; i < sz(ys); i |= i + 1) 159 t[i] += val; 160 } 161 162 inline int sum(int i) { 163 int ans = 0; 164 for ( ; i >= 0; i = (i & (i + 1)) - 1) 165 ans += t[i]; 166 return ans; 167 } 168 169 int ans[N]; 170 171 void solve() { 172 ys.clear(); 173 forn(i, n) ys.pb(a[i].x.y); 174 sort(all(ys)); 175 ys.erase(unique(all(ys)), ys.end()); 176 forn(i, sz(ys)) t[i] = 0; 177 178 sort(a, a + n); 179 nfor(i, n) { 180 int idx = int(lower_bound(all(ys), a[i].x.y) - ys.begin()); 181 ans[a[i].y] = sum(idx); 182 inc(idx, +1); 183 } 184 185 forn(i, n) printf("%dn", ans[i]); 186 } 187 ``` 188 189 Complexity: *O*(*nlogn*). 190 191 ### [652E - Pursuit For Artifacts](/contest/652/problem/E "Educational Codeforces Round 10") 192 193 The problem was suggested by Alexey Dergunov [dalex](/profile/dalex "Candidate Master dalex"). 194 195 Edge biconnected component in an undirected graph is a maximal by inclusion set of vertices so that there are two edge disjoint paths between any pair of vertices. Consider the graph with biconnected components as vertices. Easy to see that it's a tree (if it contains some cycle then the whole cycle is a biconnected component). All edges are destroying when we passing over them so we can't returnto the same vertex (in the tree) after leaving it by some edge. 196 197 Consider the biconncted components that contains the vertices *a* and *b*. Let's denote them *A* and *B*. Statement: the answer is *YES* if and only if on the path in the tree from the vertex *A* to the vertex *B* there are an edge with an artifact or there are a biconnected component that contains some edge with an artifact. Easy to see that the statement is true: if there are such edge then we can pass over it in the tree on the path from *A* to *B* or we can pass over it in biconnected component. The converse also easy to check. 198 199 Here is one of the ways to find edge biconnected components: 200 201 1. Let's orient all edges to direction that depth first search passed it for the first time. 202 2. Let's find in new directed graph strongly connected components. 203 204 Statement: the strongly connected components in the new graph coincide with the biconnected components in old undirected graph. 205 206 Also you can notice that the edges in tree is the bridges of the graph (bridges in terms of graph theory). So you can simply find the edges in the graph. 207 208 **Not too short C++ solution** 209 210 const int N = 500500, M = 500500; 211 212 int n, m; int eused[M]; vector eid[N]; vector g1[N], tg1[N]; vector w[N]; int a, b; 213 214 bool read() { if (!(cin >> n >> m)) return false; forn(i, m) eused[i] = false; forn(i, n) { g1[i].clear(); tg1[i].clear(); eid[i].clear(); w[i].clear(); } forn(i, m) { int x, y, z; assert(scanf("%d%d%d", &x, &y, &z) == 3); x--, y--; g1[x].pb(y); g1[y].pb(x); eid[x].pb(i); eid[y].pb(i); w[x].pb(z); w[y].pb(z); } assert(cin >> a >> b); a--, b--; return true; } 215 216 int u, used[N]; int sz, perm[N]; 217 218 void dfs1(int v) { used[v] = u; forn(i, sz(g1[v])) { int u = g1[v][i]; int cid = eid[v][i]; if (!eused[cid]) { eused[cid] = true; tg1[u].pb(v); } if (used[u] != ::u) dfs1(u); } perm[sz++] = v; } 219 220 int c, comp[N]; 221 222 void dfs2(int v) { used[v] = u; for (auto u : tg1[v]) if (used[u] != ::u) dfs2(u); comp[v] = c; } 223 224 vector g2[N]; vector w2[N]; 225 226 bool good[N]; 227 228 bool dfs3(int v, int p, int t, bool& ans) { if (v == t) { ans |= good[v]; return true; } 229 230 ``` 231 forn(i, sz(g2[v])) { 232 int to = g2[v][i]; 233 if (to == p) continue; 234 if (dfs3(to, v, t, ans)) { 235 ans |= good[v]; 236 ans |= w2[v][i]; 237 return true; 238 } 239 } 240 return false; 241 ``` 242 243 } 244 245 void solve() { u++, sz = 0; dfs1(0); assert(sz == n); reverse(perm, perm + sz); 246 247 ``` 248 u++, c = 0; 249 forn(i, sz) if (used[perm[i]] != u) dfs2(perm[i]), c++; 250 251 forn(i, c) good[i] = false; 252 253 forn(i, c) { 254 g2[i].clear(); 255 w2[i].clear(); 256 } 257 forn(i, n) 258 forn(j, sz(g1[i])) { 259 int x = comp[i], y = comp[g1[i][j]]; 260 if (x != y) { 261 g2[x].pb(y); 262 w2[x].pb(w[i][j]); 263 } else if (w[i][j]) good[x] = true; 264 } 265 266 n = c; 267 a = comp[a], b = comp[b]; 268 269 bool ans = good[a]; 270 assert(dfs3(a, -1, b, ans)); 271 puts(ans ? "YES" : "NO"); 272 ``` 273 274 } 275 276 Complexity: *O*(*n* + *m*). 277 278 ### [652F - Ants on a Circle](/contest/652/problem/F "Educational Codeforces Round 10") 279 280 The problem was suggested by Lewin Gan [Lewin](/profile/Lewin "International Master Lewin"). 281 282 The first observation: if all the ants are indistinguishable we can consider that there are no collisions and all the ants are passing one through another. So we can easily determine the final positions of all the ants, but we can't say which ant will be in which position. 283 284 The second observation: the relative order of the ants will be the same all the time. 285 286 So to solve the problem we should only find the position of one ant after *t* seconds. 287 288 Let's solve that problem in the following way: 289 290 1. Consider the positions of all the ants after *m* time units. Easy to see that by the first observation all the positions of the ants will left the same, but the order will be different (we will have some cyclic shift of the ants). If we find that cyclic shift *sh* we can apply it  times. 291 2. After that we will have only *t* ± *od* *m* time units. 292 293 So the problem now is to model the process for the one ant with *m* and *r* ± *od* *m* time units. Note that in that time interval the fixed ant will have no more than two collisions with each other ant. So if we model the process with ignoring all collisions except the ones that include the fixed ant, we will have no more than 2*n* collisions. 294 295 Let's model that process with two queues for the ants going to the left and to the right. Each time we should take the first ant in the queue with opposite direction, process the collision and add that ant to the end of the other queue. 296 297 Hint: you will have a problem when the fixed ant can be in two different positions at the end, but it's easy to fix with doing the same with the next ant. 298 299 **C++ solution** 300 301 const int N = 300300; 302 303 int n, m; li t; pair<pair<int, char>, int> a[N]; 304 305 bool read() { if (!(cin >> n >> m >> t)) return false; forn(i, n) { assert(scanf("%d %c", &a[i].x.x, &a[i].x.y) == 2); a[i].x.x--; a[i].y = i; } return true; } 306 307 int dx[] = { -1, +1 }; const string dirs("LR"); inline int getDir(char d) { return (int) dirs.find(d); } 308 309 inline int getPos(li x, char d, li t) { x %= m, t %= m; li ans = (x + t * dx[getDir(d)]) % m; (ans < 0) && (ans += m); return int(ans); } 310 311 typedef pair<li, li> ptl; void clear(queue& q) { while (!q.empty()) q.pop(); } queue tol, tor; 312 313 int calc(int v, li t) { clear(tol); clear(tor); 314 315 ``` 316 fore(d, 1, n) { 317 int i = (v - d + n) % n; 318 if (a[i].x.y == 'R') tor.push(mp(i > v ? a[i].x.x - m : a[i].x.x, 0)); 319 } 320 fore(d, 1, n) { 321 int i = (v + d) % n; 322 if (a[i].x.y == 'L') tol.push(mp(i < v ? a[i].x.x + m : a[i].x.x, 0)); 323 } 324 325 li cx = a[v].x.x; 326 char cd = a[v].x.y; 327 li curt = 0; 328 while (t > 0) { 329 if (cd == 'R') { 330 if (tol.empty()) return getPos(cx, cd, t); 331 assert(curt >= tol.front().y); 332 li nx = tol.front().x - (curt - tol.front().y); 333 tol.pop(); 334 li d = min((nx - cx + 1) >> 1, t); 335 assert(cx <= nx); 336 cx += d, nx -= d; 337 t -= d; 338 if (cx > nx) { 339 assert((nx - cx) & 1); 340 cx--, nx++; 341 } 342 assert(cx <= nx); 343 cd = 'L'; 344 curt += d; 345 assert(nx - m < cx); 346 tor.push(mp(nx - m, curt)); 347 } else { 348 if (tor.empty()) return getPos(cx, cd, t); 349 assert(curt >= tor.front().y); 350 li nx = tor.front().x + (curt - tor.front().y); 351 tor.pop(); 352 li d = min((cx - nx + 1) >> 1, t); 353 assert(cx >= nx); 354 cx -= d, nx += d; 355 t -= d; 356 if (cx < nx) { 357 assert((cx - nx) & 1); 358 cx++, nx--; 359 } 360 assert(cx >= nx); 361 cd = 'R'; 362 curt += d; 363 assert(nx + m > cx); 364 tol.push(mp(nx + m, curt)); 365 } 366 } 367 return getPos(cx, cd, 0); 368 ``` 369 370 } 371 372 int ans[N]; 373 374 void solve() { assert(n > 1); sort(a, a + n); 375 376 ``` 377 vector<int> poss; 378 forn(i, n) 379 poss.pb(getPos(a[i].x.x, a[i].x.y, t)); 380 sort(all(poss)); 381 382 vector<vector<int>> xs; 383 forn(s, 2) { 384 int x = calc(s, m); 385 int pos = -1; 386 forn(i, n) 387 if (a[i].x.x == x) { 388 assert(pos == -1); 389 pos = i; 390 } 391 assert(pos != -1); 392 pos = (pos - s + n) % n; 393 li k = (t / m) % n; 394 pos = int((s + pos * k) % n); 395 396 x = calc(pos, t % m); 397 xs.pb(vector<int>()); 398 forn(i, sz(poss)) 399 if (poss[i] == x) 400 xs.back().pb(i); 401 assert(!xs.back().empty()); 402 if (sz(xs.back()) == 2) assert(xs.back()[0] + 1 == xs.back()[1]); 403 } 404 405 int pos = xs[0][0]; 406 if (sz(xs[0]) > 1) { 407 assert(sz(xs[0]) == 2); 408 assert(pos + 1 == xs[0][1]); 409 if (xs[0] != xs[1]) 410 pos = xs[0][1]; 411 } 412 413 forn(ii, n) { 414 int i = (ii + pos) % sz(poss); 415 ans[a[ii].y] = poss[i]; 416 } 417 418 forn(i, n) { 419 if (i) putchar(' '); 420 assert(0 <= ans[i] && ans[i] < m); 421 printf("%d", ans[i] + 1); 422 } 423 puts(""); 424 ``` 425 426 } 427 428 Complexity: *O*(*nlogn*).