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>