codeforces-scrape

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

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 ```