codeforces-scrape

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

2027.md (18521B)


      1 Source: https://codeforces.com/blog/entry/135558
      2 
      3 Thank you so much for participating in our round! We really hope you enjoyed it. For us, it was an amazing and educational experience, and we look forward to the possibility that we could one day help to or hold a round again. Thanks again to [abc864197532](/profile/abc864197532 "International Grandmaster abc864197532") and [Vladithur](/profile/Vladithur "International Master Vladithur") for making the process so smooth and enjoyable.
      4 
      5 [2027A - Rectangle Arrangement](/contest/2027/problem/A "Codeforces Round 982 (Div. 2)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19     cin.tie(0)->sync_with_stdio(0);
     20     int t;
     21     cin >> t;
     22     while (t--) {
     23         int n;
     24         cin >> n;
     25         int maxw = 0, maxh = 0;
     26         for (int i=0; i<n; i++) {
     27             int w, h;
     28             cin >> w >> h;
     29             maxw = max(maxw, w);
     30             maxh = max(maxh, h);
     31         }
     32         cout << 2 * (maxw + maxh) << "\n";
     33     }
     34     return 0;
     35 }
     36 ```
     37 
     38 [2027B - Stalin Sort](/contest/2027/problem/B "Codeforces Round 982 (Div. 2)")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Code**
     45 
     46 ```
     47 #include <bits/stdc++.h>
     48 
     49 using namespace std;
     50 
     51 int main() {
     52     cin.tie(0)->sync_with_stdio(0);
     53     int t;
     54     cin >> t;
     55     while (t--) {
     56         int n;
     57         cin >> n;
     58         vector<int> A(n);
     59         for (int i=0; i<n; i++) cin >> A[i];
     60         int best = 0;
     61         for (int i=0; i<n; i++) {
     62             int curr = 0;
     63             for (int j=i; j<n; j++) {
     64                 if (A[j] <= A[i]) {
     65                     curr += 1;
     66                 }
     67             }
     68             best = max(best, curr);
     69         }
     70         cout << n - best << "\n";
     71     }
     72   return 0;
     73 }
     74 ```
     75 
     76 [2027C - Add Zeros](/contest/2027/problem/C "Codeforces Round 982 (Div. 2)")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Code**
     83 
     84 ```
     85 #include <bits/stdc++.h>
     86 
     87 using namespace std;
     88 using ll = long long;
     89 
     90 int main() {
     91   cin.tie(0)->sync_with_stdio(0);
     92   int t;
     93   cin >> t;
     94   while (t--) {
     95         int n;
     96         cin >> n;
     97         vector<ll> A(n);
     98         for (int i=0; i<n; i++) cin >> A[i];
     99         map<ll,vector<ll>> adj;
    100         for (int i=1; i<n; i++) {
    101             ll u = A[i] + i;
    102             ll v = u + i;
    103             adj[u].push_back(v);
    104         }
    105         set<ll> vis;
    106         function<void(ll)> dfs = [&](ll u) -> void {
    107             if (vis.count(u)) return;
    108             vis.insert(u);
    109             for (ll v : adj[u]) dfs(v);
    110         };
    111         dfs(n);
    112         cout << *vis.rbegin() << "\n";
    113   }
    114   return 0;
    115 }
    116 ```
    117 
    118 [2027D1 - The Endspeaker (Easy Version)](/contest/2027/problem/D1 "Codeforces Round 982 (Div. 2)")
    119 
    120 **Tutorial**
    121 
    122 ## [2027D1 - The Endspeaker (Easy Version)](/contest/2027/problem/D1 "Codeforces Round 982 (Div. 2)")
    123 
    124 Let's use dynamic programming. We will have $\operatorname{dp}_{i,j}$ be the minimum cost to remove the prefix of length $i$, where the current value of $k$ is $j$. By a type $1$ operation, we can transition from $\operatorname{dp}_{i,j}$ to $\operatorname{dp}_{i,j+1}$ at no cost. Otherwise, by a type $2$ operation, we need to remove some contiguous subarray $a_{i+1}, a_{i+2}, \dots, a_{x}$ (a prefix of the current array), to transition to $\operatorname{dp}_{x,j}$ with a cost of $m - k$.
    125 
    126 Let $r$ be the largest value of $x$ possible. Given we're spending $m - k$ whatever value of $x$ we choose, it's clear to see that we only need to transition to $\operatorname{dp}_{r,j}$. To find $r$ for each value of $i$ and $j$, we can either binary search over the prefix sums or simply maintain $r$ as we increase $i$ for a fixed value of $k$. The answer is then $\operatorname{dp}_{n,k}$. The latter method solves the problem in $\mathcal{O}(nm)$.
    127 
    128 **Code**
    129 
    130 ```
    131 #include <bits/stdc++.h>
    132 
    133 using namespace std;
    134 using ll = long long;
    135 
    136 const int inf = 1 << 30;
    137 
    138 void chmin(int &a, int b) {
    139   a = min(a, b);
    140 }
    141 
    142 int main() {
    143   cin.tie(0)->sync_with_stdio(0);
    144   int t;
    145   cin >> t;
    146   while (t--) {
    147     int n, m;
    148     cin >> n >> m;
    149     vector<int> A(n+1);
    150     for (int i=0; i<n; i++) cin >> A[i];
    151     vector<int> B(m);
    152     for (int i=0; i<m; i++) cin >> B[i];
    153     vector nxt(n, vector<int>(m));
    154     for (int k=0; k<m; k++) {
    155       int r = -1, sum = 0;
    156       for (int i=0; i<n; i++) {
    157         while (r < n && sum <= B[k]) sum += A[++r];
    158         nxt[i][k] = r;
    159         sum -= A[i];
    160       }
    161     }
    162     vector dp(n+1, vector<int>(m, inf));
    163     dp[0][0] = 0;
    164     for (int k=0; k<m; k++) {
    165       for (int i=0; i<n; i++) {
    166         chmin(dp[nxt[i][k]][k], dp[i][k] + m - k - 1);
    167         if (k < m-1)
    168           chmin(dp[i][k+1], dp[i][k]);
    169       }
    170     }
    171     int ans = inf;
    172     for (int k=0; k<m; k++) {
    173       chmin(ans, dp[n][k]);
    174     }
    175     if (ans == inf) {
    176       cout << "-1\n";
    177     } else {
    178       cout << ans << "\n";
    179     }
    180   }
    181   return 0;
    182 }
    183 ```
    184 
    185 [2027D2 - The Endspeaker (Hard Version)](/contest/2027/problem/D2 "Codeforces Round 982 (Div. 2)")
    186 
    187 **Tutorial**
    188 
    189 ## [2027D2 - The Endspeaker (Hard Version)](/contest/2027/problem/D2 "Codeforces Round 982 (Div. 2)")
    190 
    191 Following on from the editorial for D1. Let's have the $\operatorname{dp}$ table store a pair of the minimum cost and the number of ways. Since we're now counting the ways, it's not enough just to consider the transition to $\operatorname{dp}_{r,j}$; we also need to transition to all $\operatorname{dp}_{x,j}$. Doing this naively is too slow, so let's instead find a way to perform range updates.
    192 
    193 Let's say we want to range update $\operatorname{dp}_{l,j}, \operatorname{dp}_{l+1,j}, ..., \operatorname{dp}_{r,j}$. We'll store some updates in another table at either end of the range. Then, for a fixed value of $k$ as we iterate through increasing $i$-values, let's maintain a map of cost to ways. Whenever the number of ways falls to zero, we can remove it from the map. On each iteration, we can set $\operatorname{dp}_{i,j}$ to the smallest entry in the map, and then perform the transitions. This works in $\mathcal{O}(nm \log n)$.
    194 
    195 Bonus: It's also possible to solve without the $\log n$ factor. We can use the fact that $\operatorname{dp}_{i,k}$ is non-increasing for a fixed value of $k$ to make the range updates non-intersecting by updating a range strictly after the previous iteration. Then we can just update a prefix sum array, instead of using a map.
    196 
    197 **Code**
    198 
    199 ```
    200 #include <bits/stdc++.h>
    201 
    202 using namespace std;
    203 using ll = long long;
    204 
    205 const int inf = 1 << 30;
    206 const int MOD = 1000000007;
    207 
    208 int main() {
    209   cin.tie(0)->sync_with_stdio(0);
    210   int t;
    211   cin >> t;
    212   while (t--) {
    213     int n, m;
    214     cin >> n >> m;
    215     vector<int> A(n+1);
    216     for (int i=0; i<n; i++) cin >> A[i];
    217     vector<int> B(m);
    218     for (int i=0; i<m; i++) cin >> B[i];
    219     vector nxt(n, vector<int>(m));
    220     for (int k=0; k<m; k++) {
    221       int r = -1, sum = 0;
    222       for (int i=0; i<n; i++) {
    223         while (r < n && sum <= B[k]) sum += A[++r];
    224         nxt[i][k] = r;
    225         sum -= A[i];
    226       }
    227     }
    228     vector dp(n+1, vector<array<int,2>>(m, {inf, 0}));
    229     vector upd(n+1, vector(m, vector<array<int,3>>()));
    230     upd[0][0].push_back({0, 0, 1});
    231     upd[1][0].push_back({1, 0, 1});
    232     for (int k=0; k<m; k++) {
    233       map<int,array<int,2>> mp;
    234       for (int i=0; i<=n; i++) {
    235         for (auto [t, move, count] : upd[i][k]) {
    236           if (t == 0) {
    237             auto &[a, b] = mp[move];
    238             a += 1;
    239             (b += count) %= MOD;
    240           } else {
    241             auto &[a, b] = mp[move];
    242             a -= 1;
    243             (b += MOD - count) %= MOD;
    244             if (a == 0) mp.erase(move);
    245           }
    246         }
    247         if (mp.empty()) continue;
    248         auto &[move, info] = *mp.begin();
    249         dp[i][k] = {move, info[1]};
    250         if (i == n) continue;
    251         if (k < m-1) {
    252           upd[i][k+1].push_back({0, move, info[1]});
    253           upd[i+1][k+1].push_back({1, move, info[1]});
    254         }
    255         if (nxt[i][k] > i) {
    256           upd[i+1][k].push_back({0, move + (m - k - 1), info[1]});
    257           if (nxt[i][k] < n) {
    258             upd[nxt[i][k]+1][k].push_back({1, move + (m - k - 1), info[1]});
    259           }
    260         }
    261       }
    262     }
    263     map<int,int> mp;
    264     for (int k=0; k<m; k++) {
    265       auto &[move, count] = dp[n][k];
    266       (mp[move] += count) %= MOD;
    267     }
    268     auto &[move, count] = *mp.begin();
    269     if (move == inf) {
    270       cout << "-1\n";
    271     } else {
    272       cout << move << " " << count << "\n";
    273     }
    274   }
    275   return 0;
    276 }
    277 ```
    278 
    279 **Tutorial (Segment Tree)**
    280 
    281 There exists an alternative solution for D1 & D2, using segment tree. We can actually consider the process in reverse; let's reformulate $\operatorname{dp}_{i,j}$ to represent the minimum score required to remove all elements after the $i$-th element, given that the current value of $k$ is $j$.
    282 
    283 Instead of using a dp table, we maintain $m$ segment trees, each of length $n$. The $i$-th segment tree will represent the $i$-th column of the dp table.
    284 
    285 We precalculate for each $i$ and $j$ the furthest position we can remove starting from $i$ — specifically, the maximum subarray starting from $i$ with a sum less than $b_j$. We store this in $\operatorname{nxt}_{i,j}$. This calculation can be done in $\mathcal{O}(nm)$ time using a sliding window.
    286 
    287 To transition in the dp, we have:
    288 
    289 $ \operatorname{dp}_{i,j} = \min\left( \operatorname{dp}_{i, j + 1}, \, \min(\operatorname{dp}_{i + 1, j}, \operatorname{dp}_{i + 2, j}, \ldots, \operatorname{dp}_{{\operatorname{nxt}_{i,j}}, j}) + m - j + 1 \right) $
    290 
    291 This transition can be computed in $\mathcal{O}(\log n)$ time thanks to range querying on the segment tree, so our total complexity is $\mathcal{O}(nm \log n)$. For D2, we can store the count of minimums within each segment, and simply sum these counts to get the total number of ways.
    292 
    293 **Code (Segment Tree)**
    294 
    295 ```
    296 #include <bits/stdc++.h>
    297 using namespace std;
    298 
    299 #define int long long
    300 int modN = 1e9 + 7;
    301 
    302 int mod(int n) {
    303     return (n + modN) % modN;
    304 }
    305 
    306 struct SegmentTree { 
    307     struct Node {
    308         int val = 1e18;
    309         int cnt = 1;
    310     }; 
    311  
    312     vector<Node> st;
    313     int n;
    314     SegmentTree(int n): n(n) {
    315         st.resize(4 * n + 1, Node());
    316     }
    317  
    318     SegmentTree(vector<int> a): n(a.size()) {
    319         st.resize(4 * n + 1, Node());
    320         build(a, 1, 0, n - 1);
    321     }
    322  
    323     void merge(Node& a, Node& b, Node& c) {
    324         a.val = min(b.val, c.val);
    325         if (b.val == c.val)
    326             a.cnt = mod(b.cnt + c.cnt);
    327         else if (b.val < c.val)
    328             a.cnt = b.cnt;
    329         else if (b.val > c.val)
    330             a.cnt = c.cnt;
    331     }
    332  
    333     void build(vector<int>& a, int id, int l, int r) {
    334         if (l == r) {
    335             st[id].val = a[l];
    336             return;
    337         }
    338         int mid = (l + r) / 2;
    339         build(a, id * 2, l, mid);
    340         build(a, id * 2 + 1, mid + 1, r);
    341         merge(st[id], st[id * 2], st[id * 2 + 1]);
    342     }
    343  
    344     void update(int id, int l, int r, int u, int val, int cnt) {
    345         if (l == r) {
    346             st[id].val = val; // or st[id].sum += val
    347             st[id].cnt = cnt;
    348             return;
    349         }
    350         int mid = (l + r) / 2;
    351         if (u <= mid) update(id * 2, l, mid, u, val, cnt);
    352         else update(id * 2 + 1, mid + 1, r, u, val, cnt); 
    353         merge(st[id], st[id * 2], st[id * 2 + 1]);
    354     }
    355  
    356     void update(int idx, int val, int cnt) { //wrapper
    357         update(1, 0, n - 1, idx, val, cnt);
    358     }
    359  
    360     Node query(int id, int l, int r, int u, int v) { //give 0, n - 1 as l and r and 1 as id
    361         if (v < l || r < u) return Node();
    362         if (u <= l && r <= v) {
    363             return st[id];
    364         }
    365         int mid = (l + r) / 2;
    366         auto a = query(id * 2, l, mid, u, v);
    367         auto b = query(id * 2 + 1, mid + 1, r, u, v);
    368         Node res;
    369         merge(res, a, b);
    370         return res;
    371     }
    372  
    373     Node query(int l, int r) { //wrapper
    374         return query(1, 0, n - 1, l, r);
    375     }
    376 };
    377 
    378 void solve() {
    379     int n, m;
    380     cin >> n >> m;
    381     vector<int> a(n), b(m);
    382     for (int &A : a) cin >> A;
    383     for (int &B : b) cin >> B;
    384     if (*max_element(a.begin(), a.end()) > b[0]) {
    385         cout << -1 << '\n';
    386         return;
    387     }
    388     vector<vector<int>> nxt(m, vector<int>(n));
    389     for (int i = 0; i < m; i++) {
    390         int curr = 0, r = -1;
    391         for (int j = 0; j < n; j++) {
    392             while (r + 1 < n && curr + a[r + 1] <= b[i]) 
    393                 curr += a[r + 1], r += 1;
    394             nxt[i][j] = r + 1;
    395             if (j <= r) curr -= a[j];
    396             r = max(r, j);
    397         }
    398     }
    399     vector<SegmentTree> dp(m, SegmentTree(vector<int>(n + 1, 1e18)));
    400     for (int i = 0; i < m; i++)
    401         dp[i].update(n, 0, 1);
    402     for (int i = n - 1; i >= 0; i--) {
    403         for (int j = m - 1; j >= 0; j--) {
    404             auto q1 = dp[j].query(i + 1, nxt[j][i]);
    405             int v1 = q1.val + m - (j + 1), ps1 = q1.cnt;
    406             if (i + 1 <= nxt[j][i]) dp[j].update(i, v1, ps1); 
    407             if (j != m - 1) {
    408                 auto q2 = dp[j + 1].query(i, i);
    409                 int v2 = q2.val, ps2 = q2.cnt;
    410                 auto q3 = dp[j].query(i, i);
    411                 if (v2 < q3.val)
    412                     dp[j].update(i, v2, ps2);
    413                 else if (v2 == q3.val)
    414                     dp[j].update(i, v2, mod(ps2 + q3.cnt));
    415             }
    416         }
    417     }
    418     cout << dp[0].query(0, 0).val << ' ' << dp[0].query(0, 0).cnt << '\n';
    419 }
    420 
    421 signed main() {
    422     cin.tie(0) -> sync_with_stdio(false);
    423     int t;  
    424     cin >> t;
    425     while (t--) 
    426        solve();
    427     return 0;
    428 }
    429 ```
    430 
    431 [2027E1 - Bit Game (Easy Version)](/contest/2027/problem/E1 "Codeforces Round 982 (Div. 2)")
    432 
    433 **Tutorial**
    434 
    435 Tutorial is loading...
    436 
    437 **Code**
    438 
    439 ```
    440 #include <bits/stdc++.h>
    441  
    442 using namespace std;
    443  
    444 int nimber(int x, int a) {
    445   int aprime = 0;
    446   bool goodbit = false;
    447   for (int bit=30; bit>=0; bit--) {
    448     if (x & (1 << bit)) {
    449       aprime *= 2;
    450       if (goodbit || (a & (1 << bit))) {
    451         aprime += 1;
    452       }
    453     } else if (a & (1 << bit)) {
    454       goodbit = true;
    455     }
    456   }
    457  
    458   // g(2^k - 2) = 0, for all k >= 1.
    459   for (int k=1; k<=30; k++) {
    460     if (aprime == (1 << k) - 2) {
    461       return 0;
    462     }
    463   }
    464  
    465   // g(2^k - 1) = k, for all k >= 1.
    466   for (int k=1; k<=30; k++) {
    467     if (aprime == (1 << k) - 1) {
    468       return k;
    469     }
    470   }
    471  
    472   // g(2^k) = k + (-1)^k, for all k >= 0.
    473   for (int k=1; k<=30; k++) {
    474     if (aprime == (1 << k)) {
    475       if (k % 2) return k - 1;
    476       else return k + 1;
    477     }
    478   }
    479  
    480   // g(2^k+1) = g(2^k+2) = ... = g(2^{k+1} - 3) = k + 1, for all k >= 2.
    481   for (int k=2; k<=30; k++) {
    482     if ((1 << k) < aprime && aprime <= (2 << k) - 3) {
    483       return k + 1;
    484     }
    485   }
    486  
    487   // should never get to this point
    488   assert(false);
    489   return -1;
    490 }
    491  
    492 int main() {
    493   cin.tie(0)->sync_with_stdio(0);
    494   int t;
    495   cin >> t;
    496   while (t--) {
    497     int n;
    498     cin >> n;
    499     vector<int> A(n);
    500     for (int i=0; i<n; i++) cin >> A[i];
    501     vector<int> X(n);
    502     for (int i=0; i<n; i++) cin >> X[i];
    503     int curr = 0;
    504     for (int i=0; i<n; i++) curr ^= nimber(X[i], A[i]);
    505     cout << (curr ? "Alice" : "Bob") << "\n";
    506   }
    507   return 0;
    508 }
    509 ```
    510 
    511 [2027E2 - Bit Game (Hard Version)](/contest/2027/problem/E2 "Codeforces Round 982 (Div. 2)")
    512 
    513 **Tutorial**
    514 
    515 Tutorial is loading...
    516 
    517 **Code**
    518 
    519 ```
    520 #include <bits/stdc++.h>
    521  
    522 using namespace std;
    523         
    524 int dp[32][32][6][2][2];
    525  
    526 const int mod = 1000000007;
    527  
    528 int main() {
    529   cin.tie(0)->sync_with_stdio(0);
    530   int t;
    531   cin >> t;
    532   while (t--) {
    533     int n;
    534     cin >> n;
    535     vector<int> A(n);
    536     for (int i=0; i<n; i++) cin >> A[i];
    537     vector<int> B(n);
    538     for (int i=0; i<n; i++) cin >> B[i];
    539     vector<int> curr(32);
    540     curr[0] = 1; // identity
    541     for (int i=0; i<n; i++) {
    542       memset(dp, 0, sizeof dp);
    543       dp[0][0][0][0][0] = 1;
    544       for (int j=0; j<=29; j++) {
    545         int p = 29 - j; // place we are going to add a bit in
    546         for (int k=0; k<=29; k++) { // position of most significant one in a'
    547           for (int type=0; type<6; type++) { // 0, 1, 11111, 11110, 10000, else
    548             for (int good=0; good<2; good++) { // good=1 iff good bit has occured
    549               for (int low=0; low<2; low++) { // low=1 iff prefix below b
    550                 for (int bit=0; bit<2; bit++) { // bit in x
    551                   if (dp[j][k][type][good][low] == 0) 
    552                     continue; // no point in transition since count is 0
    553                   if (!low && (B[i] & (1 << p)) == 0 && bit == 1) 
    554                     continue; // x can't go higher than B[i]
    555                   if (bit == 0) {
    556                     int good2 = good || (A[i] & (1 << p)) != 0; // check good bit
    557                     int low2 = low || (B[i] & (1 << p)) != 0; // check if low
    558                     // nothing added to a' so nothing else changes
    559                     (dp[j+1][k][type][good2][low2] += dp[j][k][type][good][low]) %= mod;
    560                   } else {
    561                     int bita = good || (A[i] & (1 << p)) != 0; // bit in a'
    562                     int k2 = type == 0 ? 0 : k + 1; // increase if MSOne exists
    563                     int type2 = bita ?
    564                       (
    565                         type == 0 ? 1 : // add first one
    566                         (type == 1 || type == 2) ? 2 : // 11111
    567                         5 // can't add 1 after a 0
    568                       ) : (
    569                         (type == 0) ? 0 : // 0
    570                         (type == 1 || type == 4) ? 4 : // 10000
    571                         (type == 2) ? 3 : // 11110
    572                         5 // can't have a zero in any other case
    573                       );
    574                     (dp[j+1][k2][type2][good][low] += dp[j][k][type][good][low]) %= mod;
    575                   }
    576                 }
    577               }
    578             }
    579           }
    580         } 
    581       }
    582       vector<int> count(32); // number of x-values for each nimber
    583       for (int k=0; k<=29; k++) { // position of MSOne
    584         for (int good=0; good<2; good++) { // doesn't matter
    585           for (int low=0; low<2; low++) { // doesn't matter
    586             (count[0] += dp[30][k][0][good][low]) %= mod; // 0
    587             (count[1] += dp[30][k][1][good][low]) %= mod; // 1
    588             (count[k+1] += dp[30][k][2][good][low]) %= mod; // 11111
    589             (count[0] += dp[30][k][3][good][low]) %= mod; // 11110
    590             (count[k+(k%2?-1:1)] += dp[30][k][4][good][low]) %= mod; // 10000
    591             (count[k+1] += dp[30][k][5][good][low]) %= mod; // else
    592           }
    593         }
    594       }
    595       count[0] -= 1; // remove when x=0
    596       vector<int> next(32); // knapsack after adding this pile
    597       for (int j=0; j<32; j++)
    598         for (int k=0; k<32; k++)
    599           (next[j ^ k] += 1LL * curr[j] * count[k] % mod) %= mod;
    600       swap(curr, next);
    601     }
    602     cout << curr[0] << "\n";
    603   }
    604   return 0;
    605 }
    606 ```