codeforces-scrape

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

1899.md (13599B)


      1 Source: https://codeforces.com/blog/entry/122407
      2 
      3 [1899A — Game with Integers](https://codeforces.com/contest/1899/problem/A)
      4 
      5 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), development: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX").
      6 
      7 **Editorial**
      8 
      9 Consider the remainder from dividing $n$ by $3$ before the first move. If it is equal to $1$ or $2$, then Vanya can make the number $n$ divisible by $3$ after the first move, i.e. he wins. Let the remainder be $0$, then Vanya must change the number after which it will not be divisible by $3$. Then Vova can do the same operation as Vanya and make it divisible by $3$ again. This will go on indefinitely, so Vova wins.
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 void solve() {
     19     int n;
     20     cin >> n;
     21     if (n % 3) {
     22         cout << "First\n";
     23     } else {
     24         cout << "Second\n";
     25     }
     26 }
     27  
     28 int main() {
     29     int t;
     30     cin >> t;
     31     while (t--) {
     32         solve();
     33     }
     34 }
     35 ```
     36 
     37 [1899B — 250 Thousand Tons of TNT](https://codeforces.com/contest/1899/problem/B)
     38 
     39 Idea: [zwezdinv](/profile/zwezdinv "Grandmaster zwezdinv"), development: [zwezdinv](/profile/zwezdinv "Grandmaster zwezdinv").
     40 
     41 **Editorial**
     42 
     43 Solution #1:
     44 
     45 Since $k$ is a divisor of $n$, there are $O(\sqrt[3]{n})$ such $k$. We can enumerate all k, calculate a given value in $O(n)$, and take the maximum of them. Total complexity — $O(n \cdot \sqrt[3]{n})$.
     46 
     47 Solution #2:
     48 
     49 Without using the fact that $k$ is a divisor of $n$, we can simply loop over $k$ and then calculate the values using prefix sums, and at the end check that there are exactly $k$ elements in each segment. Such a solution works in $O(\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}) = O(n \log n)$.
     50 
     51 **Solution**
     52 
     53 ```
     54 #include<bits/stdc++.h>
     55 using namespace std;
     56  
     57 using ll = long long;
     58 #define all(x) x.begin(), x.end()
     59  
     60 void solve() {
     61     int n;
     62     cin >> n;
     63     vector<int> a(n);
     64     for (int i = 0; i < n; ++i) cin >> a[i];
     65     ll ans = -1;
     66     for (int d = 1; d <= n; ++d) {
     67         if (n % d == 0) {
     68             ll mx = -1e18, mn = 1e18;
     69             for (int i = 0; i < n; i += d) {
     70                 ll sm = 0;
     71                 for (int j = i; j < i + d; ++j) {
     72                     sm += a[j];
     73                 }
     74                 mx = max(mx, sm);
     75                 mn = min(mn, sm);
     76             }
     77             ans = max(ans, mx - mn);
     78         }
     79     }
     80     cout << ans << '\n';
     81 }
     82  
     83 int32_t main() {
     84     int t;
     85     cin >> t;
     86     while (t--) solve();
     87 }
     88 ```
     89 
     90 [1899C — Yarik and Array](https://codeforces.com/contest/1899/problem/C)
     91 
     92 Idea: [meowcneil](/profile/meowcneil "Grandmaster meowcneil"), development: [meowcneil](/profile/meowcneil "Grandmaster meowcneil").
     93 
     94 **Editorial**
     95 
     96 There are "bad" positions in the array, i.e., those on which two numbers of the same parity are next to each other. Note that all matching segments cannot contain such positions, in other words, we need to solve the problem of finding a sub segment with maximal sum on some number of non-intersecting sub segments of the array, the boundaries of which are between two neighboring elements of the same parity.
     97 
     98 The problem of finding a sub segment with maximal sum can be solved using the classical algorithm with keeping minimal prefix sum on the prefix. The problem can be solved in a single pass over the array by simply dropping the keeped values when we are in a bad position.
     99 
    100 Total complexity — $O(n)$.
    101 
    102 **Solution**
    103 
    104 ```
    105 #include <iostream>
    106 #include <vector>
    107 #include <algorithm>
    108  
    109 using namespace std;
    110  
    111 void solve() {
    112     int n;
    113     cin >> n;
    114     vector<int> a(n);
    115     for (int i = 0; i < n; ++i) {
    116         cin >> a[i];
    117     }
    118     int ans = a[0];
    119     int mn = min(0, a[0]), sum = a[0];
    120     for (int i = 1; i < n; ++i) {
    121         if (abs(a[i] % 2) == abs(a[i - 1] % 2)) {
    122             mn = 0;
    123             sum = 0;
    124         }
    125         sum += a[i];
    126         ans = max(ans, sum - mn);
    127         mn = min(mn, sum);
    128     }
    129     cout << ans << endl;
    130 }
    131  
    132 int main() {
    133     int tc = 1;
    134     cin >> tc;
    135     for (int t = 1; t <= tc; t++) {
    136         solve();
    137     }
    138 }
    139 ```
    140 
    141 [1899D — Yarik and Musical Notes](https://codeforces.com/contest/1899/problem/D)
    142 
    143 Idea: [zwezdinv](/profile/zwezdinv "Grandmaster zwezdinv"), development: [molney](/profile/molney "Master molney").
    144 
    145 **Editorial**
    146 
    147 The problem requires to count the number of pairs of indices $(i, j)$ ($i \lt j$) such that $(2^a)^{(2^b)} = (2^b)^{(2^a)}$, where $a = b_i, b = b_j$. Obviously, when $a = b$ this equality is satisfied. Let $a \neq b$, then rewrite the equality: $(2^a)^{(2^b)} = (2^b)^{(2^a)} \Leftrightarrow 2^{(a \cdot 2^b)} = 2^{(b \cdot 2^a)} \Leftrightarrow a \cdot 2^b = b \cdot 2^a \Leftrightarrow \frac{a}{b} = \frac{2^a}{2^b}$. Obviously, $a$ and $b$ must differ by powers of two, otherwise the equality cannot be satisfied, since the ratio of powers of two is on the right. Without loss of generality, suppose that $b = a \cdot 2^k$ ($k \gt 0$), then the equation takes the form $\frac{a}{a \cdot 2^k} = \frac{2^a}{2^{a \cdot 2^k}} \Leftrightarrow \frac{1}{2^k} = \frac{1}{2^{(2^k - 1)a}} \Leftrightarrow 2^k = 2^{(2^k - 1)a}$. If $k = 1$, then $a = 1$, $b = 2$. If $k \gt 1$, then $2^k - 1 \gt k$, and so the equality cannot be satisfied.
    148 
    149 Thus, the only possible cases where the equality is satisfied are if $b_i = b_j$ or $b_i = 1, b_j = 2$ (and vice versa). The number of such pairs can be counted for $O(n \log n)$.
    150 
    151 **Solution**
    152 
    153 ```
    154 #include <bits/stdc++.h>
    155 using namespace std;
    156 using ll = long long;
    157  
    158 void solve() {
    159 	int n;
    160 	cin >> n;
    161 	vector<int> a(n);
    162 	for (int& x : a) cin >> x;
    163 	ll ans = 0;
    164 	map<int, int> cnt;
    165 	for (int i = 0; i < n; i++) {
    166 		ans += cnt[a[i]];
    167 		if (a[i] == 1) ans += cnt[2];
    168 		else if (a[i] == 2) ans += cnt[1];
    169 		cnt[a[i]]++;
    170 	}
    171 	cout << ans << "\n";
    172 }
    173  
    174 signed main() {
    175 	int t;
    176 	cin >> t;
    177 	while (t--) solve();
    178 }
    179 ```
    180 
    181 [1899E — Queue Sort](https://codeforces.com/contest/1899/problem/E)
    182 
    183 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), development: [Vladosiya](/profile/Vladosiya "Expert Vladosiya").
    184 
    185 **Editorial**
    186 
    187 Consider the position of the first minimum in the array, let it be equal to $k$. All elements standing on positions smaller than $k$ are strictly greater, so we must apply operations to them, because otherwise the array will not be sorted. Suppose we have applied operations to all such elements, they have taken some positions after $k$ (since they are strictly greater than the minimum), i.e. now the minimum element that moved from position $k$ is at the beginning of the array. If we apply the operation to it, it will return to its current position, since it is less than or equal to all elements of the array, i.e. the array will not change.
    188 
    189 Thus, after the array has its minimum at the beginning, it is useless to apply operations, and all the operations applied before that will move the element from the beginning of the array to some position after the position of the first minimum.
    190 
    191 Then, if the part of the array after the position $k$ is not sorted, the answer is $-1$, because it is impossible to change the order of elements in it. Otherwise, the answer is equal to the number of elements standing before the first minimum, since the operation must be applied to them and they will be in the right place in the right part. Total complexity — $O(n)$.
    192 
    193 **Solution**
    194 
    195 ```
    196 def solve():
    197     n = int(input())
    198     a = [int(x) for x in input().split()]
    199     fm = 0
    200     for i in range(n):
    201         if a[i] < a[fm]:
    202             fm = i
    203     for i in range(fm + 1, n):
    204         if a[i] < a[i - 1]:
    205             print(-1)
    206             return
    207     print(fm)
    208  
    209  
    210 for _ in range(int(input())):
    211     solve()
    212 ```
    213 
    214 [1899F — Alex's whims](https://codeforces.com/contest/1899/problem/F)
    215 
    216 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), development: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), [zwezdinv](/profile/zwezdinv "Grandmaster zwezdinv").
    217 
    218 **Editorial**
    219 
    220 This problem can be solved in several similar ways, one of them is given below. First, it is most convenient to take a bamboo — vertices from $1$ to $n$ connected in order. Then, we will maintain the following construction. At each moment of time, vertices $1$ and $2$ will be connected by an edge, from vertex $2$ there will be at most two branches, which are sequentially connected vertices (bamboo). Thus, at any given time there will be at most three leaves in the tree, one of which is vertex $1$.
    221 
    222 We will maintain vertices from two branches in two arrays. Then, let the current number from the query be $d$. If the distance from any of the leaves to vertex $1$ is $d$, we don't need to perform the operation. Otherwise, let's do the operation so that the distance from a leaf from, for example, the first branch to vertex $1$ is equal to $d$. If the current distance is greater than $d$, then we remove the extra vertices to the end of the second branch, and otherwise we add the necessary ones from the end of the second branch. Thus, after each operation, the distance from vertex $1$ to some of the sheets will be equal to $d$.
    223 
    224 Transformations can be done by completely moving vertices, then the total complexity — $O(nq)$.
    225 
    226 **Solution**
    227 
    228 ```
    229 #include<bits/stdc++.h>
    230 using namespace std;
    231 
    232 int main() {
    233 	int t;
    234 	cin >> t;
    235 	while (t--) {
    236 		int n;
    237 		cin >> n;
    238 		vector<int> b1, b2;
    239 		for (int i = 0; i < n; ++i) {
    240 			b1.push_back(i);
    241 		}
    242 		b2.push_back(1);
    243 		for (int i = 1; i < n; ++i) {
    244 			cout << i << ' ' << i + 1 << endl;
    245 		}
    246 		int q;
    247 		cin >> q;
    248 		while (q--) {
    249 			int d;
    250 			cin >> d;
    251 			d++;
    252 			if (b1.size() == d) {
    253 				cout << "-1 -1 -1\n";
    254 			} else if (b1.size() < d) {
    255 				d = d - b1.size();
    256 				vector<int> qq(b2.end() - d, b2.end());
    257 				int u = b2[b2.size() - d];
    258 				int v1 = b2[b2.size() - d - 1];
    259 				int v2 = b1.back();
    260 				cout << u + 1 << ' ' << v1 + 1 << ' ' << v2 + 1 << '\n';
    261 				for (int i = 0; i < d; ++i) b2.pop_back();
    262 				for (auto i : qq) b1.push_back(i);
    263 			} else {
    264 				d = b1.size() - d;
    265 				vector<int> qq(b1.end() - d, b1.end());
    266 				int u = b1[b1.size() - d];
    267 				int v1 = b1[b1.size() - d - 1];
    268 				int v2 = b2.back();
    269 				cout << u + 1 << ' ' << v1 + 1 << ' ' << v2 + 1 << '\n';
    270 				for (int i = 0; i < d; ++i) b1.pop_back();
    271 				for (auto i : qq) b2.push_back(i);
    272 			}
    273 		}
    274 	}
    275 }
    276 ```
    277 
    278 [1899G — Unusual Entertainment](https://codeforces.com/contest/1899/problem/G)
    279 
    280 Idea: [EJIC_B_KEDAX](/profile/EJIC_B_KEDAX "Master EJIC_B_KEDAX"), development: [Sokol080808](/profile/Sokol080808 "Master Sokol080808").
    281 
    282 **Editorial**
    283 
    284 Let's start the depth-first search from vertex $1$ and write out the entry and exit times for each vertex. Then, the fact that vertex $b$ is a descendant of vertex $a$ is equivalent to the fact that $\mathrm{tin}[a] \leq \mathrm{tin}[b] \leq \mathrm{tout}[b] \leq \mathrm{tout}[b] \leq \mathrm{tout}[a]$, where $\mathrm{tin}$ and $\mathrm{tout}$ — entry and exit times, respectively. Then, let us create an array $a$, where $a_i = \mathrm{tin}[p_i]$, then the problem is reduced to checking that on the segment c $l$ through $r$ in array $a$ there is at least one number belonging to the segment $[\mathrm{tin}[x]; \mathrm{tout}[x]]$. This can be done, for example, using Merge Sort Tree, then the total complexity will be $O(n \log n + q \log^ 2 n)$.
    285 
    286 **Solution**
    287 
    288 ```
    289 #include <bits/stdc++.h>
    290  
    291 using namespace std;
    292  
    293 #define sz(x) (int)x.size()
    294 #define all(x) x.begin(), x.end()
    295  
    296 struct SegmentTree {
    297     int n;
    298     vector<vector<int>> tree;
    299  
    300     void build(vector<int> &a, int x, int l, int r) {
    301         if (l + 1 == r) {
    302             tree[x] = {a[l]};
    303             return;
    304         }
    305  
    306         int m = (l + r) / 2;
    307         build(a, 2 * x + 1, l, m);
    308         build(a, 2 * x + 2, m, r);
    309         merge(all(tree[2 * x + 1]), all(tree[2 * x + 2]), back_inserter(tree[x]));
    310     }
    311  
    312     SegmentTree(vector<int>& a) : n(a.size()) {
    313         int SIZE = 1 << (__lg(n) + bool(__builtin_popcount(n) - 1));
    314         tree.resize(2 * SIZE - 1);
    315         build(a, 0, 0, n);
    316     }
    317  
    318     int count(int lq, int rq, int mn, int mx, int x, int l, int r) {
    319         if (rq <= l || r <= lq) return 0;
    320         if (lq <= l && r <= rq) return lower_bound(all(tree[x]), mx) - lower_bound(all(tree[x]), mn);
    321  
    322         int m = (l + r) / 2;
    323         int a = count(lq, rq, mn, mx, 2 * x + 1, l, m);
    324         int b = count(lq, rq, mn, mx, 2 * x + 2, m, r);
    325         return a + b;
    326     }
    327  
    328     int count(int lq, int rq, int mn, int mx) {
    329         return count(lq, rq, mn, mx, 0, 0, n);
    330     }
    331 };
    332  
    333 vector<vector<int>> g;
    334  
    335 vector<int> tin, tout;
    336 int timer;
    337 void dfs(int v, int p) {
    338     tin[v] = timer++;
    339     for (auto u : g[v]) {
    340         if (u != p) {
    341             dfs(u, v);
    342         }
    343     }
    344     tout[v] = timer;
    345 }
    346  
    347 void solve() {
    348     int n, q;
    349     cin >> n >> q;
    350     
    351     g.assign(n, vector<int>());
    352     for (int i = 0; i < n - 1; i++) {
    353         int u, v;
    354         cin >> u >> v;
    355         u--; v--;
    356         g[u].push_back(v);
    357         g[v].push_back(u);
    358     }
    359  
    360     timer = 0;
    361     tin.resize(n);
    362     tout.resize(n);
    363     dfs(0, -1);
    364     
    365     vector<int> p(n);
    366     for (int i = 0; i < n; i++) cin >> p[i];
    367  
    368     vector<int> a(n);
    369     for (int i = 0; i < n; i++) a[i] = tin[p[i] - 1];
    370     SegmentTree ST(a);
    371  
    372     for (int i = 0; i < q; i++) {
    373         int l, r, x;
    374         cin >> l >> r >> x;
    375         l--; x--;
    376         if (ST.count(l, r, tin[x], tout[x])) {
    377             cout << "YES\n";
    378         } else {
    379             cout << "NO\n";
    380         }
    381     }
    382 }
    383  
    384 int main() {
    385     int tests;
    386     cin >> tests;
    387     while (tests--) {
    388         solve();
    389         if(tests > 0) cout << "\n";
    390     }
    391     return 0;
    392 }
    393 ```