codeforces-scrape

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

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 ![](https://espresso.codeforces.com/2d404e937d5e8ae30de453cf189d7169caf634c9.png).
     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 ![](https://espresso.codeforces.com/2b0780f524505b9bb2ec7f5805c56a0da274c900.png) 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 ![](https://espresso.codeforces.com/ed8dd0dfd126a8bba5a7c42603a04802e0bc5682.png) 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*).