codeforces-scrape

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

2158.md (15611B)


      1 Source: https://codeforces.com/blog/entry/148782
      2 
      3 [2158A - Suspension](/contest/2158/problem/A "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi")
      4 
      5 **Hint 1**
      6 
      7 Each red card immediately suspends a player. What is the best way to use $r$ red cards to maximize the number of distinct suspended players?
      8 
      9 **Hint 2**
     10 
     11 A player is suspended after receiving 2 yellow cards. With $y$ yellow cards, what is the maximum number of players you can suspend using only yellows?
     12 
     13 **Hint 3**
     14 
     15 If you add the maximum suspensions from red cards and yellow cards, can this total ever exceed $n$? What should happen with extra cards in that case?
     16 
     17 **Tutorial**
     18 
     19 Tutorial is loading...
     20 
     21 **Solution**
     22 
     23 ```
     24 #include<bits/stdc++.h>
     25 using namespace std;
     26 
     27 void solve(){
     28     int n,y,r;
     29     cin >> n;
     30     cin >> y >> r;
     31     cout << min(n,r+y/2) << "\n";
     32 }
     33 
     34 int main(){
     35     ios_base::sync_with_stdio(0);
     36     cin.tie(0);
     37     cout.tie(0);
     38     int t;
     39     cin >> t;
     40     while(t--){
     41         solve();
     42     }
     43 }
     44 ```
     45 
     46 **Bonus**
     47 
     48 How do you calculate the **minimum** number of players suspended from the game possible?
     49 
     50 [2158B - Split](/contest/2158/problem/B "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi")
     51 
     52 **Hint 1**
     53 
     54 Does the contribution of an element depend on its exact split $(u, v)$, or only on whether $u$ and $v$ are **odd** or **even**?
     55 
     56 **Hint 2**
     57 
     58 If every distinct element contributed its maximum possible amount, what would be the upper bound of the answer?
     59 
     60 **Hint 3**
     61 
     62 Elements with frequency of the form $4k+2$ can be split as $(2k+1,\,2k+1)$, creating $0$ size imbalance. Elements with frequency of the form $4k$ can be split as $(2k-1,\,2k+1)$, creating $2$ size imbalance.
     63 
     64 **Hint 4**
     65 
     66 The number of elements with odd total frequency is always even. How can these elements help correct any size imbalance?
     67 
     68 **Hint 5**
     69 
     70 In which situation does the size imbalance become impossible to fix, making the upper bound unreachable?
     71 
     72 **Hint 6**
     73 
     74 Consider the case when the number of distinct elements with frequency of the form $4k$ is **odd**. What happens if there exists **at least one** element with odd frequency? What happens if there are **no** elements with odd frequency?
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution**
     81 
     82 ```
     83 #include<bits/stdc++.h>
     84 using namespace std;
     85 
     86 void solve(){
     87     int n;
     88     cin >> n;
     89     vector<int> a(2*n);
     90     for(int i = 0;i < 2*n;i++){
     91         cin >> a[i];
     92     }
     93 
     94     vector<int> cnt(2*n+1);
     95     for(auto &x : a)cnt[x]++;
     96 
     97     int x = 0,y = 0,z = 0;
     98     for(int i = 1;i <= 2*n;i++){
     99         if(cnt[i] == 0)continue; 
    100         if(cnt[i]&1)x++;         //odd elements
    101         else if(cnt[i]%4)y++;    //element of form 4*k + 2
    102         else z++;                //element of form 4*k 
    103     }
    104 
    105     int ans = x+2*y+2*z;
    106     if((z&1) && x == 0)ans -= 2; 
    107     cout << ans << "\n";
    108 }
    109 
    110 int main(){
    111     ios_base::sync_with_stdio(0);
    112     cin.tie(0);
    113     cout.tie(0);
    114     int t;
    115     cin >> t;
    116     while(t--){
    117         solve();
    118     }
    119 }
    120 ```
    121 
    122 [2158C - Annoying Game](/contest/2158/problem/C "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi")
    123 
    124 **Hint 1**
    125 
    126 If Alice makes a move and Bob immediately performs the opposite move on the same index (and vice versa), what happens to the array?
    127 
    128 **Hint 2**
    129 
    130 How does the parity of $k$ affect who makes the last move and therefore who can enforce the final uncancelled change?
    131 
    132 **Hint 3**
    133 
    134 Using the cancellation idea, can the entire game be reduced to a simpler one with exactly $k \bmod 2$ effective moves?
    135 
    136 **Hint 4**
    137 
    138 If Alice changes $a_i$, only subarrays containing $i$ can improve. What are the maximum-sum subarrays that **end at $i$** and **start at $i$**, and how can combining them give the best subarray passing through $i$?
    139 
    140 **Tutorial**
    141 
    142 Tutorial is loading...
    143 
    144 **Solution**
    145 
    146 ```
    147 #include<bits/stdc++.h>
    148 using namespace std;
    149 
    150 void solve(){
    151     int n,k;
    152     cin >> n >> k;
    153     vector<int> a(n),b(n);
    154     for(int i = 0;i < n;i++)cin >> a[i];
    155     for(int i = 0;i < n;i++)cin >> b[i];
    156     k &= 1; //It can be reduced as 0/1 move game
    157 
    158     vector<long long> L(n); //maximum sum non empty subarray ending at each position
    159     for(int i = 0;i < n;i++){
    160         L[i] = (i && L[i-1]>0 ? L[i-1] : 0ll) + a[i]; 
    161     }   
    162 
    163     vector<long long> R(n); //maximum sum non empty subarray starting at each position
    164     for(int i = n-1;i >= 0;i--){
    165         R[i] = (i+1<n && R[i+1]>0 ? R[i+1] : 0ll) + a[i];
    166     }
    167 
    168     if(k == 0){
    169         long long ans = *max_element(L.begin(),L.end());
    170         cout << ans << "\n";
    171     }
    172     else{
    173         long long ans = LONG_MIN;
    174         for(int i = 0;i < n;i++){
    175             ans = max(ans,L[i]+R[i]-a[i]+b[i]);
    176         }
    177         cout << ans << "\n";
    178     }
    179 }
    180 
    181 int main(){
    182     ios_base::sync_with_stdio(0);
    183     cin.tie(0);
    184     cout.tie(0);
    185     int t;
    186     cin >> t;
    187     while(t--){
    188         solve();
    189     }
    190 }
    191 ```
    192 
    193 **Bonus**
    194 
    195 How do you calculate the final score if goals of Alice and Bob were **swapped**?
    196 
    197 [2158D - Palindrome Flipping](/contest/2158/problem/D "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi") and [abc864197532](/profile/abc864197532 "International Grandmaster abc864197532")
    198 
    199 **Hint 1**
    200 
    201 Instead of directly transforming $s$ into $t$, is it enough to know how to transform any string into an intermediate string?
    202 
    203 **Hint 2**
    204 
    205 If you know how to turn any string into $0^n$ in at most $n$ operations, how can you use that to transform $s$ into $t$ in at most $2n$ operations?
    206 
    207 **Hint 3**
    208 
    209 If there is at least one position $p$ with $s_p = s_{p+1}$. Can you grow a block of equal bits starting from $[p, p+1]$?
    210 
    211 **Hint 4**
    212 
    213 How do you ensure such a position $p$ in strictly alternating string after exactly one operation?
    214 
    215 **Hint 5**
    216 
    217 When trying to grow the block to the right (or left), what happens if the next bit is equal to the block's boundary bit?  
    218 What if it is different? Can you use flipping a palindromic block (all equal bits) to force the boundary to match the next bit?
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution**
    225 
    226 ```
    227 #include<bits/stdc++.h>
    228 using namespace std;
    229 
    230 vector<array<int,2>> reduce(string &s){
    231     int n = s.size();
    232     vector<array<int,2>> op;
    233 
    234     int p = -1; // position p such that two consecutive characters are same
    235     for(int i = 0;i < n-1;i++){
    236         if(s[i] == s[i+1])p = i;
    237     }
    238     if(p == -1){ // string is alternating
    239         op.push_back({0,2}); // substring of first three character must be palindrome
    240         s[0] ^= 1;s[1] ^= 1;
    241         p = 2;
    242     }
    243 
    244     char value = s[p+1];
    245     int L = p,R = p+1; // We maintain [L,R] such that all position in it have the same value
    246 
    247     while(R+1 < n){
    248         if(s[R+1] != value)op.push_back({L,R});
    249         R++;value = s[R];
    250     }
    251 
    252     while(L){
    253         if(s[L-1] != value)op.push_back({L,R});
    254         L--;value = s[L];
    255     }
    256 
    257     if(value == '1')op.push_back({0,n-1}); // We want to make all zeroes
    258 
    259     return op;
    260 }
    261 
    262 void solve(){
    263     int n;
    264     cin >> n;
    265     string s,t;
    266     cin >> s >> t;
    267 
    268     auto operation_s = reduce(s); // operations to reduce s to all zeroes
    269     auto operation_t = reduce(t); // operations to reduce t to all zeroes
    270 
    271     reverse(operation_t.begin(),operation_t.end());
    272 
    273     int moves = operation_s.size() + operation_t.size();
    274     cout << moves << "\n";
    275     for(auto &[x,y] : operation_s)cout << x+1 << " " << y+1 << "\n";
    276     for(auto &[x,y] : operation_t)cout << x+1 << " " << y+1 << "\n";
    277 
    278 }
    279 
    280 int main(){
    281     ios_base::sync_with_stdio(0);
    282     cin.tie(0);
    283     cout.tie(0);
    284     int t;
    285     cin >> t;
    286     while(t--){
    287         solve();
    288     }
    289 }
    290 ```
    291 
    292 [2158E - Sink](/contest/2158/problem/E "Codeforces Round 1067 (Div. 2)") Idea & Solution: [kingmessi](/profile/kingmessi "Master kingmessi")
    293 
    294 **Hint 1**
    295 
    296 How would you solve the problem if every value in the grid was distinct?
    297 
    298 **Hint 2**
    299 
    300 When some cells have the same value, is it natural to treat a connected component of equal valued cells as a single group?  
    301 For such a group, how can you decide whether this entire group **needs** a hole?
    302 
    303 **Hint 3**
    304 
    305 After a single query (decreasing the value of one cell), can the beauty increase by more than 1?  
    306 How many groups from previous grid can stop needing a hole because they now have a strictly smaller neighbour?
    307 
    308 **Hint 4**
    309 
    310 How can you model the evolution of the grid as a graph, where edges reflect either adjacency in the grid or "time adjacency" between different versions of the same cell?
    311 
    312 **Hint 5**
    313 
    314 If a cell receives $k$ decreasing updates over all queries, can you model it as a chain of $k+1$ nodes (one per value over time)?  
    315 How does connecting each new node to the latest versions of its neighbours help you maintain connected components of equal values efficiently?
    316 
    317 **Tutorial**
    318 
    319 Tutorial is loading...
    320 
    321 **Solution**
    322 
    323 ```
    324 #include<bits/stdc++.h>
    325 using namespace std;
    326  
    327 const int N = 400005;
    328 int parent[N],siz[N],important[N],val[N];
    329  
    330 void make_set(int v,int x) {
    331     parent[v] = v;siz[v] = 1;important[v] = 1;val[v] = x;
    332 }
    333  
    334 int find_set(int v) {
    335     if (v == parent[v])return v;
    336     return parent[v] = find_set(parent[v]);
    337 }
    338  
    339 void union_sets(int a, int b) {
    340     a = find_set(a);
    341     b = find_set(b);
    342     if (a != b) {
    343         if (siz[a] < siz[b])swap(a, b);
    344         parent[b] = a;
    345         siz[a] += siz[b];
    346         important[a] = min(important[a],important[b]);
    347     }
    348 }
    349  
    350 int n,m;
    351  
    352 vector<array<int,2>> neighbours(int r,int c){
    353     vector<array<int,2>> v;
    354     if(r)v.push_back({r-1,c});
    355     if(r+1 < n)v.push_back({r+1,c});
    356     if(c)v.push_back({r,c-1});
    357     if(c+1 < m)v.push_back({r,c+1});
    358     return v;
    359 }
    360  
    361 void solve()
    362 {
    363     cin >> n >> m;
    364     vector<vector<int>> a(n,vector<int>(m));  // latest value of a given cell
    365     vector<vector<int>> ls(n,vector<int>(m)); // latest node created for a given cell
    366     for(int i = 0;i < n;i++){
    367         for(int j = 0;j < m;j++){
    368             cin >> a[i][j];
    369             ls[i][j] = m*i+j;
    370         }
    371     }
    372  
    373     for(int i = 0;i < n;i++){
    374         for(int j = 0;j < m;j++){
    375             make_set(m*i+j,a[i][j]);
    376             for(auto &[p,q] : neighbours(i,j)){
    377                 if(a[p][q] < a[i][j])important[m*i+j] = 0;
    378             }      
    379         }
    380     }
    381  
    382     for(int i = 0;i < n;i++){
    383         for(int j = 0;j < m;j++){
    384             for(auto &[p,q] : neighbours(i,j)){
    385                 if(a[p][q] == a[i][j])union_sets(m*i+j,m*p+q);
    386             }
    387         }
    388     }
    389  
    390     int ans = 0;
    391     for(int i = 0;i < n;i++){
    392         for(int j = 0;j < m;j++){
    393             if(parent[m*i+j] == m*i+j)ans+=important[m*i+j];
    394         }
    395     }
    396     
    397     cout << ans << "\n";
    398  
    399     int q;
    400     cin >> q;
    401     int nd = n*m;
    402  
    403     for(int i = 0;i < q;i++){
    404         int r,c,x;
    405         cin >> r >> c >> x;
    406         r--;c--;
    407         x = a[r][c] - x;
    408         set<int> s;
    409  
    410         int mn = INT_MAX;
    411         for(auto &[p,q] : neighbours(r,c)){
    412             s.insert(find_set(ls[p][q]));
    413             mn = min(mn,a[p][q]);
    414         }
    415         s.insert(find_set(ls[r][c]));
    416  
    417         for(auto &y : s){
    418             ans -= important[y];
    419         }
    420  
    421         for(auto &y : s){
    422             if(val[y] > x)important[y] = 0;
    423         }
    424  
    425         make_set(nd,x);
    426         if(mn < x)important[nd] = 0;
    427         else important[nd] = 1;
    428  
    429  
    430         for(auto &y : s){
    431             if(val[y] == x){
    432                 union_sets(y,nd);
    433             }
    434         }
    435  
    436         a[r][c] = x;
    437         ls[r][c] = nd++;
    438  
    439         s.clear();
    440         for(auto &[p,q] : neighbours(r,c)){
    441             s.insert(find_set(ls[p][q]));
    442         }
    443         s.insert(find_set(ls[r][c]));
    444  
    445         for(auto &y : s){
    446             ans += important[y];
    447         }
    448  
    449         cout << ans << "\n";
    450     }
    451  
    452 }
    453  
    454 signed main(){
    455     ios_base::sync_with_stdio(0);
    456     cin.tie(0);
    457     cout.tie(0);
    458     int t;
    459     cin >> t;
    460     while(t--)
    461         solve();
    462     return 0;
    463 }
    464 ```
    465 
    466 [2158F2 - Distinct GCDs (Hard Version)](/contest/2158/problem/F2 "Codeforces Round 1067 (Div. 2)") Idea & Solution: [koderkushy](/profile/koderkushy "Candidate Master koderkushy")
    467 
    468 **Tutorial**
    469 
    470 Tutorial is loading...
    471 
    472 **Solution (Python)**
    473 
    474 ```
    475 from copy import deepcopy
    476 
    477 def get_nums(k: int=10):
    478     nums = [
    479         2**(i + j) * 3**i * 5**j * 7**(k-1-i) * 11**(k-1-j)
    480         for i in range(k) for j in range(k)
    481     ]
    482 
    483     return nums
    484 
    485 def eulerian_paths(max_k: int = 100):
    486     paths = [[], [0, 0], [1,1,0,0]]
    487 
    488     for k in range(3, max_k + 1):
    489         path = deepcopy(paths[k - 2])
    490         x, y = k-2, k-1
    491 
    492         if k % 2:
    493             path.extend([x, x, y, y])
    494             for j in range(1, x, 2):
    495                 path.extend([j, x, j+1, y])
    496             path.append(0)
    497         else:
    498             path.extend([x, x, 1, y, y])
    499             for j in range(2, x, 2):
    500                 path.extend([j, x, j+1, y])
    501             path.append(0)
    502 
    503         paths.append(path)
    504 
    505     return paths
    506 
    507 def path_len(k: int):
    508     return 1 + (k*k+k)//2 - (0 if k%2 else k//2-1)
    509 
    510 if __name__ == "__main__":
    511     nums = get_nums(10)
    512     paths = eulerian_paths(100)
    513 
    514     for i in range(1, 101):
    515         assert len(paths[i]) == path_len(i)
    516 
    517     t = int(input())
    518 
    519     for _ in range(t):
    520         n = int(input())
    521 
    522         l, r = 0, 100
    523         while l < r-1:
    524             m = r - (r-l)//2
    525             if path_len(m) < n:
    526                 l = m
    527             else:
    528                 r = m
    529 
    530         path = paths[r]
    531         assert len(path) >= n
    532 
    533         a = [nums[i] for i in path[: n]]
    534         print(*a)
    535 ```
    536 
    537 **Solution (C++)**
    538 
    539 ```
    540 #include "bits/stdc++.h"
    541 using namespace std;
    542 
    543 constexpr int64_t poww (int64_t a, int64_t p) {
    544     assert(p >= 0);
    545     int64_t res = 1;
    546     while (p > 0) {
    547         if (p & 1) res *= a;
    548         a *= a, p >>= 1;
    549     }
    550     return res;
    551 }
    552 
    553 constexpr int32_t path_len(const int32_t n) {
    554 	return 1 + (n*n + n) / 2 - (n % 2 ? 0: n/2 - 1);
    555 }
    556 
    557 vector nums(0, 0ll);
    558 vector walks(0, vector(0, 0));
    559 
    560 void load_nums(const size_t p=10) {
    561 	nums.resize(p * p);
    562 
    563 	for (int i = 0; i < p; ++i)
    564 		for (int j = 0; j < p; ++j)
    565 			nums[i * 10 + j] = poww(2,(i+j)) * poww(3,i) * poww(5,j) * poww(7,(9-i)) * poww(11,(9-j));
    566 }
    567 
    568 void load_walks(const size_t max_k=100) {
    569 	walks.resize(max_k + 1);
    570 	walks[1] = vector({0, 0});
    571 	walks[2] = vector({1, 1, 0, 0});
    572 
    573 	for (int k = 3; k <= max_k; k++) {
    574 		auto& walk = walks[k];
    575 		walk = walks[k - 2];
    576 		const int x = k-2, y = k-1;
    577 
    578 		if (k % 2) {
    579 			walk.push_back(x);
    580 			walk.push_back(x);
    581 			walk.push_back(y);
    582 			walk.push_back(y);
    583 			for (int j = 1; j < x; j += 2)
    584 				walk.push_back(j),
    585 				walk.push_back(x),
    586 				walk.push_back(j+1),
    587 				walk.push_back(y);
    588 			walk.push_back(0);
    589 		} else {
    590 			walk.push_back(x);
    591 			walk.push_back(x);
    592 			walk.push_back(1);
    593 			walk.push_back(y);
    594 			walk.push_back(y);
    595 			for (int j = 2; j < x; j += 2)
    596 				walk.push_back(j),
    597 				walk.push_back(x),
    598 				walk.push_back(j+1),
    599 				walk.push_back(y);
    600 			walk.push_back(0);
    601 		}
    602 	}
    603 }
    604 
    605 void solve (const int kase) {
    606 
    607     int n; cin >> n;
    608 
    609     int l = 0, r = 100;
    610     while (l < r - 1) {
    611     	int m = r - (r-l) / 2;
    612     	if (path_len(m) < n)
    613     		l = m;
    614     	else
    615     		r = m;
    616     }
    617 
    618     vector a(n, 0ll);
    619     for (size_t i = 0; i < n; ++i) {
    620     	a[i] = nums[walks[r][i]];
    621     	cout << a[i] << ' ' ;
    622     }
    623 
    624     vector gcds(n-1, 0ll);
    625     for (size_t i = 1; i < n; ++i) {
    626     	gcds[i-1] = gcd(a[i], a[i - 1]);
    627     }
    628 
    629     assert(set(gcds.begin(), gcds.end()).size() == n-1);
    630 
    631     cout << '\n';
    632 }
    633 
    634 int main () {
    635     ios_base::sync_with_stdio(0), cin.tie(0);
    636 
    637     load_nums();
    638     load_walks();
    639 
    640     for (size_t i = 1 ; i < 101; ++i)
    641     	assert(walks[i].size() == path_len(i));
    642 
    643     int t; cin >> t, assert(t >= 0);
    644     for (int i = 0; t--; )
    645         solve(++i);
    646 
    647 }
    648 ```