Codeforces Round #982 (Div. 2) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
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;
 
int nimber(int x, int a) {
  int aprime = 0;
  bool goodbit = false;
  for (int bit=30; bit>=0; bit--) {
    if (x & (1 << bit)) {
      aprime *= 2;
      if (goodbit || (a & (1 << bit))) {
        aprime += 1;
      }
    } else if (a & (1 << bit)) {
      goodbit = true;
    }
  }
 
  // 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() {
  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 curr = 0;
    for (int i=0; i<n; i++) curr ^= nimber(X[i], A[i]);
    cout << (curr ? "Alice" : "Bob") << "\n";
  }
  return 0;
}

2027E2 - Bit Game (Hard Version)

Tutorial

Code

#include <bits/stdc++.h>
 
using namespace std;
        
int dp[32][32][6][2][2];
 
const int mod = 1000000007;
 
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; // identity
    for (int i=0; i<n; i++) {
      memset(dp, 0, sizeof dp);
      dp[0][0][0][0][0] = 1;
      for (int j=0; j<=29; j++) {
        int p = 29 - j; // place we are going to add a bit in
        for (int k=0; k<=29; k++) { // position of most significant one in a'
          for (int type=0; type<6; type++) { // 0, 1, 11111, 11110, 10000, else
            for (int good=0; good<2; good++) { // good=1 iff good bit has occured
              for (int low=0; low<2; low++) { // low=1 iff prefix below b
                for (int bit=0; bit<2; bit++) { // bit in x
                  if (dp[j][k][type][good][low] == 0) 
                    continue; // no point in transition since count is 0
                  if (!low && (B[i] & (1 << p)) == 0 && bit == 1) 
                    continue; // x can't go higher than B[i]
                  if (bit == 0) {
                    int good2 = good || (A[i] & (1 << p)) != 0; // check good bit
                    int low2 = low || (B[i] & (1 << p)) != 0; // check if low
                    // nothing added to a' so nothing else changes
                    (dp[j+1][k][type][good2][low2] += dp[j][k][type][good][low]) %= mod;
                  } else {
                    int bita = good || (A[i] & (1 << p)) != 0; // bit in a'
                    int k2 = type == 0 ? 0 : k + 1; // increase if MSOne exists
                    int type2 = bita ?
                      (
                        type == 0 ? 1 : // add first one
                        (type == 1 || type == 2) ? 2 : // 11111
                        5 // can't add 1 after a 0
                      ) : (
                        (type == 0) ? 0 : // 0
                        (type == 1 || type == 4) ? 4 : // 10000
                        (type == 2) ? 3 : // 11110
                        5 // can't have a zero in any other case
                      );
                    (dp[j+1][k2][type2][good][low] += dp[j][k][type][good][low]) %= mod;
                  }
                }
              }
            }
          }
        } 
      }
      vector<int> count(32); // number of x-values for each nimber
      for (int k=0; k<=29; k++) { // position of MSOne
        for (int good=0; good<2; good++) { // doesn't matter
          for (int low=0; low<2; low++) { // doesn't matter
            (count[0] += dp[30][k][0][good][low]) %= mod; // 0
            (count[1] += dp[30][k][1][good][low]) %= mod; // 1
            (count[k+1] += dp[30][k][2][good][low]) %= mod; // 11111
            (count[0] += dp[30][k][3][good][low]) %= mod; // 11110
            (count[k+(k%2?-1:1)] += dp[30][k][4][good][low]) %= mod; // 10000
            (count[k+1] += dp[30][k][5][good][low]) %= mod; // else
          }
        }
      }
      count[0] -= 1; // remove when x=0
      vector<int> next(32); // knapsack after adding this pile
      for (int j=0; j<32; j++)
        for (int k=0; k<32; k++)
          (next[j ^ k] += 1LL * curr[j] * count[k] % mod) %= mod;
      swap(curr, next);
    }
    cout << curr[0] << "\n";
  }
  return 0;
}

Rev.	By	When	Δ	Comment
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)

History