codeforces-scrape

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

2248.md (24832B)


      1 Source: https://codeforces.com/blog/entry/155640
      2 
      3 [2248A - Ты удаляешь, я удаляю](/contest/2248/problem/A "Codeforces Round 1113 (Div. 2)")
      4 
      5 **Hint1**
      6 
      7 Alice deletes a `0`, Bob deletes a `1`. Which occurrence should each of them choose?
      8 
      9 **Hint2**
     10 
     11 Deleting a `0` makes the string lexicographically larger. Does the position of that `0` matter?
     12 
     13 **Hint3**
     14 
     15 After Alice's move, Bob sees one string and deletes a `1`. What is his best move?
     16 
     17 **Solution**
     18 
     19 Deleting a `0` at an earlier position is always better for Alice. Indeed, compare deleting the `0`s at positions $i \lt j$: the two results agree before position $i$, and at position $i$ the first result has `1` while the second still has `0`. So Alice deletes the **first** `0`.
     20 
     21 After that, Bob wants to minimize the string. By the symmetric argument he deletes the **first** `1` of the remaining string, which is the first `1` of the original string, since deleting a `0` never changes the order of the `1`s.
     22 
     23 Hence the answer is the original string with its first `0` and its first `1` removed.
     24 
     25 **Complexity:** $O(n)$ per test case.
     26 
     27 **Code**
     28 
     29 ```
     30 #include <cstdio>
     31 #include <cstring>
     32 const int N = 105;
     33 char str[N];
     34 void solve() {
     35     scanf("%s", str + 1);
     36     int n = strlen(str + 1);
     37     bool c0 = 0, c1 = 0;
     38     for (int i = 1; i <= n; i++) {
     39         if (!c0 && str[i] == '0') {
     40             c0 = true;
     41             continue;
     42         }
     43         if (!c1 && str[i] == '1') {
     44             c1 = true;
     45             continue;
     46         }
     47         putchar(str[i]);
     48     }
     49     puts("");
     50 }
     51 int main() {
     52     int t = 0;
     53     scanf("%d", &t);
     54     while (t--) solve();
     55     return 0;
     56 }
     57 ```
     58 
     59 **Code (Brute Force)**
     60 
     61 ```
     62 #include<bits/stdc++.h>
     63 using namespace std;
     64 
     65 #define ll long long
     66 #define nline "\n"
     67 #define sz(x) (int)x.size()
     68 
     69 void solve(){
     70 	string s; cin>>s;
     71 	string ans;
     72 	for(int i=0;i<sz(s);i++){
     73 		if(s[i]=='1'){
     74 			continue;
     75 		}
     76 		string t=s;
     77 		t.erase(t.begin()+i);
     78 		string cur;
     79 		for(int j=0;j<sz(t);j++){
     80 			if(t[j]=='0'){
     81 				continue;
     82 			}
     83 			string now=t;
     84 			now.erase(now.begin()+j);
     85 			if((cur.empty()) or (now<cur)){
     86 				cur=now;
     87 			}
     88 		}
     89 		if((ans.empty()) or (ans<cur)){
     90 			ans=cur;
     91 		}
     92 	}
     93 	cout<<ans<<nline;
     94 	return;
     95 }
     96 
     97 int main(){
     98 	ios_base::sync_with_stdio(false);
     99 	cin.tie(NULL);
    100 	ll test_cases=1;
    101 	cin>>test_cases;
    102 	while(test_cases--){
    103 		solve();
    104 	}
    105 }
    106 ```
    107 
    108 [2248B - Слияние для совпадения](/contest/2248/problem/B "Codeforces Round 1113 (Div. 2)")
    109 
    110 **Hint1**
    111 
    112 Sort both arrays. Each operation reduces the number of elements by exactly one.
    113 
    114 **Hint2**
    115 
    116 All values are distinct, so no final element can be an untouched original element. What lower bound on $n$ does this give?
    117 
    118 **Hint3**
    119 
    120 After sorting, in which interval of $a$ must the $i$-th smallest value $b_i$ lie?
    121 
    122 **Solution**
    123 
    124 Sort both arrays. An operation merges two elements $x \le y$ into any $z \in [x,y]$, so think of each final element as the merge of a group of original elements whose min/max bracket its value.
    125 
    126 **Necessity.**
    127 
    128 * **$n \ge 2m$.** The values in $b$ are distinct from those in $a$, so a final element consisting of a single original element is impossible. Every final element needs at least two originals.
    129 * **$a_i \le b_i \le a_{n-m+i}$.** The $i$ smallest final values are produced by $i$ groups containing at least $i$ original elements, all $\le b_i$. Only $i-1$ original elements are smaller than $a_i$, so $b_i \ge a_i$. The symmetric argument on the largest values gives $b_i \le a_{n-m+i}$.
    130 
    131 **Sufficiency.** If the conditions hold, pair $a_i$ with $a_{n-m+i}$ for each $i$ (the pairs are disjoint since $n \ge 2m$) and merge each pair into $b_i$. The remaining middle elements can be attached to any group one by one: merging the current group value $b_1$ with an extra element $e$ yields $b_1$ again, because $b_1$ lies between them.
    132 
    133 **Complexity:** $O((n+m)\log(n+m))$ per test case.
    134 
    135 **Code**
    136 
    137 ```
    138 using namespace std;
    139 
    140 int main() {
    141 	int T;
    142 	scanf("%d", &T);
    143 	for (int _ = 0; _ < T; ++_) {
    144 		int n, m;
    145 		scanf("%d %d", &n, &m);
    146 		vector<int> a(n), b(m);
    147 		for (int &x : a) {
    148 		    scanf("%d", &x);
    149 		}
    150 		for (int &x : b) {
    151 			scanf("%d", &x);
    152 		}
    153 		sort(a.begin(), a.end());
    154 		sort(b.begin(), b.end());
    155 
    156 		if (n < 2 * m) {
    157 			puts("NO");
    158 			continue;
    159 		}
    160 
    161 		int i = 0;
    162 		while (i < m && a[i] < b[i] && b[i] < a[n - m + i]) ++i;
    163 		puts(i < m ? "no" : "Yes");
    164 	}
    165 	return 0;
    166 }
    167 ```
    168 
    169 [2248C - Максимизируйте счёт](/contest/2248/problem/C "Codeforces Round 1113 (Div. 2)")
    170 
    171 **Hint1**
    172 
    173 If a value is chosen when some elements between its two occurrences were already deleted, move its deletion earlier. When is this never worse? Think about $(a+b)^2 \ge a^2 + b^2$.
    174 
    175 **Hint2**
    176 
    177 Conclude that the process is equivalent to partitioning the array into disjoint blocks: each block is either a single position, or the whole interval between two equal values at its ends.
    178 
    179 **Hint3**
    180 
    181 DP over the prefix. Consider the block containing the last position.
    182 
    183 **Solution**
    184 
    185 Call an operation **full** if it deletes the entire original interval between the two occurrences of the chosen value.
    186 
    187 **Lemma.** There is an optimal strategy in which every operation is full.
    188 
    189 Suppose a value is chosen with current span $p \dots q$, while an interval $J$ strictly inside its original span was deleted earlier. Swap the two deletions: the value now covers the whole original interval. If the two original lengths are $A$ and $B$ ($A \ge B$), the score changes from at most $(A-B)^2 + B^2$ to $A^2$, and $(A-B)^2 + B^2 \le A^2$. So the total never decreases, and repeating this exchange makes every operation full.
    190 
    191 Now the deleted intervals are disjoint, and the whole process is exactly: partition the array into blocks, each being a single position or the interval between the two equal values at its ends, and collect $\sum (\text{block length})^2$.
    192 
    193 Let $dp[i]$ be the best score for the prefix $a_1 \dots a_i$. The block containing position $i$ is either the singleton ${i}$, or the interval $[l,i]$ where $l$ is the first occurrence of $a_i$:
    194 
    195 $ dp[i] = \max\big(dp[i-1] + 1,\; dp[l-1] + (i-l+1)^2\big). $
    196 
    197 The singleton option never overestimates: if the mate of $a_i$ is still present in the optimal strategy of the prefix, deleting $[l,i]$ instead is at least as good, since $(i-l+1)^2 \ge (i-l)^2 + 1$.
    198 
    199 The answer is $dp[2n]$.
    200 
    201 **Complexity:** $O(n)$ per test case.
    202 
    203 **Code**
    204 
    205 ```
    206 #include <bits/stdc++.h>
    207 using namespace std;
    208 
    209 int main() {
    210 	int T;
    211 	scanf("%d", &T);
    212 	for (int _ = 0; _ < T; ++_) {
    213 		int n;
    214 		scanf("%d", &n);
    215 		vector<int> a(2 * n);
    216 		for (int &x : a) {
    217 			scanf("%d", &x);
    218 		}
    219 
    220 		vector<int> lp(2 * n, -1);
    221 		vector<int> occ(n, -1);
    222 		for (int i = 0; i < 2 * n; ++i) {
    223 			if (occ[a[i] - 1] != -1) {
    224 				lp[i] = occ[a[i] - 1];
    225 			} else {
    226 				occ[a[i] - 1] = i;
    227 			}
    228 		}
    229 
    230 		vector<long long> dp(2 * n);
    231 		dp[0] = 1;
    232 		for (int i = 1; i < 2 * n; ++i) {
    233 			dp[i] = dp[i - 1] + 1;
    234 			if (lp[i] != -1) {
    235 				dp[i] = max(dp[i], (lp[i] == 0 ? 0 : dp[lp[i] - 1]) + 1LL * (i - lp[i] + 1) * (i - lp[i] + 1));
    236 			}
    237 		}
    238 		printf("%lld\n", dp[2 * n - 1]);
    239 	}
    240 }
    241 ```
    242 
    243 [2248D - Запросы хороших пар](/contest/2248/problem/D "Codeforces Round 1113 (Div. 2)")
    244 
    245 **Hint1**
    246 
    247 Classify each position by the pair $(s_i, t_i)$ and count the four types: $(0,0)$, $(0,1)$, $(1,0)$, $(1,1)$.
    248 
    249 **Hint2**
    250 
    251 Find a quantity that only decreases during the game, and equals $0$ at the end.
    252 
    253 **Hint3**
    254 
    255 Which pairs of columns can be deleted together in one operation? When can all columns be paired up?
    256 
    257 **Solution**
    258 
    259 For a substring pair let $x=N(0,1)$, $y=N(1,0)$, $u=N(0,0)$, $v=N(1,1)$, where $N(0,1)$ denotes the number occurrences of $(0,1)$.
    260 
    261 **Claim.** The pair is good iff $|x-y| \le u+v$.
    262 
    263 **Necessity**: Take any allowed operation. Let the deleted columns have counts $u_0, v_0, x_0, y_0$ and total $k = u_0+v_0+x_0+y_0$.
    264 
    265 **Case $c=0$:**  
    266 In the deleted subsequence of $s$, character $0$ appears $u_0+x_0$ times; in $t$ it appears $u_0+y_0$ times.  
    267 Mode condition:
    268 
    269 $ u_0+x_0 \ge \lceil k/2 \rceil,\qquad u_0+y_0 \ge \lceil k/2 \rceil . $
    270 
    271 Adding them: $2u_0 + x_0 + y_0 \ge k = u_0+v_0+x_0+y_0$ $\Rightarrow$ $u_0 \ge v_0$.  
    272 Subtracting one from the other gives $|x_0 - y_0| \le u_0 - v_0 \le u_0 + v_0$.
    273 
    274 **Case $c=1$:** similarly $v_0 \ge u_0$ and $|x_0 - y_0| \le v_0 - u_0 \le u_0 + v_0$.
    275 
    276 Thus **every operation** satisfies $|x_0 - y_0| \le u_0+v_0$.
    277 
    278 Now define the potential $\Phi = |x-y| - (u+v)$.  
    279 After one operation the change is
    280 
    281 $ \Phi' - \Phi = \bigl(|x-x_0 - (y-y_0)| - |x-y|\bigr) + (u_0+v_0). $
    282 
    283 By the triangle inequality, $|x-y| - |(x-y)-(x_0-y_0)| \le |x_0-y_0|$.  
    284 Therefore
    285 
    286 $ \Phi' - \Phi = (u_0+v_0) - \bigl(|x-y| - |(x-y)-(x_0-y_0)|\bigr) \ge u_0+v_0 - |x_0-y_0| \ge 0. $
    287 
    288 So $\Phi$ never decreases.  
    289 The empty pair has $\Phi = 0$. Hence initially $\Phi \le 0$, i.e. $|x-y| \le u+v$.
    290 
    291 **Sufficiency**: We can empty the strings by repeatedly deleting columns in groups of size 1 or 2.
    292 
    293 A single column can be deleted alone **iff** it is pure: $(0,0)$ (mode $0$) or $(1,1)$ (mode $1$). Two columns can be deleted together **iff** they are **not** two identical mixed columns:
    294 
    295 * $(0,0)$ pairs with anything.
    296 * $(1,1)$ pairs with anything.
    297 * $(0,1)$ pairs with $(1,0)$.
    298 
    299 So we can pair $\min(x,y)$ copies of $(0,1)$ with $(1,0)$, and the remaining $|x-y|$ mixed columns (all of the same type) are paired with pure columns $(0,0)$ or $(1,1)$. This is possible exactly because $u+v \ge |x-y|$.
    300 
    301 The leftover $u+v-|x-y|$ pure columns are paired arbitrarily among themselves. If the total number of columns is odd, exactly one pure column remains and can be deleted alone.
    302 
    303 All these pairs / singletons are valid operations. After their deletion the strings become empty, so the pair is good.
    304 
    305 Precompute prefix sums for the four column types. For a query $[l,r]$ obtain the four counts $u,v,x,y$ in constant time. Answer yes if $|x-y| \le u+v$, otherwise no.
    306 
    307 **Complexity:** $O(n+q)$ per test case.
    308 
    309 **Code**
    310 
    311 ```
    312 #include <cstdio>
    313 #include <cstring>
    314 #include <cctype>
    315 #include <algorithm>
    316 #include <iostream>
    317 #include <queue>
    318 typedef long long LL;
    319 using namespace std;
    320 inline int read() {
    321     int num = 0 ,f = 1; char c = getchar();
    322     while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    323     while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    324     return num * f;
    325 }
    326 const int N = 2e5 + 5;
    327 char s[N] ,t[N];
    328 int sum[4][N] ,n ,q;
    329 inline void fuling_solve() {
    330     n = read() ,q = read();
    331     scanf("%s%s" ,s + 1 ,t + 1);
    332     for (int j = 0; j < 4; j++) sum[j][0] = 0;
    333     for (int i = 1; i <= n; i++) {
    334         int id = (s[i] ^ 48) * 2 + (t[i] ^ 48);
    335         for (int j = 0; j < 4; j++) sum[j][i] = sum[j][i - 1] + (id == j);
    336     }
    337     while (q--) {
    338         int l = read() ,r = read();
    339         int a = sum[0][r] - sum[0][l - 1];
    340         int b = sum[1][r] - sum[1][l - 1];
    341         int c = sum[2][r] - sum[2][l - 1];
    342         int d = sum[3][r] - sum[3][l - 1];
    343         puts(abs(b - c) <= a + d ? "YES" : "NO");
    344     }
    345 }
    346 signed main() {
    347     int t = read();
    348     while (t--) fuling_solve();
    349     return 0;
    350 }
    351 ```
    352 
    353 **Bonus Question**
    354 
    355 We have consider to change this problem to a harder version: Find number of pairs $(l, r) (1 \le l \le r \le n)$ such that $(s[l, r], t[l, r])$ is good.
    356 
    357 Can you solve this too?
    358 
    359 [2248E - Извинение за перерывы](/contest/2248/problem/E "Codeforces Round 1113 (Div. 2)")
    360 
    361 **Hint1**
    362 
    363 Let $S_i = F(I(i))$. Since the counter resets at $n$, $S_{i+n} = S_i + S_n$.
    364 
    365 **Hint2**
    366 
    367 If $S_x + S_y \gt S_{x+y+1}$ for some $x,y$, the array $I(x),[0],I(y)$ already wins. Conversely, if no such pair exists, every array loses.
    368 
    369 **Hint3**
    370 
    371 For fixed $y$, the function $S_x + S_y - S_{x+y+1}$ changes only when $x+1$ or $x+y+2$ is a reward point. Where is its maximum attained?
    372 
    373 **Solution**
    374 
    375 Let $S_i = F(I(i))$ ($S_0 = 0$). The counter resets exactly at $n$, so $S_{i+n} = S_i + S_n$; also $F$ is additive across a `0`: if a string ends with `0`, the next part starts from $c=0$.
    376 
    377 Define
    378 
    379 $ M = \max_{x,y \ge 1} \big(S_x + S_y - S_{x+y+1}\big). $
    380 
    381 **Claim.** $F(s) \le S_{|s|} + \max(M,0)$ for every binary array $s$, with equality for $s = I(x),[0],I(y)$ at a maximizing pair. Hence the answer is `YES` iff $M \gt 0$.
    382 
    383 Induct on the number of runs. If $s$ has no `0`, then $F(s) = S_{|s|}$. Otherwise write $s = I(x),[0],t$ with $x$ leading ones. Then
    384 
    385 $F(s) = S_x + F(t) \le S_x + S_{|t|} + \max(M,0) \le S_{|s|} + \max(M,0),$
    386 
    387 because $S_x + S_{|t|} - S_{x+|t|+1} \le M$.
    388 
    389 **Only reward thresholds matter.** Let $g(x,y) = S_x + S_y - S_{x+y+1}$. By periodicity $g$ is $n$-periodic in each variable. Fix $y$:
    390 
    391 $g(x+1,y) - g(x,y) = (S_{x+1}-S_x) - (S_{x+y+2}-S_{x+y+1}),$
    392 
    393 which is positive only when $x+1$ is a reward point $p_i$. On the circle of residues modulo $n$, the maximum is attained on a plateau whose left end is congruent to some $p_i$ — so some $x = p_i$ attains it. The same argument in $y$ gives
    394 
    395 $ M = \max_{1 \le i,j \le m} \big(S_{p_i} + S_{p_j} - S_{p_i+p_j+1}\big). $
    396 
    397 (If $m=0$, then $S_x = dx$ and $M = -d \le 0$.)
    398 
    399 **Algorithm.** All needed values of $S$ follow from the periodic formula $S_i = \lfloor i/n\rfloor S_n + S_{i\bmod n}$. For each pair $(i,j)$, locate $p_i+p_j+1$ among the sorted points ${p_1,\dots,p_m, n+p_1,\dots,n+p_m}$ with a two-pointer scan; if $S_{p_i}+S_{p_j} \gt S_{p_i+p_j+1}$ for some pair, print `YES`.
    400 
    401 **Complexity:** $O(m^2)$ per test case ($\sum m \le 2000$).
    402 
    403 **Code**
    404 
    405 ```
    406 import sys
    407 input = sys.stdin.readline
    408 
    409 class Point:
    410     def __init__(self, t, v):
    411         self.t = t
    412         self.v = v
    413 
    414 srw = [Point(0, 0) for _ in range(4100)]
    415 
    416 T = int(input())
    417 for _ in range(T):
    418     n, m, d = map(int, input().split())
    419     for i in range(1, m+1):
    420         t, v = map(int, input().split())
    421         srw[i].t = t
    422         srw[i].v = v + srw[i-1].v
    423     for i in range(1, m+1):
    424         srw[m+i] = Point(n + srw[i].t, srw[m].v + srw[i].v)
    425     ok = False
    426     for i in range(1, m+1):
    427         k = i
    428         for j in range(1, m+1):
    429             st = srw[i].t + 1 + srw[j].t
    430             while k+1 <= 2*m and srw[k+1].t <= st:
    431                 k += 1
    432             if srw[i].v + srw[i].t*d + srw[j].v + srw[j].t*d > srw[k].v + st*d:
    433                 ok = True
    434     print("Yes" if ok else "No")
    435     for i in range(1, 2*m+1):
    436         srw[i] = Point(0, 0)
    437 ```
    438 
    439 [2248F - Устранение матрицы](/contest/2248/problem/F "Codeforces Round 1113 (Div. 2)")
    440 
    441 **Hint1**
    442 
    443 Define the deficit $g_{x,y} = \text{rowSum}_x + \text{colSum}_y - 3v_{x,y}$ of a cell. A cell is a peak iff its deficit is $\le 0$. How much can one operation reduce a deficit?
    444 
    445 **Hint2**
    446 
    447 For $n,m \ge 2$, every operation reduces any deficit by at most $n+m-3$, and full-matrix operations achieve this bound for every cell at once. So the problem reduces to a $k$-th smallest value.
    448 
    449 **Hint3**
    450 
    451 In one dimension a cell is a peak iff $2a_i \ge S$ (total sum). Only "full" operations and operations that skip one endpoint matter, and the two endpoint types are never both useful. The rest is a couple of linear inequalities solved in $O(1)$.
    452 
    453 **Solution**
    454 
    455 Let $R_x = \sum_j v_{x,j}$ and $C_y = \sum_i v_{i,y}$. The peak condition is equivalent to
    456 
    457 $ g_{x,y} := R_x + C_y - 3v_{x,y} \le 0. $
    458 
    459 If an operation covers $a$ cells of row $x$ and $b$ cells of column $y$, it changes the deficit by $-(a+b-3)$ when it covers $(x,y)$, and by $-(a+b)$ otherwise. For $n,m \ge 2$ this means the deficit is reduced by at most $n+m-3$ per operation: full coverage gives $a+b-3 \le n+m-3$, while an operation avoiding $(x,y)$ can cover cells of only one of the two lines, contributing at most $\max(n-1,m-1) \le n+m-3$.
    460 
    461 **Case $n,m \ge 2$.** After $T$ operations, cell $(x,y)$ can be a peak only if $g_{x,y} \le T(n+m-3)$. Conversely, $T$ full-matrix operations make every cell with $\lceil g_{x,y}/(n+m-3)\rceil \le T$ a peak simultaneously. Hence the answer is the $k$-th smallest value of
    462 
    463 $ \text{need}_{x,y} = \max\left(0,\ \left\lceil \frac{R_x + C_y - 3v_{x,y}}{n+m-3}\right\rceil\right). $
    464 
    465 **Case $n=1$ or $m=1$.** Rotate to a row of length $L=\max(n,m)$, sum $S$.  
    466 Peak condition: $a_i \ge S-a_i \iff h_i := S-2a_i \le 0$.
    467 
    468 An operation on a segment of length $\ell$ subtracts 1 from each element inside.
    469 
    470 * If $i$ is inside: $h_i$ decreases by $\ell-2$
    471 * If $i$ is outside: $h_i$ decreases by $\ell$
    472 
    473 Only three segment types are useful (others are dominated):
    474 
    475 1. **Full** $[1,L]$: every $h_i$ reduced by $L-2$.
    476 2. **Skip‑first** $[2,L]$: $h_1$ reduced by $L-1$, others by $L-3$.
    477 3. **Skip‑last** $[1,L-1]$: $h_L$ reduced by $L-1$, others by $L-3$.
    478 
    479 **Only full operations**: Same as the general formula with $n+m-3 = L-2$:  
    480 Answer = $k$-th smallest $\left\lceil \frac{S-2a_i}{L-2} \right\rceil$ (with $\max(0,\cdot)$). (This is exactly the `xlim` part in the code).
    481 
    482 **Full + one skip type, with an endpoint among the peaks**: Assume the chosen endpoint is $p$ (either 1 or $L$), using $x$ full and $y$ skip‑$p$ operations ($T=x+y$). Take the other $k-1$ peaks as the cells with the **largest** $a_i$ (smallest $h_i$) among the remaining $L-1$ cells; let $v_k$ be the smallest of these. Reductions: - For $p$: $(L-2)x + (L-1)y = (L-2)T + y$ - For the other $k-1$ cells: $(L-2)x + (L-3)y = (L-2)T - y$
    483 
    484 Requirements:
    485 
    486 $ \begin{aligned} (L-2)T + y &\ge S - 2a_p \quad &(1)\\ (L-2)T - y &\ge S - 2v_k \quad &(2)\\ 0 \le y &\le T . \end{aligned} $
    487 
    488 From the constraints:
    489 
    490 * (2) with $y=0$ gives $T \ge \lceil (S-2v_k)/(L-2) \rceil$
    491 * (1) with $y=T$ gives $T \ge \lceil (S-2a_p)/(L-1) \rceil$
    492 * Adding (1) and (2): $2(L-2)T \ge 2S-2a_p-2v_k \iff T \ge \lceil (S-a_p-v_k)/(L-2) \rceil$
    493 
    494 Set
    495 
    496 $ z = \max\left( \lceil \frac{S-a_p-v_k}{L-2} \rceil,\; \lceil \frac{S-2a_p}{L-1} \rceil \right) $
    497 
    498 (If the first bound $\lceil (S-2v_k)/(L-2) \rceil$ were strictly larger, then $y=0$ is optimal and Strategy of only full operations already covers it.)
    499 
    500 Now we must check whether there exists an integer $y$ satisfying the box constraints:
    501 
    502 $ \max\bigl(0,\; S-2a_p - (L-2)z\bigr) \;\le\; y \;\le\; \min\bigl(z,\; (L-2)z - (S-2v_k)\bigr). $
    503 
    504 If this holds, $T=z$ is feasible and optimal for this endpoint; otherwise the endpoint strategy cannot beat the "only full operations" strategy.
    505 
    506 The code’s `solveL` implements exactly this: it computes $z$, tests feasibility, and returns $z$ if valid or $\infty$ otherwise.  
    507 The final answer is $\min(\text{Strategy full},\; \text{solveL for left endpoint},\; \text{solveL for right endpoint})$.
    508 
    509 **Complexity:** $O(nm)$ per test case.
    510 
    511 **Code**
    512 
    513 ```
    514 import math
    515 
    516 def ceil_div(a, b):
    517     return (a + b - 1) // b
    518 
    519 def solveL(v, v1, s, k):
    520     n = len(v) + 1
    521     if k == 1:
    522         return max(0, ceil_div(s - 2 * v1, n - 1))
    523     v.sort(reverse=True)
    524     vk = v[k - 2]
    525     z = max(ceil_div(s - v1 - vk, n - 2), ceil_div(s - 2 * v1, n - 1))
    526     if min(z, (n - 2) * z - s + 2 * vk) >= max(0, s - (n - 2) * z - 2 * v1):
    527         return z
    528     return math.inf
    529 
    530 T = int(input())
    531 for _ in range(T):
    532     n, m, k = map(int, input().split())
    533     s = 0
    534     u, rs, cs = [], [0] * n, [0] * m
    535     v = []
    536     for _ in range(n):
    537         row = list(map(int, input().split()))
    538         v.append(row)
    539         s += sum(row)
    540         rs[_] = sum(row)
    541         for j in range(m):
    542             cs[j] += row[j]
    543             u.append(row[j])
    544 
    545     if n + m <= 3:
    546         u.sort()
    547         if k == 1:
    548             if n + m == 2 and u[0] < 0:
    549                 print(-1)
    550             else:
    551                 print(0)
    552         else:
    553             print(abs(u[0] - u[1]))
    554         continue
    555 
    556     xlim = []
    557     for i in range(n):
    558         for j in range(m):
    559             xlim.append(max(0, ceil_div(rs[i] + cs[j] - 3 * v[i][j], n + m - 3)))
    560 
    561     xlim.sort()
    562     ans = xlim[k - 1]
    563 
    564     if m == 1 or n == 1:
    565         ans = min(ans, solveL(u[:-1], u[-1], s, k))
    566         ans = min(ans, solveL(u[1:], u[0], s, k))
    567     print(ans)
    568 ```
    569 
    570 [2248G - На балансе пусто](/contest/2248/problem/G "Codeforces Round 1113 (Div. 2)")
    571 
    572 **Hint1**
    573 
    574 A purchase is a transaction: spend an achievable amount $x$, gain rebate $r(x)$, net change $r(x)-x$. The achievable spends form a knapsack.
    575 
    576 **Hint2**
    577 
    578 Below the smallest spend that yields a net increase, the balance only decreases; reachability is a DP on a DAG.
    579 
    580 **Hint3**
    581 
    582 Above that threshold the balance can grow without bound, and every transaction changes it by a multiple of a single gcd. What determines whether $0$ is reachable?
    583 
    584 **Hint4**
    585 
    586 If the smallest threshold does not exceed the cheapest product, every purchase is discounted and no positive balance can ever become $0$.
    587 
    588 **Solution**
    589 
    590 Let $V = \max(s, a_m)$ and compute the set $C$ of spend amounts achievable up to $V$ with an unbounded knapsack over the prices (a bitset, $O(V^2/64)$). The rebate for a spend $x$ is $r(x) = \max{b_j : a_j \le x}$, obtained by a prefix maximum.
    591 
    592 For every achievable $x$:
    593 
    594 * if $r(x) \lt x$, the net decrease is $d = x - r(x)$; keep $L[d] = \min{x}$ — the cheapest way to lose exactly $d$;
    595 * if $r(x) \gt x$, the purchase increases the balance; let $\text{mnip}$ be the smallest such spend.
    596 
    597 **Below $\text{mnip}$.** Every affordable transaction has $r(x) \le x$, so the balance only decreases. Define $f[0] = 1$ and
    598 
    599 $ f[i] = \bigvee_{d \le i} \big(L[d] \le i \text{ and } f[i-d]\big). $
    600 
    601 This is a DAG (all transitions go down); using the minimum spend for each decrease $d$ is optimal because a cheaper transaction is only more flexible. A shifted bitset computes all $f[i]$ in $O(V^2/64)$.
    602 
    603 **At or above $\text{mnip}$.** A net-increasing purchase is affordable and can be repeated, so the balance can be made arbitrarily large. Every transaction changes the balance by a multiple of
    604 
    605 $ g = \gcd(I,\ D,\ c_1, \dots, c_n,\ b_m), $
    606 
    607 so the residue of the balance modulo $g$ is invariant, and from a sufficiently large balance every value in the same residue class is reachable (Frobenius). Any path to $0$ must enter the decreasing region: for the last purchase, $b - x + r(x) = 0$ with $x \le b$ forces $r(x) = 0$ and $x = b \lt a_1$. Therefore a balance $i \ge \text{mnip}$ can reach $0$ iff $i \equiv 0 \pmod g$ and some positive balance below $\text{mnip}$ is reachable.
    608 
    609 The second condition is automatic when $a_1 \gt c_{\min}$: the spend $c_{\min}$ (the cheapest product) has rebate $0$, so $f[c_{\min}] = 1$ and $c_{\min} \lt \text{mnip}$. Conversely, if $a_1 \le c_{\min}$, every purchase has $r(x) \ge b_1 \ge 1$, so a purchase of cost $x \le h$ leaves balance $h - x + r(x) \gt 0$ — no positive balance can ever become $0$.
    610 
    611 Here $I$ and $D$ are the net increases/decreases found above, and the costs and $b_m$ stand in for the spends beyond $V$: for $x \ge a_m$ the net change is $x - b_m$, and since all achievable spends are multiples of $\gcd(c_1,\dots,c_n)$, the whole tail contributes exactly $\gcd(c_1,\dots,c_n, b_m)$.
    612 
    613 **Complexity:** $O(V^2/64)$ time and $O(V)$ memory, with $V = \max(s, a_m) \le 125\,000$.
    614 
    615 **Code**
    616 
    617 ```
    618 #include <bits/stdc++.h>
    619 using namespace std;
    620 
    621 const int maxV = 125000 + 5;
    622 
    623 int Lgcd(const vector<int> &v) {
    624 	return accumulate(v.begin(), v.end(), 0, [](int a, int b) { return gcd(a, b); });
    625 }
    626 
    627 int main() {
    628 	int n, m, s;
    629 	scanf("%d %d %d", &n, &m, &s);
    630 	vector<int> c(n);
    631 	vector<pair<int, int>> ab(m);
    632 	for (auto &x : c)
    633 		scanf("%d", &x);
    634 	for (auto &[a, b] : ab)
    635 		scanf("%d %d", &a, &b);
    636 	ab.insert(ab.begin(), make_pair(0, 0));
    637 	m += 1;
    638 
    639 	bitset<maxV> p;
    640 	p.set(0);
    641 	for (int x : c)
    642 		p.set(x);
    643 
    644 	const int V = max(s, ab.back().first);
    645 	for (int i = 1; i <= V; ++i) {
    646 		if (p[i])
    647 			p |= (p << i);
    648 	}
    649 
    650 	vector<int> l(V + 1, s + 1);
    651 	l[0] = 0;
    652 	int mnip = s + 1;
    653 	vector<int> I, D;
    654 	for (int i = 1, abp = 0; i <= V; ++i) {
    655 		if (!p[i])
    656 			continue;
    657 		while (abp + 1 < m && ab[abp + 1].first <= i)
    658 			abp += 1;
    659 
    660 		auto [a, b] = ab[abp];
    661 		if (b <= i) {
    662 			l[i - b] = min(l[i - b], i);
    663 			D.push_back(i - b);
    664 		} else {
    665 			I.push_back(b - i);
    666 			mnip = min(mnip, i);
    667 		}
    668 	}
    669 
    670 	vector<pair<int, int>> lv;
    671 	for (int i = 1; i <= V; ++i) {
    672 		if (l[i] <= s)
    673 			lv.emplace_back(l[i], i);
    674 	}
    675 	const int ln = lv.size();
    676 
    677 	sort(lv.begin(), lv.end());
    678 	sort(c.begin(), c.end());
    679 	sort(I.begin(), I.end());
    680 	sort(D.begin(), D.end());
    681 
    682 	bitset<maxV> f, L;
    683 	f.set(0);
    684 	for (int i = 1, lp = 0; i < mnip; ++i) {
    685 		while (lp < ln && lv[lp].first <= i) {
    686 			L.set(maxV - lv[lp].second);
    687 			lp += 1;
    688 		}
    689 
    690 		f[i] = ((f & (L >> (maxV - i)))._Find_first() < V);
    691 	}
    692 
    693 	int Ig = Lgcd(I), Dg = Lgcd(D), cg = Lgcd(c);
    694 	int ugcd = gcd(gcd(Ig, Dg), gcd(cg, ab.back().second));
    695 
    696 	for (int i = 1; i < mnip; ++i)
    697 		puts(f[i] ? "YES" : "NO");
    698 	for (int i = mnip; i <= s; ++i)
    699 		puts((i % ugcd == 0 && ab[1].first > c[0]) ? "YES" : "NO");
    700 	return 0;
    701 }
    702 ```
    703 
    704 I promise I'll improve this soon. I know its unclear and skipped some steps for now.
    705 
    706 Also check out:
    707 
    708 * <https://codeforces.com/blog/entry/155549?#comment-1382258>
    709 * <https://codeforces.com/blog/entry/155640?#comment-1382379>