2049A - MEX Destruction

Case 1: All elements are $$$0$$$. Then the answer is $$$0$$$.

Case 2: Some element is non-zero, and all non-zero elements form a contiguous subarray. Then the answer is $$$1$$$ since we can choose that subarray and replace it with a $$$0$$$.

Case 3: Otherwise, the answer is $$$2$$$.

• We can replace the entire array with a non-zero element (since $$$0$$$ is in the array), then replace the entire array again with a $$$0$$$ (since the only element left is non-zero).
• $$$1$$$ operation is not enough. If we only use $$$1$$$ operation, the selected subarray must contain all non-zero elements. Since the non-zero elements do not form a subarray, the selected subarray must contain a $$$0$$$, thus the $$$\operatorname{MEX}$$$ will be non-zero.

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

void solve()
{
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    while (!a.empty() && a.back() == 0)
        a.pop_back();

    reverse(a.begin(), a.end());
    while (!a.empty() && a.back() == 0)
        a.pop_back();
    reverse(a.begin(), a.end());

    if (a.empty())
    {
        cout << 0 << '\n';
        return;
    }

    bool hasZero = false;
    for (const auto x : a)
        hasZero |= x == 0;
    if (hasZero)
        cout << 2 << '\n';
    else
        cout << 1 << '\n';
}

int main()
{
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
        solve();

    return 0;
}

2049B - pspspsps

Since the entire $$$p$$$ must be a permutation, if $$$s_1 =$$$s, we can set $$$s_1 = $$$., and if $$$s_n =$$$p, we can set $$$s_n =$$$..

After that, the answer is YES if and only if all non-dot characters in $$$s$$$ are all p or s.

If all non-dot characters are p, we can choose the permutation $$$p = [1, 2, \ldots, n]$$$. If all non-dot characters are s, we can choose $$$p = [n, n - 1, \ldots, 1]$$$.

Otherwise, there exists both a p and a s. Suppose for contradiction that there is a solution. Let $$$a$$$ and $$$b$$$ represent the subarrays represented by the p and s respectively. Without loss of generality, suppose $$$a$$$ is the shorter subarray.

• Since $$$b$$$ is also a permutation, the elements of $$$a$$$ must be in $$$b$$$. Since $$$p$$$ is a permutation, $$$a$$$ must be a subarray of $$$b$$$.
• However, $$$b$$$ cannot contain $$$a$$$: since $$$a$$$ is not the entire $$$p$$$, $$$a$$$ does not contain $$$p_n$$$. However, $$$b$$$ contains $$$p_n$$$. Contradiction.

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

void solve()
{
    int n; cin >> n;
    string s; cin >> s;
    if (s[0] == 's') s[0] = '.';
    if (s.back() == 'p') s.back() = '.';
    bool found_p = false;
    bool found_s = false;
    for (const auto c : s)
    {
        switch (c)
        {
        case 'p':
            found_p = true;
            break;
        case 's':
            found_s = true;
            break;
        }
    }
    cout << (found_p && found_s ? "NO" : "YES") << '\n';
}

int main()
{
    int t; cin >> t;
    for (int i = 0; i < t; i++) solve();

    return 0;
}

2049C - MEX Cycle

There are many possible solutions. The simplest one we can find (thanks to Kaey) is as follows:

• Set $$$a_x = 0, a_{x+1} = 1, a_{x+2} = 0, \ldots$$$, alternating between 0 and 1, wrapping around accordingly. Formally, using 0-based indexing, set $$$a_{(x+i) \bmod n} = i \bmod 2$$$ for all $$$i$$$ ($$$0 \le i \le n - 1$$$).
• If $$$n$$$ is odd or if $$$x - y$$$ is even, set $$$a_x = 2$$$.

Why this works:

• If $$$n$$$ is even and $$$x - y$$$ is odd, all $$$0$$$'s are only friends with $$$1$$$'s and vice versa.
• If $$$n$$$ is odd, $$$a_x$$$ will be adjacent to $$$0$$$ and $$$1$$$, so we set $$$a_x = 2$$$. Now $$$a$$$ is valid ignoring the extra friendship. Adding in the extra friendship, $$$a$$$ is still valid since $$$a_x = 2 > a_y$$$, so it will not affect $$$a_y$$$.
• If $$$n$$$ is even and $$$x - y$$$ is even, the extra friendship connects two $$$0$$$ or two $$$1$$$. Setting $$$a_x = 2$$$ works because dragon $$$x$$$'s friends still have another neighbor to maintain their $$$\operatorname{MEX}$$$.

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    --x; --y;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) ans[(x + i) % n] = i % 2;
    if (n % 2 || (x - y) % 2 == 0)
        ans[x] = 2;
    for (auto x : ans)cout << x << ' ';
    cout << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
}

2049D - Shift + Esc

Let $$$f(i,j)$$$ be the minimum cost to move to cell $$$(i,j)$$$ after shifting and $$$g(i,j,x)$$$ be the minimum cost to move to $$$(i,j)$$$ assuming row $$$i$$$ is shifted to the left by $$$x$$$.

For simplicity sake, we will add a row with all zeros above the first row. Also note that the operations with states denoting columns are all under modulo $$$m$$$, I am omitting the notation to avoid clutter.

The transitions are as follows:

Base cases:

From row $$$i$$$ to row $$$i+1$$$:

In $$$(*)$$$, the $$$f(i-1,j)$$$ term is from the case where you move from $$$(i-1,j)$$$ to $$$(i,j)$$$. Similarly the $$$g(i,j-1,x)$$$ term is from the case where you move from $$$(i,j-1)$$$ to $$$(i,j)$$$.

The final answer is $$$f(n,m-1)$$$. The overall complexity is $$$O(nm^2)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[511][511],a[511][511];

void solve()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=0;j<m;j++)cin>>a[i][j];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<m;j++)dp[i][j] = 1e18;
    }

    dp[0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int shift = 0;shift<m;shift++){
            vector<ll>tmp(m,1e18);
            for(int j=0;j<m;j++)tmp[j] = dp[i-1][j] + a[i][(j+shift)%m] + k*1LL*shift;

            for(int j=0;j<m;j++)tmp[j] = min(tmp[j],tmp[(j+m-1)%m] + a[i][(j+shift)%m]);
            for(int j=0;j<m;j++)tmp[j] = min(tmp[j],tmp[(j+m-1)%m] + a[i][(j+shift)%m]);
            for(int j=0;j<m;j++)dp[i][j] = min(dp[i][j],tmp[j]);
        }
        //for(int j=0;j<m;j++)cout<<dp[i][j]<<" ";
       // cout<<'\n';
    }
    cout<<dp[n][m-1]<<endl;
}

int main()
{
    int t; cin>>t;
    for (int i = 0; i < t; i++) solve();
}

2049E - Broken Queries

Make 2 queries $$$[1, n/4]$$$ and $$$[n/4+1, n/2]$$$. This tells us which half the 1 is in: it is in $$$[1, n / 2]$$$ if the query results are different and $$$[n / 2 + 1, n]$$$ otherwise.

Make 1 query: query $$$[1, n/2]$$$ if the 1 is in it or $$$[n/2+1, n]$$$ otherwise. This tells us that $$$k < n / 2$$$ if the result is $$$1$$$ and $$$k \ge n / 2$$$ otherwise.

Without loss of generality, assume that the 1 is in $$$[1, n / 2]$$$. Now we can binary search for $$$k$$$ in $$$[1, n / 2]$$$ or $$$[n / 2 + 1, n]$$$. Let $$$k'$$$ be our guess.

• If $$$k < n / 2$$$, query $$$[n / 2 + 1, n / 2 + k']$$$. The result is $$$1$$$ if $$$k' \ge k$$$ and $$$0$$$ otherwise.
• If $$$k \ge n / 2$$$, query $$$[1, k']$$$. The result is $$$0$$$ if $$$k' \ge k$$$ and $$$1$$$ otherwise.

In both cases, the binary search takes $$$\log n - 1 \le 29$$$ queries. Overall, this takes at most $$$2 + 1 + 29 = 32$$$ queries.

The limit of $$$33$$$ queries (instead of $$$32$$$) is to allow less optimized solutions and other solutions. For example, one can instead do 3 queries in the beginning $$$[1, n / 4]$$$, $$$[n / 4 + 1, n / 2]$$$, $$$[n / 2 + 1, 3n / 4]$$$ to determine which quarter the 1 is in.

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

int qry(int l, int r, bool rev = 0, int n = 0) {
    if (rev) {
        int t = n - l;
        l = n - r;
        r = t;
    }
    cout << "? " << l + 1 << ' ' << r << endl;
    cin >> r;
    return r;
}

void solve() {
    int n;
    cin >> n;
    int a = qry(0, n / 4);
    int b = qry(n / 4, n / 2);
    bool kSmall = 1;
    bool firstHalf = 1;
    if (a == b) firstHalf = 0;
    int bs = 0;
    if (qry(0, n / 2, firstHalf, n) == 0) kSmall = 0;
    if (kSmall) {
        for (int k = n / 4; k; k /= 2)
            if (qry(0, bs + k, firstHalf, n) == 0) bs += k;
    } else {
        bs = n / 2 - 1;
        for (int k = n / 4; k; k /= 2)
            if (qry(0, bs + k, 1-firstHalf, n) == 1) bs += k;
    }
    cout << "! " << bs + 1 << endl;
}

int main() {
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

2049F - MEX OR Mania

Let's figure out when a sequence is good. Let $$$m$$$ be the maximum element of the sequence. Notice that the bitwise OR of the sequence is at least $$$m$$$ and as MEX $$$-$$$ OR $$$=1$$$, that means MEX has to be at least $$$m + 1$$$. Which means all elements from $$$0$$$ to $$$m$$$ has to be present in the sequence. As MEX can't be greater than $$$m + 1$$$, the MEX has to be exactly $$$m + 1$$$.

Now we need to check for which $$$m$$$ the bitwise OR of the elements from $$$0$$$ to $$$m$$$ is exactly $$$m$$$. It's not hard to see that this is true for $$$m = 2^k - 1$$$ for some integer $$$k \geq 0$$$. The reason is that all bits from $$$0$$$ to $$$k - 1$$$ have to be set in $$$m$$$ for the OR to be $$$m$$$ and it's only possible if $$$m$$$ is of the form $$$2^k - 1$$$.

So, a sequence is good if the maximum element is $$$m = 2^k - 1$$$ for some integer $$$k$$$ and all elements from $$$0$$$ to $$$m$$$ are present in the sequence.

Now, let's see how to answer the queries without any updates. To find the longest good subarray, we can use a two-pointers approach. But a better way to do this is to fix the power $$$k (0 \leq k \leq \log_2 n)$$$ and find the longest good subarray with maximum element $$$2^k - 1$$$. To do this, ignore the elements greater than $$$2^k - 1$$$ and then split the array into segments of consecutive numbers where each segment has elements from $$$0$$$ to $$$2^k - 1$$$. To check if a segment is good, we can track the number of distinct elements in the segment. If the number of distinct elements is $$$2^k$$$, then the segment is good.

So to sum it up, for each power $$$k$$$, we will track some segments/components and the number of distinct elements in them and also the lengths of the segments to get the longest one during queries.

Now regarding the updates, it is hard to track everything if we do the updates normally. But its's easier if we look at them in reverse order!

Then each update will be decreasing the value of $$$a_i$$$ by $$$x$$$. Then for each power $$$k$$$, we will have to add a new element to a component or merge two components. For tracking distinct elements, we can use a map or unordered map and to merge we can use DSU with small to large merging. And that's pretty much it.

Please check my code for more details.

Overall complexity is $$$O((n + q) \log^2 n)$$$ or $$$O((n + q) \log^3 n)$$$ depending on if you use an unordered map or a map.

#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 9, Q = 3e5 + 9;
using ll = long long;
 
struct GoodSet { // insert, erase and track distinct and total elements
  map<int, int> mp;
  int size;
  int k;
  GoodSet() {}
  GoodSet(int _k): k(_k), size(0) { };
  void insert(int x, int c = 1) {
    mp[x] += c;
    size += c;
  }
  void erase(int x) {
    if (mp[x] == 1) {
      mp.erase(x);
    }
    else {
      mp[x]--;
    }
    size -= 1;
  }
  void merge(GoodSet oth) {
    for (auto [x, c]: oth.mp) {
      insert(x, c);
    }
  }
  bool is_good() { // check if all elements from 0 to 2^k - 1 exists in the set
    return (int) mp.size() == (1 << k);
  }
  int get_value() {
    if (is_good()) return size;
    return 0;
  }
};
 
struct MaxSet { // insert, erase and track max element
  map<int, int> mp;
  MaxSet() {}
  void insert(int x) {
    mp[x]++;
  }
  void erase(int x) {
    mp[x]--;
    if (mp[x] == 0) mp.erase(x);
  }
  int get_max() {
    return mp.rbegin() -> first;
  }
};
 
struct DSU { // DSU for each power of 2
  int n;
  int k;
  vector<int> par;
  vector<GoodSet> comp;
  MaxSet good_lengths;
  DSU() {}
  DSU(int _n, int _k): n(_n), k(_k) {
    par.resize(n + 1);
    comp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
      par[i] = i;
      comp[i] = GoodSet(k);
      good_lengths.insert(comp[i].get_value());
    }
  }
  int find(int u) {
    return par[u] = (par[u] == u ? u : find(par[u]));
  }
  void merge(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return;
    good_lengths.erase(comp[u].get_value());
    good_lengths.erase(comp[v].get_value());
 
    // small to large merging
    if (comp[u].mp.size() < comp[v].mp.size()) {
      comp[u].mp.swap(comp[v].mp);
      swap(comp[u].size, comp[v].size);
    }
    comp[u].merge(comp[v]);
    comp[v].mp.clear(); // clear to save up memory
 
    good_lengths.insert(comp[u].get_value());
    par[v] = u;
  }
  // insert or erase an element from the component that u belongs to
  void update_in_component(int u, int x, bool insert = true) {
    u = find(u);
    good_lengths.erase(comp[u].get_value());
    if (insert) comp[u].insert(x);
    else comp[u].erase(x);
    good_lengths.insert(comp[u].get_value());
  }
};
DSU f[18];
ll a[N]; // make it long long as total sum can be huge
int id[Q], x[Q], ans[Q];
void solve() {
  int n, q; cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i++) {
    cin >> id[i] >> x[i];
    a[id[i]] += x[i];
  }
  MaxSet se;
  for (int k = 0; (1 << k) <= n; k++) {
    f[k] = DSU(n, k);
    for (int i = 1; i <= n; i++) {
      if (a[i] < (1 << k)) {
        f[k].update_in_component(i, a[i], true);
      }
    }
    for (int i = 2; i <= n; i++) {
      if (a[i] < (1 << k) and a[i - 1] < (1 << k)) {
        f[k].merge(i - 1, i);
      }
    }
    se.insert(f[k].good_lengths.get_max());
  }
  for (int qid = q; qid >= 1; qid--) {
    ans[qid] = se.get_max();
    int i = id[qid], sub = x[qid];
    for (int k = 0; (1 << k) <= n; k++) {
      se.erase(f[k].good_lengths.get_max());
 
      if (a[i] < (1 << k)) f[k].update_in_component(i, a[i], false);
      if (a[i] - sub < (1 << k)) f[k].update_in_component(i, a[i] - sub, true);
 
      if (a[i] >= (1 << k) and a[i] - sub < (1 << k)) {
        if (i > 1 and a[i - 1] < (1 << k)) {
          f[k].merge(i - 1, i);
        }
        if (i + 1 <= n and a[i + 1] < (1 << k)) {
          f[k].merge(i, i + 1);
        }
      }
 
      se.insert(f[k].good_lengths.get_max());
    }
    a[i] -= sub;
  }
 
  for (int i = 1; i <= q; i++) {
    cout << ans[i] << '\n';
  }
}
 
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}