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 ```