2055.md (37322B)
1 Source: https://codeforces.com/blog/entry/138343 2 3 Hope you enjoyed the problems! 4 5 **UPD 1:** Added implementations! 6 7 **UPD 2:** It seems my wording for the solution to C is not the best, and it is causing some confusion. I've updated it to be better! 8 9 **UPD 3:** Implementation links didn't work for some reason, so I've just added the code directly. 10 11 [2055A - Two Frogs](/contest/2055/problem/A "Codeforces Round 996 (Div. 2)") 12 13 **Hint 1** 14 15 Look at the distance between the frogs. 16 17 **Solution** 18 19 Notice that regardless of how the players move, the difference between the numbers of the lilypads the two players are standing on always alternates even and odd, depending on the starting configuration. Then, the key observation is that exactly one player has the following winning strategy: 20 21 * Walk towards the other player, and do not stop until they are forced onto lilypad $1$ or $n$. 22 23 For instance, if Alice and Bob start on lilypads with the same parity, Bob cannot stop Alice from advancing towards him. This is because at the start of Alice's turn, she will always be able to move towards Bob due to their distance being even and therefore at least $2$, implying that there is a free lilypad for her to jump to. This eventually forces Bob into one of the lilypads $1, n$, causing him to lose. 24 25 In the case that they start on lilypads with different parity, analogous logic shows that Bob wins. Therefore, for each case, we only need to check the parity of the lilypads for a constant time solution. 26 27 **Implementation** 28 29 ``` 30 #include <bits/stdc++.h> 31 32 using namespace std; 33 34 int main() 35 { 36 ios_base::sync_with_stdio(false); 37 cin.tie(0); 38 39 int T; cin >> T; 40 while (T--) { 41 int N, A, B; cin >> N >> A >> B; 42 if ((A ^ B) & 1) cout << "NO\n"; 43 else cout << "YES\n"; 44 } 45 cout.flush(); 46 return 0; 47 } 48 ``` 49 50 [2055B - Crafting](/contest/2055/problem/B "Codeforces Round 996 (Div. 2)") 51 52 **Hint 1** 53 54 The order of the moves is pretty much irrelevant. What happens if we try to make two different materials? 55 56 **Solution** 57 58 The key observation is that we will never use the operation to craft two different types of materials $i, j$. This is because if we were to combine the net change in resources from these two operations, we would lose two units each of every material $k \neq i, j$, and receive a net zero change in our amounts of materials $i, j$. Therefore, we will only ever use the operation on one type of material $i$. 59 60 An immediate corollary of this observation is that we can only be deficient in at most one type of material, i.e. at most one index $i$ at which $a_i \lt b_i$. If no such index exists, the material is craftable using our starting resources. Otherwise, applying the operation $x$ times transforms our array to 61 62 $a_j := \begin{cases} a_j + x & \text{if}\ i = j \\ a_j - x & \text{if}\ i \neq j \end{cases}$ 63 64 i.e. increasing element $a_i$ by $x$ and decreasing all other elements by $x$. We must have $x \geq b_i - a_i$ to satisfy the requirement on material type $i$. However, there is also no point in making $x$ any larger, as by then we already have enough of type $i$, and further operations cause us to start losing materials from other types that we could potentially need to craft the artifact. Therefore, our condition in this case is just to check that 65 66 $b_i - a_i \leq \min_{j \neq i} a_j - b_j,$ 67 68 i.e. we are deficient in type $i$ by at most as many units as our smallest surplus in all other material types $j \neq i$. This gives an $O(n)$ solution. 69 70 **Implementation** 71 72 ``` 73 // #include <ext/pb_ds/assoc_container.hpp> 74 // #include <ext/pb_ds/tree_policy.hpp> 75 // using namespace __gnu_pbds; 76 // typedef tree<int, null_type, std::less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; 77 78 #include <bits/stdc++.h> 79 80 #define f first 81 #define s second 82 #define pb push_back 83 84 typedef long long int ll; 85 typedef unsigned long long int ull; 86 using namespace std; 87 typedef pair<int,int> pii; 88 typedef pair<ll,ll> pll; 89 90 template<typename T> int die(T x) { cout << x << endl; return 0; } 91 92 #define mod_fft 998244353 93 #define mod_nfft 1000000007 94 #define INF 100000000000000 95 #define LNF 1e15 96 #define LOL 12345678912345719ll 97 98 struct LL { 99 100 static const ll m = mod_fft; 101 long long int val; 102 103 LL(ll v) {val=reduce(v);}; 104 LL() {val=0;}; 105 ~LL(){}; 106 LL(const LL& l) {val=l.val;}; 107 LL& operator=(int l) {val=l; return *this;} 108 LL& operator=(ll l) {val=l; return *this;} 109 LL& operator=(LL l) {val=l.val; return *this;} 110 111 static long long int reduce(ll x, ll md = m) { 112 x %= md; 113 while (x >= md) x-=md; 114 while (x < 0) x+=md; 115 return x; 116 } 117 118 bool operator<(const LL& b) { return val<b.val; } 119 bool operator<=(const LL& b) { return val<=b.val; } 120 bool operator==(const LL& b) { return val==b.val; } 121 bool operator>=(const LL& b) { return val>=b.val; } 122 bool operator>(const LL& b) { return val>b.val; } 123 124 LL operator+(const LL& b) { return LL(val+b.val); } 125 LL operator+(const ll& b) { return (*this+LL(b)); } 126 LL& operator+=(const LL& b) { return (*this=*this+b); } 127 LL& operator+=(const ll& b) { return (*this=*this+b); } 128 129 LL operator-(const LL& b) { return LL(val-b.val); } 130 LL operator-(const ll& b) { return (*this-LL(b)); } 131 LL& operator-=(const LL& b) { return (*this=*this-b); } 132 LL& operator-=(const ll& b) { return (*this=*this-b); } 133 134 LL operator*(const LL& b) { return LL(val*b.val); } 135 LL operator*(const ll& b) { return (*this*LL(b)); } 136 LL& operator*=(const LL& b) { return (*this=*this*b); } 137 LL& operator*=(const ll& b) { return (*this=*this*b); } 138 139 static LL exp(const LL& x, const ll& y){ 140 ll z = y; 141 z = reduce(z,m-1); 142 LL ret = 1; 143 LL w = x; 144 while (z) { 145 if (z&1) ret *= w; 146 z >>= 1; w *= w; 147 } 148 return ret; 149 } 150 LL& operator^=(ll y) { return (*this=LL(val^y)); } 151 152 LL operator/(const LL& b) { return ((*this)*exp(b,-1)); } 153 LL operator/(const ll& b) { return (*this/LL(b)); } 154 LL operator/=(const LL& b) { return ((*this)*=exp(b,-1)); } 155 LL& operator/=(const ll& b) { return (*this=*this/LL(b)); } 156 157 }; ostream& operator<<(ostream& os, const LL& obj) { return os << obj.val; } 158 159 int N; 160 vector<ll> segtree; 161 162 void pull(int t) { 163 segtree[t] = max(segtree[2*t], segtree[2*t+1]); 164 } 165 166 void point_set(int idx, ll val, int L = 1, int R = N, int t = 1) { 167 if (L == R) segtree[t] = val; 168 else { 169 int M = (L + R) / 2; 170 if (idx <= M) point_set(idx, val, L, M, 2*t); 171 else point_set(idx, val, M+1, R, 2*t+1); 172 pull(t); 173 } 174 } 175 176 ll range_add(int left, int right, int L = 1, int R = N, int t = 1) { 177 if (left <= L && R <= right) return segtree[t]; 178 else { 179 int M = (L + R) / 2; 180 ll ret = 0; 181 if (left <= M) ret = max(ret, range_add(left, right, L, M, 2*t)); 182 if (right > M) ret = max(ret, range_add(left, right, M+1, R, 2*t+1)); 183 return ret; 184 } 185 } 186 187 void build(vector<ll>& arr, int L = 1, int R = N, int t = 1) { 188 if (L == R) segtree[t] = arr[L-1]; 189 else { 190 int M = (L + R) / 2; 191 build(arr, L, M, 2*t); 192 build(arr, M+1, R, 2*t+1); 193 pull(t); 194 } 195 } 196 197 int main() { 198 ios_base::sync_with_stdio(false); 199 cin.tie(0); 200 int T = 1; cin >> T; 201 while (T--) { 202 int N; cin >> N; 203 vector<int> A(N), B(N); 204 for (int i = 0; i < N; i++) cin >> A[i]; 205 int bad = -1, margin = 1e9, need = 0; 206 bool reject = 0; 207 for (int i = 0; i < N; i++) { 208 cin >> B[i]; 209 if (A[i] < B[i]) { 210 if (bad != -1) reject = 1; 211 bad = i; 212 need = B[i] - A[i]; 213 } else { 214 margin = min(margin, A[i] - B[i]); 215 } 216 } 217 if (reject) { 218 cout << "NO" << endl; 219 continue; 220 } else { 221 cout << ((margin >= need) ? "YES" : "NO") << endl; 222 } 223 } 224 } 225 ``` 226 227 [2055C - The Trail](/contest/2055/problem/C "Codeforces Round 996 (Div. 2)") 228 229 **Hint 1** 230 231 Pick $x$, and find the sum of the whole grid. What does this tell you? 232 233 **Hint 2** 234 235 Once you know $x$, the top left cell is fixed. 236 237 **Hint 3** 238 239 What about the next cell on the trail? 240 241 **Solution** 242 243 The naive solution of writing out a linear system and solving them will take $O((n + m)^3)$ time, which is too slow, so we will need a faster algorithm. 244 245 We begin by selecting a target sum $S$ for each row and column. If we calculate the sum of all numbers in the completed grid, summing over rows gives a total of $S \cdot n$ while summing over columns gives a total of $S \cdot m$. Therefore, in order for our choice of $S$ to be possible, we require $S \cdot n = S \cdot m$, and since it is possible for $n \neq m$, we will pick $S = 0$ for our choice to be possible in all cases of $n, m$. **Notice that all choices $S \neq 0$ will fail on $n \neq m$, as the condition $S \cdot n = S \cdot m$ no longer holds. As such, $S = 0$ is the only one that will work in all cases.** 246 247 Now, we aim to make each row and column sum to $S$. The crux of the problem is the following observation: 248 249 * Denote $x_1, x_2, \dots, x_{n+m-1}$ to be the variables along the path. Let's say variables $x_1, \dots, x_{i-1}$ have their values set for some $1 \leq i \lt n+m-1$. Then, either the row or column corresponding to variable $x_i$ has all of its values set besides $x_i$, and therefore we may determine exactly one possible value of $x_i$ to make its row or column sum to $0$. 250 251 The proof of this claim is simple. At variable $x_i$, we look at the corresponding path move $s_i$. If $s_i = \tt{R}$, then the path will never revisit the column of variable $x_i$, and its column will have no remaining unset variables since $x_1, \dots, x_{i-1}$ are already set. Likewise, if $s_i = \tt{D}$, then the path will never revisit the row of variable $x_i$, which can then be used to determine the value of $x_i$. 252 253 Repeating this process will cause every row and column except for row $n$ and column $m$ to have a sum of zero, with $x_{n+m-1}$ being the final variable. However, we will show that we can use either the row or column to determine it, and it will give a sum of zero for both row $n$ and column $m$. WLOG we use row $n$. Indeed, if the sum of all rows and columns except for column $m$ are zero, we know that the sum of all entries of the grid is zero by summing over rows. However, we may then subtract all columns except column $m$ from this total to arrive at the conclusion that column $m$ also has zero sum. Therefore, we may determine the value of $x_{n+m-1}$ using either its row or column to finish our construction, giving a solution in $O(n \cdot m)$. 254 255 **Implementation** 256 257 ``` 258 #include <bits/stdc++.h> 259 260 #define f first 261 #define s second 262 #define pb push_back 263 264 typedef long long int ll; 265 typedef unsigned long long int ull; 266 using namespace std; 267 typedef pair<int,int> pii; 268 typedef pair<ll,ll> pll; 269 270 template<typename T> int die(T x) { cout << x << endl; return 0; } 271 272 #define mod 1000000007 273 #define INF 1000000000 274 #define LNF 1e15 275 #define LOL 12345678912345719ll 276 277 using namespace std; 278 279 int main() 280 { 281 ios_base::sync_with_stdio(false); 282 cin.tie(0); 283 284 int T; cin >> T; 285 while (T--) { 286 int N, M; cin >> N >> M; 287 string S; cin >> S; 288 vector<vector<ll>> A; 289 for (int i = 0; i < N; i++) { 290 A.push_back(vector<ll>(M)); 291 for (int j = 0; j < M; j++) { 292 cin >> A[i][j]; 293 } 294 } 295 int x = 0, y = 0; 296 for (char c : S) { 297 if (c == 'D') { 298 long long su = 0; 299 for (int i = 0; i < M; i++) { 300 su += A[x][i]; 301 } 302 A[x][y] = -su; 303 ++x; 304 } else { 305 long long su = 0; 306 for (int i = 0; i < N; i++) { 307 su += A[i][y]; 308 } 309 A[x][y] = -su; 310 ++y; 311 } 312 } 313 long long su = 0; 314 for (int i = 0; i < M; i++) { 315 su += A[N-1][i]; 316 } 317 A[N-1][M-1] = -su; 318 for (int i = 0; i < N; i++) { 319 for (int j = 0; j < M; j++) { 320 cout << A[i][j] << " "; 321 } 322 cout << endl; 323 } 324 325 } 326 return 0; 327 } 328 ``` 329 330 [2055D - Scarecrow](/contest/2055/problem/D "Codeforces Round 996 (Div. 2)") 331 332 **Hint 1** 333 334 Should you ever change the order of scarecrows? 335 336 **Hint 2** 337 338 What's the first thing that the leftmost scarecrow should do? 339 340 **Hint 3** 341 342 What's the only way to save time? Think in terms of distances and not times. 343 344 **Hint 4** 345 346 Look at the points where the crow "switches over" between scarecrows. 347 348 **Hint 5** 349 350 Greedy. 351 352 **Solution** 353 354 We make a few preliminary observations: 355 356 * (1) The order of scarecrows should never change, i.e no two scarecrows should cross each other while moving along the interval. 357 * (2) Scarecrow $1$ should spend the first $a_1$ seconds moving to position zero, as this move is required for the crow to make any progress and there is no point in delaying it. 358 * (3) Let's say that a scarecrow at position $p$ `has' the crow if the crow is at position $p + k$, and there are no other scarecrows in the interval $[p, p+k]$. A scarecrow that has the crow should always move to the right; in other words, all scarecrows that find themselves located to the left of the crow should spend all their remaining time moving to the right, as it is the only way they will be useful. 359 * (4) Let there be a scenario where at time $T$, scarecrow $i$ has the crow and is at position $x$, and another scenario at time $T$ where scarecrow $i$ also has the crow, but is at position $y \geq x$. Then, the latter scenario is at least as good as the former scenario, assuming scarecrows numbered higher than $i$ are not fixed. 360 * (5) The only way to save time is to maximize the distance $d$ teleported by the crow. 361 362 The second and fifth observations imply that the time spent to move the crow across the interval is $a_1 + \ell - d$. 363 364 Now, for each scarecrow $i$, define $b_i$ to be the position along the interval at which it begins to have the crow, i.e. the crow is transferred from scarecrow $i-1$ to $i$. For instance, in the second sample case the values of $b_i$ are 365 366 $(b_1, b_2, b_3) = (0, 2.5, 4.5)$ 367 368 The second observation above implies that $b_1 = 0$, and the first observation implies that $b_1 \leq \dots \leq b_n$. Notice that we may express the distance teleported as 369 370 $d = \sum_{i=1}^{n} \min(k, b_{i+1} - b_i)$ 371 372 with the extra definition that $b_{n+1} = \ell$. For instance, in the second sample case the distance teleported is 373 374 $d = \min(k, b_2 - b_1) + \min(k, b_3 - b_2) + \min(k, \ell - b_3) = 2 + 2 + 0.5 = 4.5$ 375 376 and the total time is $a_1 + \ell - d = 2 + 5 - 4.5 = 2.5$. 377 378 Now, suppose that $b_1, \dots, b_{i-1}$ have been selected for some $2 \leq i \leq n$, and that time $T$ has elapsed upon scarecrow $i-1$ receiving the crow. We will argue the optimal choice of $b_i$. 379 380 At time $T$ when scarecrow $i-1$ first receives the crow, scarecrow $i$ may be at any position in the interval $[a_i - T, \min(a_i + T, \ell)]$. Now, we have three cases. 381 382 **Case 1. $b_{i-1} + k \leq a_i - T.$** In this case, scarecrow $i$ will need to move some nonnegative amount to the left in order to meet with scarecrow $i-1$. They will meet at the midpoint of the crow position $b_{i-1} + k$ and the leftmost possible position $a_i - T$ of scarecrow $i$ at time $T$. This gives 383 384 $b_i := \frac{a_i - T + b_{i-1} + k}{2}.$ 385 386 **Case 2. $a_i - T \leq b_{i-1} + k \leq a_i + T.$** Notice that if our choice of $b_i$ has $b_i \lt b_{i-1} + k$, it benefits us to increase our choice of $b_i$ (if possible) as a consequence of our fourth observation, since all such $b_i$ will cause an immediate transfer of the crow to scarecrow $i$ at time $T$. However, if we choose $b_i \gt b_{i-1} + k$, lowering our choice of $b_i$ is now better as it loses less potential teleported distance $\min(k, b_i - b_{i-1})$, while leaving more space for teleported distance after position $b_i$. Therefore, we will choose $b_i := b_{i-1} + k$ in this case. 387 388 **Case 3. $a_i + T \leq b_{i-1} + k.$** In this case, regardless of how we choose $b_i$, the crow will immediately transfer to scarecrow $i$ from scarecrow $i-1$ at time $T$. We might as well pick $b_i := a_i + T$. 389 390 Therefore, the optimal selection of $b_i$ may be calculated iteratively as 391 392 $b_i := \min\left(\ell, \overbrace{a_i + T}^{\text{case 3}}, \max\left(\overbrace{b_{i-1} + k}^{\text{case 2}}, \overbrace{\frac{a_i - T + b_{i-1} + k}{2}}^{\text{case 1}}\right)\right).$ 393 394 It is now easy to implement the above approach to yield an $O(n)$ solution. Note that the constraints for $k, \ell$ were deliberately set to $10^8$ instead of $10^9$ to make two times the maximum answer $4 \cdot \ell$ fit within $32$-bit integer types. It is not difficult to show that the values of $b_i$ as well as the answer are always integers or half-integers. 395 396 **Implementation** 397 398 ``` 399 #include <bits/stdc++.h> 400 401 #define f first 402 #define s second 403 #define pb push_back 404 405 typedef long long int ll; 406 typedef unsigned long long int ull; 407 using namespace std; 408 typedef pair<int,int> pii; 409 typedef pair<ll,ll> pll; 410 411 int main() 412 { 413 ios_base::sync_with_stdio(false); 414 cin.tie(0); 415 416 int T; cin >> T; 417 while (T--) { 418 int N, k, l; 419 cin >> N >> k >> l; 420 double K = k; 421 double L = l; 422 vector<int> A(N); 423 for (int i = 0; i < N; i++) cin >> A[i]; 424 double T = A[0]; 425 double last_pt = 0; 426 double S = 0; 427 for (int i = 1; i < N; i++) { 428 double this_pt = min(L, min(A[i] + T, 429 max(last_pt + K, 430 (A[i] - T + last_pt + K)/2.0))); 431 T += max(0.0, this_pt - last_pt - K); 432 S += min(K, this_pt - last_pt); 433 last_pt = this_pt; 434 } 435 S += min(K, L - last_pt); 436 cout << (int)round(2*(L - S + A[0])) << endl; 437 } 438 return 0; 439 } 440 ``` 441 442 [2055E - Haystacks](/contest/2055/problem/E "Codeforces Round 996 (Div. 2)") 443 444 **Hint 1** 445 446 Let's say you have to empty the haystacks in a fixed order. What's the best way to do it? 447 448 **Hint 2** 449 450 Write the expression for the number of moves for a given order. 451 452 **Hint 3** 453 454 In an optimal ordering, you should not gain anything by swapping two entries of the order. Using this, describe the optimal order. 455 456 **Hint 4** 457 458 The constraint only limits what you can empty last. How can you efficiently compute the expression in Hint 2? 459 460 **Solution** 461 462 Let's say we fixed some permutation $\sigma$ of $1, \dots, n$ such that we empty haystacks in the order $\sigma_1, \dots, \sigma_n$. Notice that a choice of $\sigma$ is possible if and only if the final stack $\sigma_n$ can be cleared, which is equivalent to the constraint 463 464 $a_{\sigma_1} + \dots + a_{\sigma_n} \leq b_{\sigma_1} + \dots + b_{\sigma_{n-1}}.$ 465 466 With this added constraint, the optimal sequence of moves is as follows: 467 468 * Iterate $i$ through $1, \dots, n-1$. For each $i$, try to move its haybales to haystacks $1, \dots, i-1$, and if they are all full then move haybales to haystack $n$. Once this process terminates, move all haystacks from $n$ back onto arbitrary haystacks $1, \dots, n-1$, being careful to not overflow the height limits. 469 470 The key observation is that the number of extra haybales that must be moved onto haystack $n$ is 471 472 $\max_{1 \leq i \leq n-1} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}.$ 473 474 To show this, consider the last time $i$ that a haybale is moved onto haystack $n$. At this time, all haybales from haystacks $1, \dots, i$ have found a home, either on the height limited haystacks $1, \dots, i-1$ or on haystack $n$, from which the identity immediately follows. Now, every haystack that wasn't moved onto haystack $n$ will get moved once, and every haystack that did gets moved twice. Therefore, our task becomes the following: Compute 475 476 $\sum_{i=1}^{n} a_i + \min_{\sigma} \max_{1 \leq i \leq n-1} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}$ 477 478 for $\sigma$ satisfying 479 480 $a_{\sigma_1} + \dots + a_{\sigma_n} \leq b_{\sigma_1} + \dots + b_{\sigma_{n-1}}.$ 481 482 Notice that the $\sum_{i=1}^n a_i$ term is constant, and we will omit it for the rest of this tutorial. We will first solve the task with no restriction on $\sigma$ to gain some intuition. Denote $ \lt _{\sigma}$ the ordering of pairs $(a, b)$ corresponding to $\sigma$. 483 484 Consider adjacent pairs $(a_i, b_i) \lt _{\sigma} (a_j, b_j)$. Then, if the choice of $\sigma$ is optimal, it must not be better to swap their ordering, i.e. 485 486 $\begin{align*} \overbrace{(a_i, b_i) \lt _{\sigma} (a_j, b_j)}^{\text{optimal}} \implies& \max(a_i, a_i + a_j - b_i) \leq \max(a_j, a_i + a_j - b_j) \\ \iff& \max(-a_j, -b_i) \leq \max(-a_i, -b_j)\\ \iff& \min(a_j, b_i) \geq \min(a_i, b_j). \end{align*}$ 487 488 As a corollary, there exists an optimal $\sigma$ satisfying the following properties: 489 490 **Claim [Optimality conditions of $\sigma$].** 491 492 * All pairs with $a_i \lt b_i$ come first. Then, all pairs with $a_i = b_i$ come next. Then, all pairs with $a_i \gt b_i$. 493 * The pairs with $a_i \lt b_i$ are in ascending order of $a_i$. 494 * The pairs with $a_i \gt b_i$ are in descending order of $b_i$. 495 496 It is not hard to show that all such $\sigma$ satisfying these properties are optimal by following similar logic as above. We leave it as an exercise for the reader. 497 498 Now, we add in the constraint on the final term $\sigma_n$ of the ordering. We will perform casework on this final haystack. Notice that for any fixed $a_n, b_n$, if 499 500 $\max_{1 \leq i \leq n-1} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}$ 501 502 is maximized, then so is 503 504 $\max_{1 \leq i \leq n} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}.$ 505 506 So, if we were to fix any last haystack $\sigma_n$, the optimality conditions tell us that we should still order the remaining $n-1$ haystacks as before. Now, we may iterate over all valid $\sigma_n$ and compute the answer efficiently as follows: maintain a segment tree with leaves representing pairs $(a_i, b_i)$ and range queries for 507 508 $\max_{1 \leq i \leq n} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}.$ 509 510 This gives an $O(n \log n)$ solution. 511 512 Note that it is possible to implement this final step using prefix and suffix sums to yield an $O(n)$ solution, but it is not necessary to do so. 513 514 **Implementation** 515 516 ``` 517 #include <bits/stdc++.h> 518 519 #define f first 520 #define s second 521 #define pb push_back 522 523 typedef long long int ll; 524 typedef unsigned long long int ull; 525 using namespace std; 526 typedef pair<int,int> pii; 527 typedef pair<ll,ll> pll; 528 529 template<typename T> int die(T x) { cout << x << endl; return 0; } 530 531 #define LNF 1e15 532 533 int N; 534 vector<pll> segtree; 535 536 pll f(pll a, pll b) { 537 return {max(a.first, a.second + b.first), a.second + b.second}; 538 } 539 540 void pull(int t) { 541 segtree[t] = f(segtree[2*t], segtree[2*t+1]); 542 } 543 544 void point_set(int idx, pll val, int L = 1, int R = N, int t = 1) { 545 if (L == R) segtree[t] = val; 546 else { 547 int M = (L + R) / 2; 548 if (idx <= M) point_set(idx, val, L, M, 2*t); 549 else point_set(idx, val, M+1, R, 2*t+1); 550 pull(t); 551 } 552 } 553 554 pll range_add(int left, int right, int L = 1, int R = N, int t = 1) { 555 if (left <= L && R <= right) return segtree[t]; 556 else { 557 int M = (L + R) / 2; 558 pll ret = {0, 0}; 559 if (left <= M) ret = f(ret, range_add(left, right, L, M, 2*t)); 560 if (right > M) ret = f(ret, range_add(left, right, M+1, R, 2*t+1)); 561 return ret; 562 } 563 } 564 565 void build(vector<pll>& arr, int L = 1, int R = N, int t = 1) { 566 if (L == R) segtree[t] = arr[L-1]; 567 else { 568 int M = (L + R) / 2; 569 build(arr, L, M, 2*t); 570 build(arr, M+1, R, 2*t+1); 571 pull(t); 572 } 573 } 574 575 vector<int> theoretical(const vector<pii>& arr) { 576 vector<int> idx(arr.size()); 577 for (int i = 0; i < arr.size(); ++i) { 578 idx[i] = i; 579 } 580 581 vector<int> ut, eq, lt; 582 for (int i = 0; i < arr.size(); ++i) { 583 if (arr[i].first < arr[i].second) { 584 ut.push_back(i); 585 } else if (arr[i].first == arr[i].second) { 586 eq.push_back(i); 587 } else { 588 lt.push_back(i); 589 } 590 } 591 592 sort(ut.begin(), ut.end(), [&arr](int i, int j) { 593 return arr[i].first < arr[j].first; 594 }); 595 596 sort(eq.begin(), eq.end(), [&arr](int i, int j) { 597 return arr[i].first > arr[j].first; 598 }); 599 600 sort(lt.begin(), lt.end(), [&arr](int i, int j) { 601 return arr[i].second > arr[j].second; 602 }); 603 604 vector<int> result; 605 result.insert(result.end(), ut.begin(), ut.end()); 606 result.insert(result.end(), eq.begin(), eq.end()); 607 result.insert(result.end(), lt.begin(), lt.end()); 608 609 return result; 610 } 611 612 int main() { 613 ios_base::sync_with_stdio(false); 614 cin.tie(0); 615 int T = 1; cin >> T; 616 while (T--) { 617 cin >> N; 618 vector<pll> data(N); 619 ll sum_a = 0; 620 ll sum_b = 0; 621 for (int i = 0; i < N; i++) { 622 cin >> data[i].f >> data[i].s; 623 sum_a += data[i].f; 624 sum_b += data[i].s; 625 } 626 vector<int> order = theoretical(vector<pii>(data.begin(), data.end())); 627 628 vector<pll> data_sorted; 629 for (int i : order) data_sorted.push_back({data[i].first, data[i].first - data[i].second}); 630 data_sorted.push_back({0, 0}); 631 632 ++N; 633 634 segtree = vector<pll>(4*N); 635 build(data_sorted); 636 637 ll ans = LNF; 638 for (int i = 0; i < N-1; i++) { 639 if (sum_b - (data_sorted[i].first - data_sorted[i].second) >= sum_a) { 640 point_set(i+1, data_sorted[N-1]); 641 point_set(N, data_sorted[i]); 642 643 ans = min(ans, range_add(1, N).first); 644 645 point_set(i+1, data_sorted[i]); 646 point_set(N, data_sorted[N-1]); 647 } 648 } 649 if (ans == LNF) cout << -1 << endl; 650 else cout << ans + sum_a << endl; 651 } 652 } 653 ``` 654 655 [2055F - Cosmic Divide](/contest/2055/problem/F "Codeforces Round 996 (Div. 2)") 656 657 **Hint 1** 658 659 The results of the partition must be convex. Can you see why? 660 661 **Hint 2** 662 663 The easier cases are when the polyomino must be cut vertically or horizontally. Let's discard those for now, and consider the "diagonal cuts". I.e. let one polyomino start from the top row, and another starting from some row $c$. WLOG the one starting on row $c$ is on the left side, we will check the other side by just duplicating the rest of the solution. 664 665 **Hint 3** 666 667 Both sub-polyominoes are fixed if you choose $c$. But, it takes $O(n)$ time to check each one. 668 669 **Hint 4** 670 671 Can you get rid of most $c$ with a quick check? 672 673 **Hint 5** 674 675 Look at perimeters shapes, or area. Both will work. 676 677 **Solution** 678 679 Assume there exists a valid partition of the polyomino. Note that the resulting congruent polyominoes must be convex, as it is not possible to join two non-overlapping non-convex polyominoes to create a convex one. 680 681 Then, there are two cases: either the two resulting polyominoes are separated by a perfectly vertical or horizontal cut, or they share some rows. The first case is easy to check in linear time. The remainder of the solution will focus on the second case. 682 683 Consider the structure of a valid partition. We will focus on the perimeter:  684 685 Notice that the cut separating the two polyominoes must only ever move down and right, or up and right, as otherwise one of the formed polyominoes will not be convex. Without loss of generality, say it only goes down and right. 686 687 In order for our cut to be valid, it must partition the perimeter into six segments as shown, such that the marked segments are congruent in the indicated orientations ($a$ with $a$, $b$ with $b$, $c$ with $c$.) If we label the horizontal lines of the grid to be $0, \dots, n$ where line $i$ is located after row $i$, we notice that the division points along the left side of the original polyomino are located at lines $0, k, 2k$ for some $1 \leq k \leq n/2$. 688 689 Notice that if we were to fix a given $k$, we can uniquely determine the lower polyomino from the first few rows of the upper polyomino. Indeed, if $a_i = r_i - \ell_i + 1$ denotes the width of the $i$-th row of the original polyomino, we can show that the resulting polyomino for a particular choice of $k$ has 690 691 $b_i = a_i - a_{i-k} + a_{i-2k} - \dots$ 692 693 cells in its $i$-th row, for $1 \leq i \leq n - k$. Therefore, iterating over all possible $k$ and checking them individually gives an $O(n^2)$ solution. 694 695 To speed this up, we will develop a constant-time check that will prune ``most'' choices of $k$. Indeed, we may use prefix sums and hashing to verify the perimeter properties outlined above, so that we can find all $k$ that pass this check in $O(n)$ time. If there are at most $f(n)$ choices of $k$ afterwards, we can check them all for a solution in $O(n \cdot (f(n) + \text{hashing errors}))$. 696 697 It can actually be shown that for our hashing protocol, $f(n) \leq 9$, so that this algorithm has linear time complexity. While the proof is not difficult, it is rather long and will be left as an exercise. Instead, we will give a simpler argument to bound $f(n)$. Fix some choice of $k$, and consider the generating functions 698 699 $A(x) = a_0 + a_1 x + \dots + a_n x^n,$ $B(x) = b_0 + b_1 x + \dots + b_{n-k} x^{n-k}.$ 700 701 The perimeter conditions imply that $(1 + x^k) B(x) = A(x)$. In other words, $k$ may only be valid if $(1 + x^k)$ divides $A(x)$. Therefore, we can use [cyclotomic polynomials](https://en.wikipedia.org/wiki/Cyclotomic_polynomial) for $1 + x^k \mid x^{2k} - 1$ to determine that 702 703 $f(n) \leq \text{maximum number of cyclotomic polynomials that can divide a degree}\ n\ \text{polynomial}.$ 704 705 As the degree of the $k$-th cyclotomic polynomial is $\phi(k)$ for the Euler totient function $\phi$, we can see that $f(n)$ is also at most the maximum number of $k_i \leq n$ we can select with $\sum_i \phi(k_i) \leq n$. Since $\phi(n) \geq \frac{n}{\log \log n}$, this tells us that 706 707 $f(n) = O(\sqrt n \cdot \log \log n)$ 708 709 and this looser bound already yields a time complexity of at most $O(n \sqrt n \cdot \log \log n).$ **While this concludes the official solution,** there exist many other heuristics with different $f(n)$ that also work. 710 711 --- 712 713 It is in the spirit of the problem to admit many alternate heuristics that give small enough $f(n)$ ``in practice'', as the official solution uses hashing. One such heuristic found by testers is as follows: 714 715 We take as our pruning criteria that the area of the subdivided polyomino $\sum_{i=1}^{n-k} b_i$ is exactly half of the area of the original polyomino, which is $\sum_{i=1}^n a_i$. Algebraically manipulating $\sum_{i=1}^{n-k} b_i$ to be a linear function of $a_i$ shows it to be equal to 716 717 $(a_1 + \dots + a_k) - (a_{k+1} + \dots + a_{2k}) + \dots.$ 718 719 The calculation of all these sums may be sped up with prefix sums, and therefore pruning of $k$, can be done in amortized $O(n \log n)$ time since any fixed choice of $k$ has $\frac nk$ segments. 720 721 However, for this choice of pruning, it can actually be shown that $f(n) \geq \Omega(d(n))$, where $d(n)$ is the number of divisors of $n$. This lower bound is obtained at an even-sized diamond polyomino, e.g. 722 723 $(a_1, \dots, a_n) = (2, 4, \dots, n, n, \dots, 4, 2).$ 724 725 Despite our efforts, we could not find an upper bound on $f(n)$ in this case, though we suspect that if it were not for the integrality and bounding constraints $a_i \in {1, \dots, 10^9}$, then $f(n) = \Theta(n)$, with suitable choices of $a_i$ being found using linear programs. Nevertheless, the solution passes our tests, and we suspect that no countertest exists (though hacking attempts on such solutions would be interesting to see!). 726 727 **Implementation** 728 729 ``` 730 #include <bits/stdc++.h> 731 732 #define f first 733 #define s second 734 735 typedef long long int ll; 736 typedef unsigned long long int ull; 737 using namespace std; 738 typedef pair<int,int> pii; 739 typedef pair<ll,ll> pll; 740 741 void print_set(vector<int> x) { 742 for (auto i : x) { 743 cout << i << " "; 744 } 745 cout << endl; 746 } 747 748 void print_set(vector<ll> x) { 749 for (auto i : x) { 750 cout << i << " "; 751 } 752 cout << endl; 753 } 754 755 bool connected(vector<ll> &U, vector<ll> &D) { 756 if (U[0] > D[0]) return 0; 757 for (int i = 1; i < U.size(); i++) { 758 if (U[i] > D[i]) return 0; 759 if (D[i] < U[i-1]) return 0; 760 if (U[i] > D[i-1]) return 0; 761 } 762 return 1; 763 } 764 765 bool compare(vector<ll> &U1, vector<ll> &D1, vector<ll> &U2, vector<ll> &D2) { 766 if (U1.size() != U2.size()) return 0; 767 if (!connected(U1, D1)) return 0; 768 for (int i = 0; i < U1.size(); i++) { 769 if (U1[i] - D1[i] != U2[i] - D2[i]) return 0; 770 if (U1[i] - U1[0] != U2[i] - U2[0]) return 0; 771 } 772 return 1; 773 } 774 775 bool horizontal_check(vector<ll>& U, vector<ll>& D) { 776 if (U.size() % 2) return 0; 777 int N = U.size() / 2; 778 auto U1 = vector<ll>(U.begin(), U.begin() + N); 779 auto D1 = vector<ll>(D.begin(), D.begin() + N); 780 auto U2 = vector<ll>(U.begin() + N, U.end()); 781 auto D2 = vector<ll>(D.begin() + N, D.end()); 782 return compare(U1, D1, U2, D2); 783 } 784 785 bool vertical_check(vector<ll>& U, vector<ll>& D) { 786 vector<ll> M1, M2; 787 for (int i = 0; i < U.size(); i++) { 788 if ((U[i] + D[i]) % 2 == 0) return 0; 789 M1.push_back((U[i] + D[i]) / 2); 790 M2.push_back((U[i] + D[i]) / 2 + 1); 791 } 792 return compare(U, M1, M2, D); 793 } 794 795 ll base = 2; 796 ll inv = 1000000006; 797 ll mod = 2000000011; 798 799 vector<ll> base_pows; 800 vector<ll> inv_pows; 801 void precompute_powers() { 802 base_pows.push_back(1); 803 inv_pows.push_back(1); 804 for (int i = 1; i <= 300000; i++) { 805 base_pows.push_back(base_pows.back() * base % mod); 806 inv_pows.push_back(inv_pows.back() * inv % mod); 807 } 808 } 809 810 ll sub(vector<ll> &hash_prefix, int a1, int b1) { 811 return ((mod + hash_prefix[b1] - hash_prefix[a1]) * inv_pows[a1]) % mod; 812 } 813 814 int main() 815 { 816 ios_base::sync_with_stdio(false); 817 cin.tie(0); 818 819 precompute_powers(); 820 821 int T; cin >> T; 822 while (T--) { 823 int N; cin >> N; 824 vector<ll> U(N), D(N), H(N); 825 vector<pii> col_UL(N), col_DR(N+1); 826 vector<ll> hash_prefix_U(N), hash_prefix_D(N); 827 for (int i = 0; i < N; i++) { 828 cin >> U[i] >> D[i]; 829 H[i] = D[i] - U[i] + 1; 830 col_UL[i] = {i,U[i]}; 831 col_DR[i] = {i+1,D[i]+1}; 832 } 833 834 // hashing 835 for (int i = 1; i < N; i++) { 836 hash_prefix_U[i] = (((mod + U[i] - U[i-1]) * base_pows[i-1]) 837 + hash_prefix_U[i-1]) % mod; 838 } 839 840 for (int i = 1; i < N; i++) { 841 hash_prefix_D[i] = (((mod + D[i] - D[i-1]) * base_pows[i-1]) 842 + hash_prefix_D[i-1]) % mod; 843 } 844 845 // horizontal split 846 if (horizontal_check(U, D)) { 847 cout << "YES" << endl; 848 goto next; 849 } 850 851 // vertical split 852 if (vertical_check(U, D)) { 853 cout << "YES" << endl; 854 goto next; 855 } 856 857 for (int _ = 0; _ < 2; _++) { 858 // down-right split 859 for (int c = 1; c <= N/2; c++) { 860 // check upper portion 861 if (sub(hash_prefix_U, 0, c-1) != sub(hash_prefix_U, c, 2*c-1)) continue; 862 if (H[0] - U[2*c] + U[2*c-1] != U[c-1] - U[c]) continue; 863 864 // check lower portion 865 if (sub(hash_prefix_D, N-c, N-1) != sub(hash_prefix_D, N-2*c, N-c-1)) continue; 866 if (H[N-1] + D[N-2*c-1] - D[N-2*c] != D[N-c-1] - D[N-c]) continue; 867 868 // check main portion 869 if (sub(hash_prefix_U, 2*c, N-1) != sub(hash_prefix_D, 0, N-2*c-1)) continue; 870 871 // brute force section 872 // polynomial division 873 bool ok = 1; 874 vector<ll> H_copy(H.begin(), H.end()); 875 vector<ll> quotient(N); 876 877 // calculate quotient 878 for (int i = 0; i < N-c; i++) { 879 quotient[i] = H_copy[i]; 880 H_copy[i+c] -= H_copy[i]; 881 if (quotient[i] < 0) ok = 0; 882 } 883 884 // check for no remainder 885 for (int i = N-c; i < N; i++) if (H_copy[i]) ok = 0; 886 if (!ok) continue; 887 888 // construct subdivision 889 vector<ll> U1, D1, U2, D2; 890 for (int i = c; i < N; i++) { 891 int ref_height = quotient[i-c]; 892 U1.push_back(D[i-c] - ref_height + 1); 893 D1.push_back(D[i-c]); 894 U2.push_back(U[i]); 895 D2.push_back(U[i] + ref_height - 1); 896 } 897 898 if (compare(U1, D1, U2, D2)) { 899 cout << "YES" << endl; 900 goto next; 901 } 902 } 903 904 // flip and go again! 905 swap(hash_prefix_U, hash_prefix_D); 906 swap(U, D); 907 for (int i = 0; i < N; i++) { 908 U[i] = -U[i]; 909 D[i] = -D[i]; 910 } 911 } 912 cout << "NO" << endl; 913 next:; 914 } 915 return 0; 916 } 917 ```