codeforces-scrape

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

1659.md (15947B)


      1 Source: https://codeforces.com/blog/entry/100938
      2 
      3 Thank you everyone for your participation. Do vote under the Feedback section, and feel free to give your review of the problems in the comments.
      4 
      5 ---
      6 
      7 [1659A - Red Versus Blue](/contest/1659/problem/A "Codeforces Round 782 (Div. 2)")
      8 
      9 Idea: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101")   
     10  Editorial: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101")
     11 
     12 **Hints**
     13 
     14 **Hint 1**
     15 
     16 Is it a good idea to have consecutive `B`'s?
     17 
     18 **Hint 2**
     19 
     20 If you space out all the `B`'s, how many regions do you have to place the `R`'s into?
     21 
     22 **Hint 3**
     23 
     24 What is the best way of placing the `R`'s into $b+1$ regions such that the maximum number of `R`'s in a region is minimum?
     25 
     26 **Solution**
     27 
     28 Tutorial is loading...
     29 
     30 **Implementation (C++)**
     31 
     32 ```
     33 #include<bits/stdc++.h>
     34 using namespace std;
     35 using lol=long long int;
     36 #define endl "\n"
     37  
     38 int main()
     39 {
     40 ios_base::sync_with_stdio(false);
     41 cin.tie(NULL);
     42 int _=1;
     43 cin>>_;
     44 while(_--)
     45 {
     46     int n,r,b;
     47     cin>>n>>r>>b;
     48     int p=r/(b+1),q=r%(b+1);
     49     for(int i=0;i<q;i++)    cout<<string(p+1,'R')<<'B';
     50     for(int i=q;i<b;i++)    cout<<string(p,'R')<<'B';
     51     cout<<string(p,'R');
     52     cout<<endl;
     53 }
     54 return 0;
     55 }
     56 ```
     57 
     58 **Implementation (Python)**
     59 
     60 ```
     61 t = int(input())
     62 for i in range(t):
     63     n, r, b = map(int, input().split())
     64     p = r % (b + 1)
     65     y = ""
     66     for j in range(int(r / (b + 1))):
     67         y = y + "R"
     68     ans = ""
     69     for i in range(b + 1):
     70         if i > 0:
     71             ans = ans + "B"
     72         ans = ans + y
     73         if p > 0:
     74             ans = ans + "R"
     75             p = p - 1
     76     print(ans)
     77 ```
     78 
     79 **Feedback**
     80 
     81 * Good problem:
     82 * Average problem:
     83 * Bad problem:
     84 * Did not solve:
     85 
     86 [1659B - Bit Flipping](/contest/1659/problem/B "Codeforces Round 782 (Div. 2)")
     87 
     88 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66")   
     89  Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66")
     90 
     91 **Hints**
     92 
     93 **Hint 1**
     94 
     95 Let's say you don't ever pick a bit. How many times will it get flipped?
     96 
     97 **Hint 2**
     98 
     99 If you do pick a bit once at some point, it will get flipped $1$ less time overall.
    100 
    101 **Hint 3**
    102 
    103 To get the lexicographically largest string, you need to make bits $1$ starting from the left. What is the minimum number of times you have to select a bit to ensure it gets flipped, or stays the same?
    104 
    105 **Solution**
    106 
    107 Tutorial is loading...
    108 
    109 **Implementation (C++)**
    110 
    111 ```
    112 #include<bits/stdc++.h>
    113 using namespace std;
    114 using lol=long long int;
    115 #define endl "\n"
    116  
    117 int main()
    118 {
    119 ios_base::sync_with_stdio(false);
    120 cin.tie(NULL);
    121 int _=1;
    122 cin>>_;
    123 while(_--)
    124 {
    125     int n,k;
    126     cin>>n>>k;
    127     string s;
    128     cin>>s;
    129     vector<int> f(n,0);
    130     int tmpk=k;
    131     for(int i=0;i<n && tmpk>0;i++)
    132     {
    133         if(k%2==s[i]-'0')
    134         {
    135             f[i]=1;
    136             tmpk--;
    137         }
    138     }
    139     f[n-1]+=tmpk;
    140     for(int i=0;i<n;i++)
    141     {
    142         if((k-f[i])%2==1)   s[i]='1'-(s[i]-'0');
    143     }
    144     cout<<s<<endl;
    145     for(auto& e:f)  cout<<e<<" ";
    146     cout<<endl;
    147 }
    148 return 0;
    149 }
    150 ```
    151 
    152 **Implementation (Python)**
    153 
    154 ```
    155 t = int(input())
    156 for i in range(t):
    157     n, k = map(int, input().split())
    158     kc = k
    159     s = input()
    160     f = [0] * n
    161     ans = ""
    162     for i in range(n):
    163         if k == 0:
    164             break
    165         if kc % 2 == 1 and s[i] == '1':
    166             f[i] = f[i] + 1
    167             k = k - 1
    168         elif kc % 2 == 0 and s[i] == '0':
    169             f[i] = f[i] + 1
    170             k = k - 1
    171     f[n - 1] = f[n - 1] + k
    172     for i in range(n):
    173         flip = kc - f[i]
    174         if flip % 2 == 0:
    175             ans = ans + s[i]
    176         else:
    177             if s[i] == '1':
    178                 ans = ans + '0'
    179             else:
    180                 ans = ans + '1'
    181     print(ans)
    182     for i in range(n):
    183         print(f[i], end = ' ')
    184     print()
    185 ```
    186 
    187 **Feedback**
    188 
    189 * Good problem:
    190 * Average problem:
    191 * Bad problem:
    192 * Did not solve:
    193 
    194 [1659C - Line Empire](/contest/1659/problem/C "Codeforces Round 782 (Div. 2)")
    195 
    196 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66")   
    197  Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66")
    198 
    199 **Hints**
    200 
    201 **Hint 1**
    202 
    203 Try to analyze the cost of each operation separately. Is there some linearity you can exploit?
    204 
    205 **Hint 2**
    206 
    207 Try to make greedy decisions. Can we say that it is always better to move right whenever possible?
    208 
    209 **Hint 3**
    210 
    211 Let's say you fix the final position of your capital. Now think about Hint 2.
    212 
    213 **Solution**
    214 
    215 Tutorial is loading...
    216 
    217 **Implementation (C++)**
    218 
    219 ```
    220 #include<bits/stdc++.h>
    221 using namespace std;
    222 using lol=long long int;
    223 #define endl "\n"
    224 const lol inf=1e18+8;
    225  
    226 int main()
    227 {
    228 ios_base::sync_with_stdio(false);
    229 cin.tie(NULL);
    230 int _=1;
    231 cin>>_;
    232 while(_--)
    233 {
    234     int n;
    235     lol a,b;
    236     cin>>n>>a>>b;
    237     vector<lol> x(n+1),p(n+1);
    238     x[0]=0;
    239     for(int i=1;i<=n;i++)   cin>>x[i];
    240     partial_sum(x.begin(),x.end(),p.begin());
    241     lol ans=inf;
    242     for(int i=0;i<=n;i++)
    243     {
    244         ans=min(ans,(a+b)*(x[i]-x[0])+b*(p[n]-p[i]-(n-i)*x[i]));
    245     }
    246     cout<<ans<<endl;
    247 }
    248 return 0;
    249 }
    250 ```
    251 
    252 **Feedback**
    253 
    254 * Good problem:
    255 * Average problem:
    256 * Bad problem:
    257 * Did not solve:
    258 
    259 [1659D - Reverse Sort Sum](/contest/1659/problem/D "Codeforces Round 782 (Div. 2)")
    260 
    261 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66")   
    262  Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66")
    263 
    264 **Hints**
    265 
    266 **Hint 1**
    267 
    268 Is there any way to tell how many $1$s were in $A$?
    269 
    270 **Hint 2**
    271 
    272 Can you tell what $a_n$ was by looking at just $c_n$?
    273 
    274 **Hint 3**
    275 
    276 Try to simulate removing each $B_i$ starting from $B_n$.
    277 
    278 **Solution**
    279 
    280 Tutorial is loading...
    281 
    282 **Implementation (C++)**
    283 
    284 ```
    285 #include<bits/stdc++.h>
    286 using namespace std;
    287 using lol=long long int;
    288 #define endl "\n"
    289  
    290 int main()
    291 {
    292 ios_base::sync_with_stdio(false);
    293 cin.tie(NULL);
    294 int _=1;
    295 cin>>_;
    296 while(_--)
    297 {
    298     int n;
    299     cin>>n;
    300     vector<lol> v(n);
    301     for(auto& e:v)  cin>>e;
    302     int k=accumulate(v.begin(),v.end(),0ll)/n;
    303     vector<int> b(n),ans(n,0);
    304     int lf=n-k;
    305     for(int i=lf;i<n;i++)   b[i]=n-1;
    306     for(int i=n-1;i>=0 && lf<=i;i--)
    307     {
    308         int cur=v[i]-(b[i]-i);
    309         if(cur==i+1)    ans[i]=1;
    310         else if(cur==1)
    311         {
    312             ans[i]=0;
    313             lf--;
    314             b[lf]=i-1;
    315         }
    316     }
    317     for(auto& e:ans)    cout<<e<<" ";
    318     cout<<endl;
    319 }
    320 return 0;
    321 }
    322 ```
    323 
    324 **Feedback**
    325 
    326 * Good problem:
    327 * Average problem:
    328 * Bad problem:
    329 * Did not solve:
    330 
    331 **Challenge**
    332 
    333 Try to solve this problem if it is possible for invalid $C$ to be given as input. This was the original version of the problem, but testers struggled a lot with it. The solution to this is still used in the validator.
    334 
    335 [1659E - AND-MEX Walk](/contest/1659/problem/E "Codeforces Round 782 (Div. 2)")
    336 
    337 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66")   
    338  Editorial: [TimeWarp101](/profile/TimeWarp101 "Expert TimeWarp101")
    339 
    340 **Hints**
    341 
    342 **Hint 1**
    343 
    344 Can the MEX ever be $ \gt 2$?
    345 
    346 **Hint 2**
    347 
    348 For the MEX to be $0$, the AND of the walk should be $ \gt 0$. This implies that some bit is on for all the edges of the walk. How can you check this efficiently?
    349 
    350 **Hint 3**
    351 
    352 Make $30$ graphs, with each graph only containing edges where the $i$-th bit is on. You can use disjoint sets on these graphs to solve the above problem.
    353 
    354 **Hint 4**
    355 
    356 When MEX is $1$, we know $0$ exists in the sequence. We need to avoid $1$ and jump from some other number to $0$. We need to get rid of the $0$-th bit while some other bit stays on to ensure we don't get $1$ in our sequence. This basically means that we need to walk to a node which has an even edge and ensure our AND so far is $ \gt 1$. Travelling through the even edge would guarantee that our answer is $1$.
    357 
    358 **Hint 5**
    359 
    360 Again, make $29$ graphs, with each graph only containing edges where the $0$-th and $i$-th ($i\geq 1$) bits are on. Use disjoint sets on these graphs. For each vertex you can note if it is adjacent to an even edge and then store this information in the disjoint set data structure.
    361 
    362 **Solution**
    363 
    364 Tutorial is loading...
    365 
    366 **Implementation (C++)**
    367 
    368 ```
    369 #pragma GCC optimize("Ofast")
    370 #pragma GCC optimize("unroll-loops")
    371 #pragma GCC target("avx,avx2,fma")
    372  
    373 #include <bits/stdc++.h>
    374 #include <ext/pb_ds/assoc_container.hpp>
    375 #include <ext/pb_ds/trie_policy.hpp>
    376 #include <ext/rope>
    377  
    378 using namespace std;
    379 using namespace __gnu_pbds;
    380 using namespace __gnu_cxx;
    381  
    382 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
    383  
    384 #define fi first
    385 #define se second
    386 #define pb push_back
    387 #define eb emplace_back
    388 #define mp make_pair
    389 #define gcd __gcd
    390 #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
    391 #define rep(i, n) for (int i=0; i<(n); i++)
    392 #define rep1(i, n) for (int i=1; i<=(n); i++)
    393 #define all(x) (x).begin(), (x).end()
    394 #define rall(x) (x).rbegin(), (x).rend()
    395 #define endl "\n"
    396  
    397 typedef long long ll;
    398 typedef unsigned long long ull;
    399 typedef unsigned uint;
    400 typedef long double ld;
    401 typedef pair<int, int> pii;
    402 typedef pair<ll, ll> pll;
    403 typedef vector<int> vi;
    404 typedef vector<vector<int>> vvi;
    405 typedef vector<ll> vll;
    406 typedef vector<vector<ll>> vvll;
    407 typedef vector<bool> vb;
    408 typedef vector<vector<bool>> vvb;
    409 template<typename T, typename cmp = less<T>>
    410 using ordered_set=tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
    411 typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
    412  
    413 struct dsu {
    414     vi d;
    415     dsu(int n) : d(n, -1) {}
    416     int find(int x) {return d[x] < 0 ? x : d[x] = find(d[x]);}
    417     void join(int x, int y) {
    418         x = find(x), y = find(y);
    419         if(x == y) return;
    420         if(d[x] > d[y]) swap(x, y);
    421         d[x] += d[y]; d[y] = x;
    422     }
    423     bool is_joined(int x, int y) {
    424         return find(x) == find(y);
    425     }
    426 };
    427  
    428 int32_t main() {
    429     fastio;
    430     int n, m; cin >> n >> m;
    431     vector<tuple<int, int, int>> edges;
    432     rep(i, m) {
    433         int u, v, w; cin >> u >> v >> w;
    434         edges.eb(--u, --v, w);
    435     }
    436     vector<dsu> zero(30, n), one(30, n);
    437     rep(j, 30) {
    438         for(auto& [u, v, w]: edges) if(w >> j & 1) {
    439             zero[j].join(u, v);
    440         }
    441     }
    442     vb even(n);
    443     rep1(j, 29) {
    444         for(auto& [u, v, w]: edges) if((w >> j & 1)) {
    445             one[j].join(u, v);
    446         }
    447         vb vis(n);
    448         for(auto& [u, v, w]: edges) if(!(w & 1)) {
    449             vis[one[j].find(u)] = 1;
    450             vis[one[j].find(v)] = 1;
    451         }
    452         rep(i, n) if(vis[one[j].find(i)]) even[i] = 1;
    453     }
    454     auto check = [&](int u, int v) -> int {
    455         rep(j, 30) if(zero[j].is_joined(u, v)) return 0;
    456         if(even[u]) return 1;
    457         rep1(j, 29) if(one[j].is_joined(u, v)) return 1;
    458         return 2;
    459     };
    460     int q; cin >> q;
    461     while(q--) {
    462         int u, v; cin >> u >> v; --u, --v;
    463         cout << check(u, v) << endl;
    464     }
    465 }
    466 ```
    467 
    468 **Feedback**
    469 
    470 * Good problem:
    471 * Average problem:
    472 * Bad problem:
    473 * Did not solve:
    474 
    475 **Challenge**
    476 
    477 Try to solve this problem if the queries were for **longest** walk instead.
    478 
    479 [1659F - Tree and Permutation Game](/contest/1659/problem/F "Codeforces Round 782 (Div. 2)")
    480 
    481 Idea: [Newtech66](/profile/Newtech66 "Expert Newtech66")   
    482  Editorial: [Newtech66](/profile/Newtech66 "Expert Newtech66")
    483 
    484 [Bench0310](/profile/Bench0310 "Grandmaster Bench0310") has written another proof for the solution to this problem [here](https://codeforces.com/blog/entry/101560?#comment-904422) and [here](https://codeforces.com/blog/entry/101560?#comment-904443). Many thanks to him!
    485 
    486 **Hints**
    487 
    488 **Hint 1**
    489 
    490 Notice that as long as there are $\geq 3$ elements not in their correct place, Alice can always put at least $1$ element into the correct place.
    491 
    492 **Hint 2**
    493 
    494 Intuitively, Alice should win if the tree is "big enough", because Bob won't be able to reach some places quickly enough. How to define this sense of "big enough"?
    495 
    496 **Hint 3**
    497 
    498 Try to solve this problem on a line graph.
    499 
    500 **Hint 4**
    501 
    502 It is actually possible to force a sequence of moves to get the $2$ remaining elements onto the diameter of the tree. Given this, use the answer to Hint 3.
    503 
    504 **Hint 5**
    505 
    506 Prove that Alice always wins on trees with diameter $\geq 3$.
    507 
    508 **Hint 6**
    509 
    510 A tree of diameter $2$ is a star graph. This case has a number of edge cases. This time, try to look at permutation cycles. Can you define some kind of invariant?
    511 
    512 **Solution**
    513 
    514 Tutorial is loading...
    515 
    516 **Implementation (C++)**
    517 
    518 ```
    519 #include<bits/stdc++.h>
    520 using namespace std;
    521 using lol=long long int;
    522 #define endl "\n"
    523  
    524 pair<int,int> dfs(int u,const vector<vector<int>>& g,int p=-1) //returns {node with max dist,max dist}
    525 {
    526     pair<int,int> res{u,0};
    527     int mx=0;
    528     for(auto v:g[u])
    529     {
    530         if(v==p)    continue;
    531         pair<int,int> cur=dfs(v,g,u);
    532         cur.second++;
    533         if(mx<cur.second)
    534         {
    535             res=cur;
    536             mx=cur.second;
    537         }
    538     }
    539     return res;
    540 }
    541  
    542 int main()
    543 {
    544 ios_base::sync_with_stdio(false);
    545 cin.tie(NULL);
    546 int _=1;
    547 cin>>_;
    548 while(_--)
    549 {
    550     int n,x;
    551     cin>>n>>x;
    552     vector<vector<int>> g(n+1);
    553     vector<int> p(n+1),deg(n+1,0);
    554     for(int i=1;i<n;i++)
    555     {
    556         int u,v;
    557         cin>>u>>v;
    558         g[u].push_back(v);
    559         g[v].push_back(u);
    560         deg[u]++,deg[v]++;
    561     }
    562     for(int i=1;i<=n;i++)
    563     {
    564         cin>>p[i];
    565     }
    566     //find diameter of tree with 2 DFSes
    567     int diam=dfs(dfs(1,g).first,g).second;
    568     //if diam>=3, Alice always wins
    569     //if diam=1, n=2, have to check if p=[1,2]
    570     //otherwise we have a star graph and cases follow
    571     if(diam>=3) cout<<"Alice";
    572     else if(diam==1)    cout<<((p[1]==1)?"Alice":"Bob");
    573     else
    574     {
    575         //we need to check if we have already won or can win in the first move
    576         //this is possible if the permutation is already sorted
    577         //or if there are two marked elements and the chip is on neither of them
    578         vector<int> marked;
    579         for(int i=1;i<=n;i++)
    580         {
    581             if(p[i]!=i) marked.push_back(i);
    582         }
    583         if((int)marked.size()==0)
    584         {
    585             cout<<"Alice";
    586         }else if((int)marked.size()==2 && (x!=marked[0] && x!=marked[1]))
    587         {
    588             cout<<"Alice";
    589         }else
    590         {
    591             //we haven't won yet and it is not possible to win in one move
    592             //cases follow
    593             //first find center, it will have deg>1
    594             int center;
    595             for(int i=1;i<=n;i++)
    596             {
    597                 if(deg[i]>1)
    598                 {
    599                     center=i;
    600                     break;
    601                 }
    602             }
    603             //is chip on center?
    604             bool chiponcenter=(x==center);
    605             //is center marked?
    606             bool centerismarked=(find(marked.begin(),marked.end(),x)!=marked.end());
    607             //list the cycles
    608             vector<int> vis(n+1,false);
    609             vector<vector<int> > cycles;
    610             for(int i=1;i<=n;i++)
    611             {
    612                 if(vis[i])  continue;
    613                 int j=i;
    614                 cycles.push_back({j});
    615                 vis[j]=true;
    616                 while(!vis[p[j]])
    617                 {
    618                     cycles.back().push_back(p[j]);
    619                     vis[p[j]]=true;
    620                     j=p[j];
    621                 }
    622             }
    623             //min number of swaps
    624             int swapcnt=0;
    625             for(auto& cycle:cycles) swapcnt+=(int)cycle.size()-1;
    626             //parity
    627             int parity=(swapcnt+!chiponcenter)%2;
    628             //cases
    629             if(!centerismarked)    cout<<(parity?"Alice":"Bob");
    630             else if(chiponcenter && centerismarked)  cout<<"Bob";
    631             else    //chip not on center and center is marked
    632             {
    633                 //need to check if we can unmark center on first move
    634                 //it is impossible if x is on p[center] (since we need to move p[center] to get center
    635                 //to the right place, but p[center] is blocked)
    636                 bool cannotunmarkcenter=(p[center]==x);
    637                 if(cannotunmarkcenter)  cout<<"Bob";
    638                 else    cout<<(parity?"Alice":"Bob");
    639             }
    640         }
    641     }
    642     cout<<endl;
    643 }
    644 return 0;
    645 }
    646 ```
    647 
    648 **Feedback**
    649 
    650 * Good problem:
    651 * Average problem:
    652 * Bad problem:
    653 * Did not solve: