2148.md (17809B)
1 Source: https://codeforces.com/blog/entry/146112 2 3 #### [2148A - Возвышенная последовательность](/contest/2148/problem/A "Codeforces Round 1050 (Div. 4)") 4 5 **Solution (written by cry)** 6 7 Notice that if we pair each odd-indexed element with an even-indexed element, it sums to $0$. 8 9 Therefore, our strategy is to pair the $2i$'th element with the $(2i+1)$th element until there are no more elements to pair. Note that if $n$ is odd, then there exists an unpaired odd element at the end. In this case, the answer will just be that ending element, which will be $x$. Otherwise, when $n$ is even, we paired every element perfectly and the sum will be $0$. 10 11 Time complexity: $\mathcal{O}(1)$ per test case. 12 13 **Code (C++) (MikeMirzayanov)** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 #define forn(i, n) for (int i = 0; i < int(n); i++) 21 22 int main() { 23 int t; 24 cin >> t; 25 forn(tt, t) { 26 int x, n; 27 cin >> x >> n; 28 if (n % 2 == 0) 29 cout << 0; 30 else 31 cout << x; 32 cout << endl; 33 } 34 } 35 ``` 36 37 #### [2148B - Лазеры](/contest/2148/problem/B "Codeforces Round 1050 (Div. 4)") 38 39 **Solution (written by cry)** 40 41 Since our path is continuous, whatever route we take will always pass through all vertical and horizontal lasers in the region from $(0,0)$ to $(x,y)$ since our movement is bounded inside the region. Therefore, the answer is simply $n + m$. 42 43 Time complexity: $\mathcal{O}(1)$ per test case. 44 45 **Code (C++) (MikeMirzayanov)** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 #define forn(i, n) for (int i = 0; i < int(n); i++) 53 54 int main() { 55 int t; 56 cin >> t; 57 forn(tt, t) { 58 int n, m, x, y, s = 0; 59 cin >> n >> m >> x >> y; 60 61 forn(i, n) 62 cin >> s; 63 forn(i, m) 64 cin >> s; 65 66 cout << n + m << endl; 67 68 } 69 } 70 ``` 71 72 #### [2148C - Тест на выносливость](/contest/2148/problem/C "Codeforces Round 1050 (Div. 4)") 73 74 **Solution (written by cry)** 75 76 In this problem, we want to maximize the amount of points between consecutive requirements. We can ask ourselves the following questions: 77 78 What is the maximum number of points we can obtain between requirements $i$ and $i+1$? The answer is $a_{i+1} - a_i$, by running every minute. When can we run every minute? Only if $(a_{i+1} - a_i)$ and $|b_{i+1} - b_i|$ have the same parity. 79 80 What if they don't have the same parity? Well we can stay in place for one minute, then we can gain $a_{i+1} - a_i - 1$ points. 81 82 The start can be represented by a requirement where $a_0 = 0$ and $b_0 = 0$. Summing up the number of points between all consecutive requirements yields the answer. Remember to add $m - a_n$ to the answer, since we are running until the $m$'th minute. 83 84 Time complexity: $\mathcal{O}(n)$ per test case. 85 86 **Code (C++) (litfan)** 87 88 ``` 89 #include<bits/stdc++.h> 90 using namespace std; 91 92 int main(){ 93 int T; 94 cin >> T; 95 while(T--){ 96 int n, m, x , y; 97 cin >> n >> m; 98 int px = 0, py = 0; 99 int points = 0; 100 while(n--){ 101 cin >> x >> y; 102 points += x - px; 103 if(((x - px + 2) % 2) != ((y - py + 2) % 2))points--; 104 px = x; 105 py = y; 106 } 107 if(px != m){ 108 points += m - px; 109 } 110 cout << points << endl; 111 } 112 } 113 ``` 114 115 #### [2148D - Уничтожение полей одуванчиков](/contest/2148/problem/D "Codeforces Round 1050 (Div. 4)") 116 117 **Solution (written by cry)** 118 119 Firstly, if there is no odd farm, then the answer is $0$ by default since we can never turn the lawnmower on. 120 121 Otherwise, let's first visit an odd farm to turn the lawnmower on. To maximize the number of grass, let's visit the odd farm with the maximum number of grass. Now that the lawnmower is on, we can visit any farm. Since the lawnmower can never turn off when we visit an even farm, let's take advantage of this and visit all the even farms. 122 123 Finally, we are forced to visit odd farms. Note that every other odd farm we visit will turn the lawnmower off. From this, we can see that it is optimal to visit the half of the odd farms with the largest amounts; we will visit them when the lawnmower is on. 124 125 Time complexity: $\mathcal{O}(n \log n)$ per test case. The $\log n$ complexity comes from sorting. 126 127 **Code (C++) (AksLolCoding)** 128 129 ``` 130 #include <bits/stdc++.h> 131 using namespace std; 132 133 void solve() { 134 int n; 135 cin >> n; 136 vector<int> a(n); 137 for (auto &i: a) cin >> i; 138 vector<int> p[2]; 139 for (int i : a) p[i%2].push_back(i); 140 long long ans = 0; 141 if (p[1].size()) ans += accumulate(p[0].begin(), p[0].end(), 0LL); 142 sort(p[1].rbegin(), p[1].rend()); 143 int m = p[1].size(); 144 for (int i = 0; i < (m+1)/2; i++) ans += p[1][i]; 145 cout << ans << '\n'; 146 } 147 148 signed main() { 149 cin.tie(0)->sync_with_stdio(0); 150 int t = 1; 151 cin >> t; 152 while (t--) solve(); 153 } 154 ``` 155 156 #### [2148E - Разделение](/contest/2148/problem/E "Codeforces Round 1050 (Div. 4)") 157 158 **Solution (written by cry)** 159 160 First, let's highlight the important parts of the statement. In my opinion, the most important part is the actual condition for determining whether subarray $a[l, r]$ is awesome, That is: there is some way to place items outside the subarray such that *all multisets contain must the exact same elements* (ignoring ordering). 161 162 There can only be one way that all multisets can contain must the exact same elements. Let $\texttt{cnt}_i$ denote the number of times element $i$ occurs in $a$. Then all multisets must contain exactly $\frac{\texttt{cnt}_i}{k}$ copies of element $i$. 163 164 Now, let's find a closed form for how we determine $a[l, r]$ is awesome. Firstly, we can note that the ordering of elements in the subarray does not matter; only the counts matter. Therefore, let's denote $c_i$ as the number of elements with value $i$ in the subarray. The claim is that the subarray is awesome if and only if $c_i \leq \frac{\texttt{cnt}_i}{k}$ over all $i$. We can show this through some casework: 165 166 * If $c_i \leq \frac{\texttt{cnt}_i}{k}$, then we can place $\frac{\texttt{cnt}_i}{k} - c_i$ occurrences inside multiset $1$. We can place the other elements such that there are exactly $\frac{\texttt{cnt}_i}{k}$ occurrences in all other multisets as well. 167 * Otherwise, if $c_i \gt \frac{\texttt{cnt}_i}{k}$. We can never make the other multisets have $\frac{\texttt{cnt}_i}{k}$ occurrences because we don't have enough occurrences to do so. 168 169 Therefore, the problem simplifies to: Count the number of subarrays such that $c_i \leq \frac{\texttt{cnt}_i}{k}$ over all $i$. We can do so using two-pointers. 170 171 Say our left pointer $l$ is fixed. Until the inequality is satisfied, we will keep increasing the right pointer $r$. Then, we will add $r - l$ to the answer since all subarrays $a[l, l], a[l, l+1], \ldots, a[l, r - 1]$ are satisfied. Then, increment the left pointer by $1$ and repeat. 172 173 **Code (C++) (kwant)** 174 175 ``` 176 #include <bits/stdc++.h> 177 using namespace std; 178 #define int long long 179 180 void solve() { 181 int n, k; 182 cin >> n >> k; 183 vector<int> a(n), cnt(n + 1), ct(n + 1); 184 for (int i = 0; i < n; i++) { 185 cin >> a[i]; 186 cnt[a[i]]++; 187 } 188 for (int i = 0; i <= n; i++) { 189 if (cnt[i] % k) { 190 return void(cout << 0 << endl); 191 } else { 192 cnt[i] /= k; 193 } 194 } 195 int res = 0; 196 for (int l = 0, r = 0; r >= l and r < n; r++) { 197 ct[a[r]]++; 198 while (ct[a[r]] > cnt[a[r]]) { 199 ct[a[l]]--; 200 l++; 201 } 202 res += (r - l + 1); 203 } 204 cout << res << endl; 205 } 206 207 int32_t main() { 208 cin.tie(0)->sync_with_stdio(0); 209 int tc = 1; 210 cin >> tc; 211 while (tc--) solve(); 212 } 213 ``` 214 215 #### [2148F - Гравити Фолз](/contest/2148/problem/F "Codeforces Round 1050 (Div. 4)") 216 217 **Solution (written by cry)** 218 219 Firstly, note the last row must have a length of $\texttt{max_k}$, the maximum $k$ among all arrays. Next, we can think about stacking as appending a suffix of the array on top to the array on the bottom. For example, if we stack an array $p$ of length $y$ on top of an array $q$ of length $x$ where $y \gt x$, then we append the suffix of $p$ that starts at index $x + 1$ to $q$ after gravity takes place. 220 221 Let $b_1, b_2, \ldots, b_i$ denote the lexicographically minimum possible bottom row if we have a prefix of length $i$ already fixed. From what array (out of the $n$ given arrays) should we append next to $b$? 222 223 The answer is: among all arrays with length greater than $i$, we want to append the array with the lexicographically minimum suffix starting at index $i+1$. We must append the entire suffix of that array to $b$. 224 225 We will repeat this process until $b$ has $\texttt{max_k}$ elements. Now, we just need to find the array to append at each step efficiently. 226 227 **Approach 1: $\mathcal{O}(\sum k \log n)$** 228 229 Iterate $i$, denoting the current length of prefix, backwards from $\texttt{max_k}$. We will keep track of the indices of all arrays that have length at least $i$. At each $i$, sort the array with the indices using a comparator with the following priority, from high to low: 230 231 * the element at index $i$. 232 * The "rank" of the suffix starting at index $i+1$ (i.e. its relative order in the previous sorting). If the rank doesn't exist (i.e. the array is exactly length $i$), then we can denote the rank as $-1$ as shorter arrays are more optimal when suffix are tied. 233 234 After the sorting, update the "rank" of each array with the current relative ordering. The first element in the sorted array will be the array you choose to append, if you ever end up with a fixed prefix of $i$ when you build $b$. 235 236 Now that we have the "next array to append" precalculated for every length, we build $b$ from left to right. Since we are sorting at most $\sum k$ elements and at most $n$ array indices can be tracked, the complexity is $\mathcal{O}(\sum k \log n)$ 237 238 **Approach 2: $\mathcal{O}(\sum k \sqrt{\sum k})$** 239 240 Every time we want to append the suffix starting at index $i$ of some array, let's say array $c$, then $c$ must have at least $i$ elements. Additionally, the sum of lengths of all arrays (i.e. $\sum k$) is bounded by $2 \cdot 10^5$. 241 242 The essential observation is: There exist at most $\sqrt{\sum k}$ distinct values of $k$ among the $n$ arrays. This also means that we are appending a non-empty suffix of some array at most $\sqrt{\sum k}$ times. 243 244 You can think of this as: if we have multiple arrays with the same length, then we only care to append the lexicographically minimum out of those arrays. Besides the array we will append, we don't care about any other arrays with that length. 245 246 Now, at each iteration of $i$, it suffices to manually iterate through all the suffixes of all $n$ arrays with lengths at least $i+ 1$ to find the lexicographically minimum one. You are iterating through at most $\sum k$ elements per step, so the complexity is 247 $\mathcal{O}(\sum k \sqrt{\sum k})$. 248 249 **Code 1 (C++) (cry)** 250 251 ``` 252 #include <bits/stdc++.h> 253 using namespace std; 254 255 #define all(x) x.begin(), x.end() 256 #define pb push_back 257 #define FOR(i,a,b) for(int i = (a); i < (b); ++i) 258 #define ROF(i,a,b) for(int i = (a); i >= (b); --i) 259 #define trav(a,x) for(auto& a: x) 260 #define sz(x) (int)x.size() 261 template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;} 262 template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;}; 263 264 void solve() { 265 int n; cin >> n; 266 vector<vector<int>> g(n), relevant; 267 int max_k = 0; 268 FOR(i,0,n){ 269 int k; cin >> k; 270 g[i].resize(k); 271 ckmax(max_k, k); 272 FOR(j,0,k){ 273 cin >> g[i][j]; 274 if(sz(relevant) == j) relevant.pb({}); 275 relevant[j].pb(i); 276 } 277 } 278 vector<int> lex_min(max_k), rank(n, -1); 279 ROF(i,max_k-1,0){ 280 vector<array<int, 3>> cur; 281 trav(j, relevant[i]){ 282 cur.pb({g[j][i], rank[j], j}); 283 } 284 sort(all(cur)); 285 lex_min[i] = cur[0][2]; 286 int rk = 0; 287 trav(j, cur) rank[j[2]] = rk++; 288 } 289 vector<int> ans; 290 while(sz(ans) < max_k){ 291 int tmp = sz(ans); 292 auto& v = g[lex_min[tmp]]; 293 FOR(i,tmp,sz(v)) ans.pb(v[i]); 294 } 295 assert(sz(ans) == max_k); 296 cout << ans << "\n"; 297 } 298 299 signed main() { 300 cin.tie(0) -> sync_with_stdio(0); 301 int t = 1; 302 cin >> t; 303 for(int test = 1; test <= t; test++){ 304 solve(); 305 } 306 } 307 308 /* /\_/\ 309 * (= ._.) 310 * / > \> 311 */ 312 ``` 313 314 **Code 2 (Python) (Vladosiya)** 315 316 ``` 317 from collections import deque 318 319 def solve(): 320 n = int(input()) 321 a = [deque(list(map(int, input().split()))[1:]) for i in range(n)] 322 a.sort(key=lambda x: -len(x)) 323 ans = [] 324 while a: 325 cur = min(a) 326 ans += cur 327 while a and len(a[-1]) <= len(cur): 328 a.pop() 329 for i in range(len(a)): 330 for j in range(len(cur)): 331 a[i].popleft() 332 print(*ans) 333 334 for _ in range(int(input())): 335 solve() 336 ``` 337 338 #### [2148G - Последнее желание фермера Джона](/contest/2148/problem/G "Codeforces Round 1050 (Div. 4)") 339 340 **Solution (written by avighankc)** 341 342 Let's start by understanding how $f(a)$ works. The definition essentially asks for the largest index $k$ such that the $\gcd$ of the first $k$ elements is strictly greater than the $\gcd$ of the first $k+1$. In other words, we're looking for the *last* point at which the running gcd 'drops'. 343 344 A useful observation is that scaling the entire array (multiplying or dividing every element by the same integer) does not affect where this drop occurs; each $\gcd$ value is just scaled accordingly. This allows us to 'normalize' the problem: divide each $a_i$ by the $\gcd$ of the whole array. After this, the $\gcd$ of the full array becomes $1$, and the question reduces to: 345 346 > What is the last index where the prefix GCD is still greater than $1$? 347 348 Now, note that $\gcd \gt 1$ for a prefix means there exists some integer $d \gt 1$ that divides every element in that prefix. So, the problem boils down to constructing the largest prefix that shares a common divisor greater than $1$. 349 350 To handle this, let’s think in terms of divisors. For each number $a_i$, compute all of its divisors. Maintain a frequency array $\text{div}$, where $\text{div}[d]$ stores how many elements seen so far are divisible by $d$. The maximum value of $\text{div}[d]$ tells us the largest prefix size where all elements share divisor $d$. That gives us $f(a)$. 351 352 --- 353 354 ## Extending to Prefixes 355 356 The problem, however, doesn’t just ask for $f(a)$ of the entire array. We need $g(p)$ for every prefix $p = [a_1, a_2, \dots, a_i]$, considering all permutations. Fortunately, the divisor-counting approach extends naturally: as we iterate through the array from left to right, we update the divisor frequencies for each new element and recompute the maximum. 357 358 There is a subtle edge case here. Suppose the array is $[8,4,2,1]$ and we are at prefix $[8, 4, 2]$. All three numbers are divisible by 2, so $\max(\text{div}) = 3$. But the true answer is not 3, it’s 2, because the gcd only drops *before* the last element (the full prefix always ends with $\gcd = 1$ by normalization). To handle this, we should ignore the trivial case where every element of the prefix shares a divisor. In other words, the correct answer is 359 360 $\max\{\text{div}[d], \text{div}[d] \neq i+1\}$ 361 362 ensuring we don’t mistakenly include the full prefix. 363 364 --- 365 366 ### Complexity 367 368 For each element, computing divisors takes $O(\sqrt{a_i})$. Updating frequencies and maintaining the maximum is $O(1)$ per divisor. Across all elements, the time complexity is: 369 370 $ 371 372 O\!\left( \sum_{i=1}^n \sqrt{a_i} \right) \leq O(n \sqrt{A}), 373 374 $ 375 376 where $A$ is the maximum element. This is efficient enough given the constraints. 377 378 **Solution 2 (written by Jteh)** 379 380 For every prefix of length $i$ ($1 \leq i \leq n$), the most optimal reordering is to reorder all prefix elements such that the $k$ first elements of $a$ can all be divided by the same divisor while the $(k+1)$'th element can't. This ensures that $gcd(a_1,...,a_k) \gt gcd(a_1,...,a_{k+1})$ is always true. 381 382 Thus, we have reduced the problem to : **Find a divisor that can divide the most elements for every prefix of length $i$.** To solve this, we can simply precompute divisors of all numbers and increase their count by $1$ as we iterate through the array and take the maximum $count[x]$ as answer. 383 384 A special case where maximum $count[x] = i$ is invalid, as $gcd(a_1, ..., a_k) \gt gcd(a_1, ..., a_{k+1})$ is no longer true. We can save all such $x$ into an array and check for every $i$ if $count[x] \lt i$ is true with bruteforce, since the number of divisors for a number $x$ is roughly at most $\sqrt[3]{x}$. 385 386 The final complexity will be $O(N \log N + N \sqrt[3]{N})$. 387 388 **Code (C++) (Jteh)** 389 390 ``` 391 #include<bits/stdc++.h> 392 393 #define pb push_back 394 using namespace std; 395 396 const int mxN = 2e5 + 2; 397 398 vector<int> divs[mxN]; 399 400 void pre(){ 401 for(int i = 2; i<mxN; i++){ 402 for(int j = i; j<mxN; j+=i)divs[j].pb(i); 403 } 404 } 405 406 void solve(){ 407 int n; 408 cin>>n; 409 vector<int> a(n+1), cnt(n+1, 0), max_nums; 410 vector<bool> vis(n+1, 0); 411 for(int i = 1; i<=n; i++)cin>>a[i]; 412 413 int ans = 0; 414 for(int i = 1; i<=n; i++){ 415 int x = a[i]; 416 vector<int> next; 417 for(auto &num : divs[x]){ 418 cnt[num]++; 419 if(cnt[num] != i)ans = max(ans, cnt[num]); 420 else if(!vis[num]){ 421 next.pb(num); 422 vis[num] = 1; 423 } 424 } 425 426 for(auto &num : max_nums){ 427 if(cnt[num] != i){ 428 ans = max(ans, cnt[num]); 429 vis[num] = 0; 430 } else next.pb(num); 431 } 432 max_nums = next; 433 cout<<ans<<" \n"[i == n]; 434 } 435 } 436 437 int main(){ 438 ios_base::sync_with_stdio(0); 439 cin.tie(nullptr); 440 441 #ifndef ONLINE_JUDGE 442 freopen("input.txt", "r", stdin); 443 freopen("output.txt", "w", stdout); 444 #endif 445 int t = 1; 446 cin>>t; 447 pre(); 448 while(t--)solve(); 449 return 0; 450 } 451 ```