Codeforces Round #982 (Div. 2) Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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 and Vladithur for making the process so smooth and enjoyable.

2027A - Rectangle Arrangement

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int maxw = 0, maxh = 0;
        for (int i=0; i<n; i++) {
            int w, h;
            cin >> w >> h;
            maxw = max(maxw, w);
            maxh = max(maxh, h);
        }
        cout << 2 * (maxw + maxh) << "\n";
    }
    return 0;
}

2027B - Stalin Sort

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int i=0; i<n; i++) cin >> A[i];
        int best = 0;
        for (int i=0; i<n; i++) {
            int curr = 0;
            for (int j=i; j<n; j++) {
                if (A[j] <= A[i]) {
                    curr += 1;
                }
            }
            best = max(best, curr);
        }
        cout << n - best << "\n";
    }
  return 0;
}

2027C - Add Zeros

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
        int n;
        cin >> n;
        vector<ll> A(n);
        for (int i=0; i<n; i++) cin >> A[i];
        map<ll,vector<ll>> adj;
        for (int i=1; i<n; i++) {
            ll u = A[i] + i;
            ll v = u + i;
            adj[u].push_back(v);
        }
        set<ll> vis;
        function<void(ll)> dfs = [&](ll u) -> void {
            if (vis.count(u)) return;
            vis.insert(u);
            for (ll v : adj[u]) dfs(v);
        };
        dfs(n);
        cout << *vis.rbegin() << "\n";
  }
  return 0;
}

2027D1 - The Endspeaker (Easy Version)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1 << 30;

void chmin(int &a, int b) {
  a = min(a, b);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(m);
    for (int i=0; i<m; i++) cin >> B[i];
    vector nxt(n, vector<int>(m));
    for (int k=0; k<m; k++) {
      int r = -1, sum = 0;
      for (int i=0; i<n; i++) {
        while (r < n && sum <= B[k]) sum += A[++r];
        nxt[i][k] = r;
        sum -= A[i];
      }
    }
    vector dp(n+1, vector<int>(m, inf));
    dp[0][0] = 0;
    for (int k=0; k<m; k++) {
      for (int i=0; i<n; i++) {
        chmin(dp[nxt[i][k]][k], dp[i][k] + m - k - 1);
        if (k < m-1)
          chmin(dp[i][k+1], dp[i][k]);
      }
    }
    int ans = inf;
    for (int k=0; k<m; k++) {
      chmin(ans, dp[n][k]);
    }
    if (ans == inf) {
      cout << "-1\n";
    } else {
      cout << ans << "\n";
    }
  }
  return 0;
}

2027D2 - The Endspeaker (Hard Version)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 1 << 30;
const int MOD = 1000000007;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(m);
    for (int i=0; i<m; i++) cin >> B[i];
    vector nxt(n, vector<int>(m));
    for (int k=0; k<m; k++) {
      int r = -1, sum = 0;
      for (int i=0; i<n; i++) {
        while (r < n && sum <= B[k]) sum += A[++r];
        nxt[i][k] = r;
        sum -= A[i];
      }
    }
    vector dp(n+1, vector<array<int,2>>(m, {inf, 0}));
    vector upd(n+1, vector(m, vector<array<int,3>>()));
    upd[0][0].push_back({0, 0, 1});
    upd[1][0].push_back({1, 0, 1});
    for (int k=0; k<m; k++) {
      map<int,array<int,2>> mp;
      for (int i=0; i<=n; i++) {
        for (auto [t, move, count] : upd[i][k]) {
          if (t == 0) {
            auto &[a, b] = mp[move];
            a += 1;
            (b += count) %= MOD;
          } else {
            auto &[a, b] = mp[move];
            a -= 1;
            (b += MOD - count) %= MOD;
            if (a == 0) mp.erase(move);
          }
        }
        if (mp.empty()) continue;
        auto &[move, info] = *mp.begin();
        dp[i][k] = {move, info[1]};
        if (i == n) continue;
        if (k < m-1) {
          upd[i][k+1].push_back({0, move, info[1]});
          upd[i+1][k+1].push_back({1, move, info[1]});
        }
        if (nxt[i][k] > i) {
          upd[i+1][k].push_back({0, move + (m - k - 1), info[1]});
          if (nxt[i][k] < n) {
            upd[nxt[i][k]+1][k].push_back({1, move + (m - k - 1), info[1]});
          }
        }
      }
    }
    map<int,int> mp;
    for (int k=0; k<m; k++) {
      auto &[move, count] = dp[n][k];
      (mp[move] += count) %= MOD;
    }
    auto &[move, count] = *mp.begin();
    if (move == inf) {
      cout << "-1\n";
    } else {
      cout << move << " " << count << "\n";
    }
  }
  return 0;
}

Code(Segment Tree)

#include <bits/stdc++.h>
using namespace std;

#define int long long
int modN = 1e9 + 7;

int mod(int n) {
    return (n + modN) % modN;
}

struct SegmentTree { 
    struct Node {
        int val = 1e18;
        int cnt = 1;
    }; 
 
    vector<Node> st;
    int n;
    SegmentTree(int n): n(n) {
        st.resize(4 * n + 1, Node());
    }
 
    SegmentTree(vector<int> a): n(a.size()) {
        st.resize(4 * n + 1, Node());
        build(a, 1, 0, n - 1);
    }
 
    void merge(Node& a, Node& b, Node& c) {
        a.val = min(b.val, c.val);
        if (b.val == c.val)
            a.cnt = mod(b.cnt + c.cnt);
        else if (b.val < c.val)
            a.cnt = b.cnt;
        else if (b.val > c.val)
            a.cnt = c.cnt;
    }
 
    void build(vector<int>& a, int id, int l, int r) {
        if (l == r) {
            st[id].val = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, id * 2, l, mid);
        build(a, id * 2 + 1, mid + 1, r);
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }
 
    void update(int id, int l, int r, int u, int val, int cnt) {
        if (l == r) {
            st[id].val = val; // or st[id].sum += val
            st[id].cnt = cnt;
            return;
        }
        int mid = (l + r) / 2;
        if (u <= mid) update(id * 2, l, mid, u, val, cnt);
        else update(id * 2 + 1, mid + 1, r, u, val, cnt); 
        merge(st[id], st[id * 2], st[id * 2 + 1]);
    }
 
    void update(int idx, int val, int cnt) { //wrapper
        update(1, 0, n - 1, idx, val, cnt);
    }
 
    Node query(int id, int l, int r, int u, int v) { //give 0, n - 1 as l and r and 1 as id
        if (v < l || r < u) return Node();
        if (u <= l && r <= v) {
            return st[id];
        }
        int mid = (l + r) / 2;
        auto a = query(id * 2, l, mid, u, v);
        auto b = query(id * 2 + 1, mid + 1, r, u, v);
        Node res;
        merge(res, a, b);
        return res;
    }
 
    Node query(int l, int r) { //wrapper
        return query(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int &A : a) cin >> A;
    for (int &B : b) cin >> B;
    if (*max_element(a.begin(), a.end()) > b[0]) {
        cout << -1 << '\n';
        return;
    }
    vector<vector<int>> nxt(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        int curr = 0, r = -1;
        for (int j = 0; j < n; j++) {
            while (r + 1 < n && curr + a[r + 1] <= b[i]) 
                curr += a[r + 1], r += 1;
            nxt[i][j] = r + 1;
            if (j <= r) curr -= a[j];
            r = max(r, j);
        }
    }
    vector<SegmentTree> dp(m, SegmentTree(vector<int>(n + 1, 1e18)));
    for (int i = 0; i < m; i++)
        dp[i].update(n, 0, 1);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            auto q1 = dp[j].query(i + 1, nxt[j][i]);
            int v1 = q1.val + m - (j + 1), ps1 = q1.cnt;
            if (i + 1 <= nxt[j][i]) dp[j].update(i, v1, ps1); 
            if (j != m - 1) {
                auto q2 = dp[j + 1].query(i, i);
                int v2 = q2.val, ps2 = q2.cnt;
                auto q3 = dp[j].query(i, i);
                if (v2 < q3.val)
                    dp[j].update(i, v2, ps2);
                else if (v2 == q3.val)
                    dp[j].update(i, v2, mod(ps2 + q3.cnt));
            }
        }
    }
    cout << dp[0].query(0, 0).val << ' ' << dp[0].query(0, 0).cnt << '\n';
}

signed main() {
    cin.tie(0) -> sync_with_stdio(false);
    int t;  
    cin >> t;
    while (t--) 
       solve();
    return 0;
}

2027E1 - Bit Game (Easy Version)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

// calculate nimber in O(log A)
int nimber(int x, int a) {
  // find bad positions
  vector<int> badpos;
  int nbits = 0;
  bool pref = 1;
  for (int i=30; i>=0; i--) {
    int mask = 1 << i;
    if ((x & mask) != 0) nbits += 1;
    if ((x & mask) == 0 && (a & mask) != 0) pref = 0;
    if ((x & mask) != 0 && (a & mask) == 0 && pref) badpos.push_back(nbits); 
  }

  // find a'
  int aprime = (1 << nbits) - 1;
  for (int i : badpos) {
    aprime -= 1 << (nbits - i);
  }

  // g(2^k - 2) = 0, for all k >= 1.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k) - 2) {
      return 0;
    }
  }

  // g(2^k - 1) = k, for all k >= 1.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k) - 1) {
      return k;
    }
  }

  // g(2^k) = k + (-1)^k, for all k >= 0.
  for (int k=1; k<=30; k++) {
    if (aprime == (1 << k)) {
      if (k % 2) return k - 1;
      else return k + 1;
    }
  }

  // g(2^k+1) = g(2^k+2) = ... = g(2^{k+1} - 3) = k + 1, for all k >= 2.
  for (int k=2; k<=30; k++) {
    if ((1 << k) < aprime && aprime <= (2 << k) - 3) {
      return k + 1;
    }
  }

  // should never get to this point
  assert(false);
  return -1;
}

int main() {
  // works in O(n log A)
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> X(n);
    for (int i=0; i<n; i++) cin >> X[i];
    int cur = 0;
    for (int i=0; i<n; i++) {
      cur ^= nimber(X[i], A[i]);
    }
    cout << (cur ? "Alice" : "Bob") << "\n";
  }
  return 0;
}

2027E2 - Bit Game (Hard Version)

Tutorial

Code

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1'000'000'007;

int dp[32][32][3][2][2][3];

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i=0; i<n; i++) cin >> A[i];
    vector<int> B(n);
    for (int i=0; i<n; i++) cin >> B[i];
    vector<int> curr(32);
    curr[0] = 1;
    for (int i=0; i<n; i++) {
      memset(dp, 0, sizeof dp);

      // dp[i][m][g][fl][gl][hl][il] : 
      // -> m = number of 1s after first good bit
      // -> g = min(2, number of good bits added)
      // -> fl = 1 iff x prefix == high prefix
      // -> gl = 1 iff no x=0 where a=1
      // -> hl = 0 iff no bad bits after first good bit
      //    hl = 1 iff one bad bit after first good bit
      //    hl = 2 iff any one-bit placed after il=1
      int a = A[i];
      int high = B[i];
      dp[0][0][0][1][1][0] = 1;
      for (int i=0; i<=30; i++) {
        int bit = 30 - i;
        int mask = 1 << bit;
        for (int m=0; m<=i; m++) {
          for (int g=0; g<3; g++) {
            for (int fl=0; fl<2; fl++) {
              for (int gl=0; gl<2; gl++) {
                for (int hl=0; hl<3; hl++) {  
                  if (dp[i][m][g][fl][gl][hl] == 0) continue;
                  for (int val=0; val<2; val++) {
                    int fl2 = fl;
                    if (fl && (high & mask) == 0 && val == 1) continue;
                    if (fl && (high & mask) != 0 && val == 0) fl2 = 0;
                    int gl2 = gl;
                    if ((a & mask) != 0 && val == 0) gl2 = 0;
                    bool good = 1;
                    if (gl && (a & mask) == 0 && val == 1) good = 0;
                    int m2 = m;
                    if (g != 0 && val == 1) m2 += 1;
                    int g2 = g;
                    if (g2 < 2 && val == 1 && good) g2 += 1;
                    int hl2 = hl;
                    if (hl == 0 && g > 0 && !good) hl2 = 1;
                    if (hl == 1 && val == 1) hl2 = 2;
                    (dp[i+1][m2][g2][fl2][gl2][hl2] += dp[i][m][g][fl][gl][hl]) %= MOD;
                  }
                }
              }  
            }
          }
        }
      }

      vector<int> here(32);
      for (int m=0; m<32; m++) {
        for (int g=0; g<3; g++) {
          for (int fl=0; fl<2; fl++) {
            for (int gl=0; gl<2; gl++) {
              for (int hl=0; hl<3; hl++) {
                if (dp[31][m][g][fl][gl][hl] == 0) continue;
                if (g == 0) {
                  (here[0] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (hl == 0) {
                  (here[m+1] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (hl == 1) {
                  (here[0] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else if (g == 1) {
                  int nim = m;
                  if (m % 2) nim -= 1;
                  else nim += 1;
                  (here[nim] += dp[31][m][g][fl][gl][hl]) %= MOD;
                } else {
                  (here[m+1] += dp[31][m][g][fl][gl][hl]) %= MOD;
                }
              }
            }
          }
        }
      }
      
      // remove x=0
      here[0] -= 1;
      
      // update knapsack
      vector<int> next(32);
      for (int i=0; i<32; i++) {
        for (int j=0; j<32; j++) {
          (next[i^j] += 1LL * curr[i] * here[j] % MOD) %= MOD;
        }
      }
      swap(curr, next);
    }
    cout << curr[0] << "\n";
  } 
  return 0;
}

Rev.	Кто	Когда	Δ	Комментарий
en13	myst-6	2024-10-27 12:41:35	2	Tiny change: 'r<int> A(n);\n fo' -> 'r<int> A(n+1);\n fo'
en12	myst-6	2024-10-27 12:32:22	2	Tiny change: 'r<int> A(n);\n fo' -> 'r<int> A(n+1);\n fo'
en11	yud08	2024-10-26 21:27:44	0	(published)
en10	myst-6	2024-10-26 21:18:43	159	Tiny change: 'g from $i$~--- specifica' -> 'g from $i$ — specifica'
en9	yud08	2024-10-26 21:12:54	34
en8	yud08	2024-10-26 21:11:24	2641
en7	yud08	2024-10-26 21:01:32	3575	Tiny change: 'torial">\nFollowin' -> 'torial">\nThe Endspeaker (Hard Version)\nFollowin'
en6	yud08	2024-10-26 20:53:11	3178	Tiny change: 'nt mod = 1'000'000'007;\n \ni' -> 'nt mod = 1000000007;\n \ni'
en5	yud08	2024-10-26 20:48:48	82	Tiny change: 'oiler>\n\n\n<spoil' -> 'oiler>\n\n<spoil'
en4	yud08	2024-10-26 20:44:13	15564	Tiny change: 'spoiler>\n' -> 'spoiler>\n<spoiler summary="Code">\n[model.cpp:2027A]\n</spoiler>\n'
en3	yud08	2024-10-26 20:23:12	3	Tiny change: ' day help or hold a' -> ' day help to or hold a'
en2	yud08	2024-10-26 20:22:07	1
en1	yud08	2024-10-26 20:19:22	984	Initial revision (saved to drafts)

История