codeforces-scrape

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

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: ![ ](/predownloaded/e6/0c/e60c78105be7516f7e7f5fc60f889abdbfbbe402.png)
    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 ```