Since $$$a_i+b_i \le a_{i+1}+b_{i+1}$$$, then $$$a_i+b_i$$$ can be equal to $$$a_{i+1}+b_{i+1}$$$.

Therefore, any permutation $$$b$$$ which satisfies $$$a_1+b_1=a_2+b_2=\ldots=a_n+b_n$$$ is a valid answer.

If $$$b_i=n+1-a_i$$$, then:

1. $$$b$$$ is a permutation;
2. $$$a_1+b_1=a_2+b_2=\ldots=a_n+b_n=n+1$$$

Consequently, $$$b=[n+1-a_1,n+1-a_2,\ldots,n+1-a_i,\ldots,n+1-a_n]$$$ is a valid answer.

Time complexity per test case : $$$O(N)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
void tc(){
    ll n;
    cin>>n;
    for(ll i=0;i<n;i++){
        ll x;
        cin>>x;
        cout<<n+1-x<<' ';
    }
    cout<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll t; cin>>t; while(t--)
        tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$max_a(x)$$$ be the length of the longest subarray from $$$a$$$ containing only elements equal to $$$x$$$. If $$$x$$$ doesn't appear in $$$a$$$, then $$$max_a(x)=0$$$.

Similarly, let $$$max_b(x)$$$ be the length of the longest subarray from $$$b$$$ containing only elements equal to $$$x$$$. If $$$x$$$ doesn't appear in $$$b$$$, then $$$max_b(x)=0$$$.

$$$max_a$$$ and $$$max_b$$$ can be computed in $$$O(N)$$$ by scanning the array while updating current maximal subarray.

When merging two arrays, it is possible to force a particular subarray $$$[a_{l_1},a_{l_1+1},\ldots,a_{r_1}]$$$ to be adjacent to another particular subarray $$$[b_{l_2},b_{l_2+1},\ldots,b_{r_2}]$$$ in the merged array.

If $$$a_{l_1}=b_{l_2}$$$, then the merged array will have a subarray consisting of $$$(r_1-l_1+1)+(r_2-l_2+1)$$$ equal elements.

Therefore, the answer is equal to:

Time complexity per testcase: $$$O(N)$$$.

#include <bits/stdc++.h>

using namespace std;

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        vector<int> b(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
        }
        for (int i = 1; i <= n; ++i)
        {
            cin >> b[i];
        }
        vector<int> fa(n + n + 1);
        vector<int> fb(n + n + 1);
        int p = 1;
        for (int i = 2; i <= n; ++i)
        {
            if (a[i] != a[i - 1])
            {
                fa[a[i - 1]] = max(fa[a[i - 1]], i - p);
                p = i;
            }
        }
        fa[a[n]] = max(fa[a[n]], n - p + 1);

        p = 1;
        for (int i = 2; i <= n; ++i)
        {
            if (b[i] != b[i - 1])
            {
                fb[b[i - 1]] = max(fb[b[i - 1]], i - p);
                p = i;
            }
        }
        fb[b[n]] = max(fb[b[n]], n - p + 1);

        int ans = 0;
        for (int i = 1; i <= n + n; ++i)
        {
            ans = max(ans, fa[i] + fb[i]);
        }

        cout << ans << '\n';
    }
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

This problem can be solved via dynamic programming. From here on out, step $$$1$$$ from the statement will be called a "scan".

Let $$$dp[i]$$$ be the number of scans needed to activate node $$$i$$$, and $$$id[i]$$$ be the index (in the order from the input) of the edge which activated node $$$i$$$.

Intially, since only $$$1$$$ is active, $$$dp[1]=1$$$ and $$$id[1]=0$$$.

We will perform a dfs traversal starting from node $$$1$$$. When we process an edge $$$(u,v)$$$, one of the following two cases can happen:

1. If $$$index((u,v)) \ge id[u]$$$, we can visit $$$v$$$ in the same scan as $$$u$$$:

1. If $$$index((u,v)) \lt id[u]$$$, $$$v$$$ will be visited in the next scan after $$$dp[u]$$$:

The answer is $$$max_{i=1}^n(dp[i])$$$.

Time complexity per test case: $$$O(n)$$$

#include<bits/stdc++.h>

using namespace std;
const int NMAX = 2e5+5;
int dp[NMAX], id[NMAX];
vector<pair<int,int>> edg[NMAX];
void dfs(int u){
    for(auto it : edg[u]){
        if(dp[it.first] == 0){
            dp[it.first] = dp[u] + (it.second <= id[u]);
            id[it.first] = it.second;
            dfs(it.first);
        }
    }
}
void tc(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) dp[i] = id[i] = 0, edg[i].clear();
    for(int i=1; i<n; i++){
        int u,v;
        cin>>u>>v;
        edg[u].push_back({v,i});
        edg[v].push_back({u,i});
    }
    dp[1] = 1;
    dfs(1);
    int ans = 0;
    for(int i=1; i<=n; i++) ans=max(ans,dp[i]);
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
        tc();
    return 0;
}

#include <bits/stdc++.h>

const int NMAX = 3e5 + 5, INF = 1e9;

int n, f[NMAX], d[NMAX];
std :: vector < std :: pair < int, int > > G[NMAX];

void DFS(int node, int t) {
    f[node] = true;

    for (int i = 0; i < G[node].size(); ++ i) {
        int u = G[node][i].first, c = G[node][i].second;

        if (f[u] == false) {
            d[u] = (c < t) + d[node];
            DFS(u, c);
        }
    }

    return;
}

int main() {
    std :: ios_base :: sync_with_stdio(false);
    std :: cin.tie(nullptr);
    
    int tc;
    
    std :: cin >> tc;
    
    while (tc --) {
        std :: cin >> n;
    
        for (int i = 1, u, v; i < n; ++ i) {
            std :: cin >> u >> v;
    
            G[u].push_back({v, i});
            G[v].push_back({u, i});
        }
        
        for (int i = 1; i <= n; ++ i)
            f[i] = false;
    
        d[1] = 0;
        DFS(1, n);
    
        int Max = 0;
    
        for (int i = 1; i <= n; ++ i)
            Max = std :: max(Max, d[i]);
    
        std :: cout << Max << "\n";
        
        for (int i = 1; i <= n; ++ i)
            G[i].clear();
    }

    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Since $$$b_i \le n$$$ and $$$b_j \le n$$$, $$$b_i+b_j = a_i \cdot a_j \le 2 \cdot n$$$. Therefore, $$$\min(a_i,a_j) \le \sqrt{2 \cdot n}$$$.

Let $$$lim=\sqrt{2 \cdot n}$$$ and $$$fr[a_i][b_i]$$$ be the number of pairs $$$(a_i,b_i)$$$ from the input such that $$$a_i \le lim$$$.

A pair $$$(i,j)$$$ is good if it satisfies $$$a_i \cdot a_j=b_i+b_j$$$.

Firstly, we'll count the number of good pairs $$$(i,j)$$$ such that $$$a_i=a_j$$$. Since $$$min(a_i,a_j) \le lim$$$, we can see that $$$a_i=a_j \le lim$$$.

This sum can be written as:

The remaining good pairs will have $$$a_i \neq a_j$$$, and instead of counting the pairs which have $$$i \lt j$$$, we can count the pairs which have $$$a_i \gt a_j$$$.

Since $$$a_j=min(a_i,a_j)$$$, we can say that $$$a_j \le lim$$$.

Substituting $$$a_j$$$ for $$$j$$$, this second sum can be written as:

Since we've already established that $$$j \le lim = \sqrt{2 \cdot n}$$$, calculating this sum takes $$$O(n\sqrt{n})$$$ time.

Be especially careful when calculating these sums, as $$$a_i \cdot a_i - b_i$$$ and $$$a_i \cdot j-b_i$$$ can end up being either negative or greater than $$$n$$$.

Time complexity per testcase: $$$O(n \sqrt n)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=2e5+5,SQRMAX=635,MOD=1e9+7;

int fr[SQRMAX][NMAX];
ll a[NMAX],b[NMAX];
void tc(){
    ll n,ans=0;
    cin>>n;
    ll lim=sqrt(n*2);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    for(ll i=0;i<n;i++){
        cin>>b[i];
        if(a[i]<=lim)
            fr[a[i]][b[i]]++;
    }
    for(ll i=0;i<n;i++){
        if(a[i]<=lim){
            if(a[i]*a[i]-b[i]>=1 && a[i]*a[i]-b[i]<=n)
                ans+=fr[a[i]][a[i]*a[i]-b[i]];
        }
    }
    for(ll i=2;i<=lim;i+=2)
        ans-=fr[i][i*i/2];
    ans/=2;

    for(ll i=0;i<n;i++){
        for(ll j=1;j<=lim && j<a[i] && j*a[i]<=2*n;j++){
            if(j*a[i]-b[i]>=1 && j*a[i]-b[i]<=n)
                ans+=fr[j][j*a[i]-b[i]];
        }
    }
    for(ll i=0;i<n;i++){
        if(a[i]<=lim)
            fr[a[i]][b[i]]=0;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
        tc();
    return 0;
}

for _ in range(int(input())):
    n = int(input())
    
    ta = list(map(int, input().split()))
    tb = list(map(int, input().split()))
    
    a = [(x, y) for x, y in zip(ta, tb)]
    a.sort()
    
    cnt = [0] * (2 * n + 1)
    pr = 0
    ans = 0
    
    for i in range(n):
        if pr != a[i][0]:
            pr = a[i][0]
            
            if pr * pr > 2 * n:
                break
                
            cnt = [0] * (2 * n + 1)
            for j in range(i + 1, n):
                t = a[i][0] * a[j][0] - a[j][1]
                if t >= 0 and t <= 2 * n:
                    cnt[t] += 1
        
        ans += cnt[a[i][1]]
        
        if i + 1 < n:
            t = a[i][0] * a[i + 1][0] - a[i + 1][1]
            if t >= 0 and t <= 2 * n:
                cnt[t] -= 1
    
    print(ans)

Good problem

Ok problem

Bad problem

Didn't solve it, idk

First and foremost, the number of regular bracket strings of length $$$2 \cdot n$$$ is equal to $$$C_n=\frac{1}{n+1}\binom{2n}{n}$$$.

Secondly, for a bracket string $$$\overline{s_1s_2 \ldots s_k}$$$, let:

A bracket string $$$\overline{s_1s_2 \ldots s_k}$$$ is a regular bracket string if both of the following statements are true:

1. $$$\Delta_k=0$$$

2. $$$\Delta_i \ge 0, i=\overline{1,k}$$$

From now on we'll call a set of indices $$$i_1 < i_2 < \ldots < i_k$$$ a group if $$$\overline{s_{i_1}s_{i_2}\ldots s_{i_k}}$$$ must be an RBS.

There are two main cases to consider, both of which can be proven with the aforementioned conditions for a string to be an RBS:

By taking both of these cases into account, we can conclude that all indices $$$i_k$$$ covered by the same subset of intervals are part of the same group.

Finding the subset of intervals which cover a certain index $$$i$$$ can be implemented using difference arrays and xor hashing.

Time complexity: $$$O(maxn \cdot log(mod))$$$ for precomputing every $$$C_n$$$, and $$$O(k\cdot log(k))$$$ per test case.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int NMAX=3e5+5, MOD=998244353;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<ll> rnd(0,LLONG_MAX);

ll fact[NMAX], invfact[NMAX], C[NMAX];

ll binPow(ll x, ll y){
    ll ans=1;
    for(;y ;y>>=1, x = x*x%MOD)
        if(y&1)
            ans = ans*x%MOD;
    return ans;
}
map<ll,ll> diff,freq;
void add_interval(ll l, ll r){
    ll Hash = rnd(gen);
    diff[l] ^= Hash, diff[r+1] ^= Hash;
}
void tc(){
    ll n,k;
    cin>>n>>k;
    diff.clear(), freq.clear();
    add_interval(1,n); /// the initial string must be an RBS

    for(ll i=0;i<k;i++){
        ll l,r;
        cin>>l>>r;
        add_interval(l,r);
    }
    ll Hash = diff[1];

    for(map<ll,ll> :: iterator it=next(diff.begin()); it!=diff.end(); it++){
        freq[Hash] += it->first - prev(it)->first;
        Hash ^= it->second;
    }

    ll ans=1;

    for(const auto& it : freq)
        ans=ans*C[it.second]%MOD;

    cout<<ans<<'\n';
}

int main()
{
    fact[0] = invfact[0] = 1;
    for(ll i=1; i<NMAX; i++){
        fact[i] = fact[i-1] * i % MOD;
        invfact[i] = binPow(fact[i], MOD - 2);
    }

    for(ll i=0; i*2<NMAX; i++) C[i*2] = fact[i*2] * invfact[i] % MOD * invfact[i+1] % MOD;

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
        tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Disclaimer: I ( tibinyte ) wanted to cut $$$O(n \sqrt{n})$$$ memory because I thought that setting 1024 MB memory limit would spoil the solution. So only blame me for this.

We will do a complementary problem which is finding the minimum loss of a coloring. The initial cost is the maximum possible cost, $$$n \cdot (n+1)$$$.

If we analyze how good a bipartite coloring of the given tree is we can note that $$$loss \le 2 \cdot n$$$

Now suppose the tree has a connected component of size $$$k$$$. We can note that in such a coloring $$$loss \ge \frac{k \cdot (k+1)}{2}$$$

By the $$$2$$$ claims above, we can note that in an optimal coloring, the maximum size $$$k$$$ of a connected component respects $$$\frac{k \cdot (k+1)}{2} \le 2 \cdot n$$$. Thus we can safely say $$$k \le \sqrt{4 \cdot n}$$$.

Now let $$$dp_{i,j,color}$$$ be the minimum loss if we color the subtree of $$$i$$$ and the connected component of vertex $$$i$$$ has size $$$j$$$. We can calculate this in a knapsack style by adding subtrees successively. The computation takes $$$O(n \cdot \sqrt{n})$$$ if we use the $$$7$$$-th trick from this blog.

Now we are only left to optimize memory, since now it's $$$O(n \cdot \sqrt{n})$$$. We can directly apply this to get linear memory.

However, the bound of $$$k \le \sqrt{4 \cdot n}$$$ is overestimated, for $$$n=200000$$$ it can be proven that the worst case for $$$k$$$ is $$$258$$$.

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int lim = 893;
const int inf = 1e16;

struct dp_state
{
    vector<int> a;
    vector<int> b;
    void init()
    {
        a.resize(lim + 1, inf);
        b.resize(lim + 1, inf);
        a[1] = 1;
        b[1] = 2;
    }
};

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        vector<vector<int>> g(n + 1);
        vector<int> sz(n + 1);

        for (int i = 1; i < n; ++i)
        {
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x);
        }

        function<int(int, int)> shuffle_kids = [&](int node, int parent)
        {
            int sz = 1;
            pair<int, int> best;
            for (int i = 0; i < (int)g[node].size(); ++i)
            {
                if (g[node][i] != parent)
                {
                    int sz2 = shuffle_kids(g[node][i], node);

                    best = max(best, {sz2, i});

                    sz += sz2;
                }
            }
            if (!g[node].empty())
            {
                swap(g[node][0], g[node][best.second]);
            }
            return sz;
        };
        shuffle_kids(1, 0);

        vector<vector<int>> merged(2 * lim + 1, vector<int>(2, inf));

        function<dp_state(int, int)> dfs = [&](int node, int parent)
        {
            dp_state dp;
            sz[node] = 1;
            bool hasinit = false;
            for (auto i : g[node])
            {
                if (i != parent)
                {
                    dp_state qui = dfs(i, node);
                    if (!hasinit)
                    {
                        dp.init();
                        hasinit = true;
                    }
                    for (int j = 0; j <= min(sz[node], lim) + min(sz[i], lim); ++j)
                    {
                        merged[j][0] = merged[j][1] = inf;
                    }
                    for (int k = 1; k <= min(sz[node], lim); ++k)
                    {
                        for (int l = 1; l <= min(sz[i], lim); ++l)
                        {
                            merged[k][0] = min(merged[k][0], dp.a[k] + qui.b[l]);
                            merged[k][1] = min(merged[k][1], dp.b[k] + qui.a[l]);
                            merged[k + l][0] = min(merged[k + l][0], dp.a[k] + qui.a[l] + k * l);
                            merged[k + l][1] = min(merged[k + l][1], dp.b[k] + qui.b[l] + k * l * 2);
                        }
                    }
                    sz[node] += sz[i];
                    for (int k = 1; k <= min(sz[node], lim); ++k)
                    {
                        dp.a[k] = merged[k][0];
                        dp.b[k] = merged[k][1];
                    }
                }
            }
            if (!hasinit)
            {
                dp.init();
                hasinit = true;
            }
            return dp;
        };
        dp_state dp = dfs(1, 0);
        int ans = inf;
        for (int i = 1; i <= lim; ++i)
        {
            ans = min(ans, dp.a[i]);
            ans = min(ans, dp.b[i]);
        }
        cout << n * (n + 1) - ans << '\n';
    }
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

First of all, we notice that if some element moves left, it will never move right.

Obviously, if an element moves right, it will never move left since it will continue to move right until it reaches its final position.

By the $$$2$$$ claims above, we conclude that left and right movers are distinct.

Now suppose we swap indicies $$$i$$$ and $$$j$$$ and note that such swap kills $$$2 \cdot (j-i) - 1$$$ inversions and the left mover $$$j$$$ moves $$$j-i$$$ steps.

Now the magic is that if we let $$$s$$$ be the sum over $$$2 \cdot (i-p_i)$$$ for all left movers we have $$$s - ans = inversions$$$, thus our answer is just $$$s-inversions$$$.

Now to handle the data structure part, we just need to be able to calculate inversions while being able to perform point updates. There are many ways to do this, for example for using a fenwick tree and a bitwise trie/ordered_set in $$$O(nlog^2n)$$$.

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

typedef long long ll;

/*               .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

struct bit
{
  int n;
  vector<ordered_set> lesgo;
  void resize(int _n)
  {
    n = _n;
    lesgo = vector<ordered_set>(n + 1);
  }
  void update(int pos, int val, int sign)
  {
    for (int i = pos; i <= n; i += i & (-i))
    {
      if (sign == -1)
      {
        lesgo[i].erase(val);
      }
      if (sign == 1)
      {
        lesgo[i].insert(val);
      }
    }
  }
  int query_smaller(int pos, int val)
  {
    int ans = 0;
    for (int i = pos; i; i -= i & (-i))
    {
      ans += lesgo[i].order_of_key(val);
    }
    return ans;
  }
  int query_greater(int pos, int val)
  {

    int ans = 0;
    for (int i = pos; i; i -= i & (-i))
    {
      int sz = lesgo[i].size();
      ans += sz - lesgo[i].order_of_key(val + 1);
    }
    return ans;
  }
  int query_smaller(int st, int dr, int val)
  {
    return query_smaller(dr, val) - query_smaller(st - 1, val);
  }
  int query_greater(int st, int dr, int val)
  {
    return query_greater(dr, val) - query_greater(st - 1, val);
  }
};

int32_t main()
{
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i)
  {
    cin >> a[i];
  }
  bit lesgo;
  lesgo.resize(n);
  for (int i = 1; i <= n; ++i)
  {
    lesgo.update(i, a[i], 1);
  }

  ll inv = 0;

  for (int i = 1; i <= n; ++i)
  {
    inv += lesgo.query_greater(1, i, a[i]);
  }

  ll sum = 0;

  for (int i = 1; i <= n; ++i)
  {
    sum += max(a[i] - i, 0);
  }

  while (q--)
  {
    int x, y;
    cin >> x >> y;
    if (x != y)
    {
      lesgo.update(x, a[x], -1);
      lesgo.update(y, a[y], -1);
      sum -= max(a[x] - x, 0);
      sum -= max(a[y] - y, 0);
      if (x + 1 <= y - 1)
      {
        int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]);
        int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]);
        inv += 2 * (y - x - 1 - lesgo1 - lesgo2);
      }

      if (a[x] > a[y])
      {
        inv--;
      }
      else
      {
        inv++;
      }

      swap(a[x], a[y]);
      sum += max(a[x] - x, 0);
      sum += max(a[y] - y, 0);
      lesgo.update(x, a[x], 1);
      lesgo.update(y, a[y], 1);
    }
    cout << sum + sum - inv << '\n';
  }
}

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random(int st, int dr)
{
  uniform_int_distribution<int> dist(st, dr);
  return dist(rng);
}

typedef long long ll;

/*               .___                 __                 __           .__
  ____  ____   __| _/____     _______/  |______ ________/  |_  ______ |  |__   ___________   ____
_/ ___\/  _ \ / __ |/ __ \   /  ___/\   __\__  \\_  __ \   __\/  ___/ |  |  \_/ __ \_  __ \_/ __ \
\  \__(  <_> ) /_/ \  ___/   \___ \  |  |  / __ \|  | \/|  |  \___ \  |   Y  \  ___/|  | \/\  ___/
 \___  >____/\____ |\___  > /____  > |__| (____  /__|   |__| /____  > |___|  /\___  >__|    \___  >
     \/           \/    \/       \/            \/                 \/       \/     \/            \/
*/

struct decomp
{
  vector<int> a;
  vector<pair<int, int>> buckets;
  vector<int> sp;
  vector<int> spbucket;
  vector<int> wh;
  const int sz = 400;
  void resize(int n)
  {
    a = vector<int>(n + 1);
    sp = vector<int>(n + 1);
    wh = vector<int>(n + 1);
    for (int i = 1; i <= n; i += sz)
    {
      int st = i;
      int dr = min(n, st + sz - 1);
      for (int j = st; j <= dr; ++j)
      {
        wh[j] = (int)buckets.size();
      }
      buckets.push_back({st, dr});
      spbucket.push_back(0);
    }
  }
  void update(int pos, int x)
  {
    a[pos] += x;
    int qui = wh[pos];
    sp[buckets[qui].first] = a[buckets[qui].first];
    for (int i = buckets[qui].first + 1; i <= buckets[qui].second; ++i)
    {
      sp[i] = sp[i - 1] + a[i];
    }
    spbucket[0] = sp[buckets[0].second];
    for (int i = 1; i < (int)buckets.size(); ++i)
    {
      spbucket[i] = spbucket[i - 1] + sp[buckets[i].second];
    }
  }
  int query(int pos)
  {
    int qui = wh[pos];
    int ans = sp[pos];
    if (qui)
    {
      ans += spbucket[qui - 1];
    }
    return ans;
  }
};

struct geralt
{
  vector<int> a;
  vector<decomp> lesgo;
  vector<pair<int, int>> buckets;
  vector<int> wh;
  const int sz = 3000;
  void resize(int n)
  {
    a = vector<int>(n + 1);
    wh = vector<int>(n + 1);
    for (int i = 1; i <= n; i += sz)
    {
      int st = i;
      int dr = min(n, st + sz - 1);
      for (int j = st; j <= dr; ++j)
      {
        wh[j] = (int)buckets.size();
      }
      buckets.push_back({st, dr});
      lesgo.push_back({});
      lesgo.back().resize(n);
    }
  }
  void update(int pos, int val)
  {
    int qui = wh[pos];
    if (a[pos] != 0)
    {
      lesgo[qui].update(a[pos], -1);
    }
    a[pos] = val;
    lesgo[qui].update(a[pos], 1);
  }
  int query_brute(int st, int dr, int val)
  {
    int ans = 0;
    for (int i = st; i <= dr; ++i)
    {
      if (a[i] <= val)
      {
        ans++;
      }
    }
    return ans;
  }
  int query_smaller(int st, int dr, int val) // number of values <= val in st...dr
  {
    if (wh[st] == wh[dr])
    {
      return query_brute(st, dr, val);
    }
    int qui1 = wh[st], qui2 = wh[dr];
    int ans = query_brute(st, buckets[qui1].second, val) + query_brute(buckets[qui2].first, dr, val);
    qui1++;
    qui2--;
    for (int i = qui1; i <= qui2; ++i)
    {
      ans += lesgo[i].query(val);
    }
    return ans;
  }
  int query_greater(int st, int dr, int val) // number of values > val in st...dr
  {
    return (dr - st + 1) - query_smaller(st, dr, val);
  }
};

int32_t main()
{
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i)
  {
    cin >> a[i];
  }

  geralt lesgo;
  lesgo.resize(n);

  ll inv = 0;

  for (int i = 1; i <= n; ++i)
  {
    lesgo.update(i, a[i]);
    inv += lesgo.query_greater(1, i, a[i]);
  }

  ll sum = 0;

  for (int i = 1; i <= n; ++i)
  {
    sum += max(a[i] - i, 0);
  }

  while (q--)
  {
    int x, y;
    cin >> x >> y;
    if (x != y)
    {
      sum -= max(a[x] - x, 0);
      sum -= max(a[y] - y, 0);
      if (x + 1 <= y - 1)
      {
        int lesgo1 = lesgo.query_smaller(x + 1, y - 1, a[x]);
        int lesgo2 = lesgo.query_greater(x + 1, y - 1, a[y]);
        inv += 2 * (y - x - 1 - lesgo1 - lesgo2);
      }

      if (a[x] > a[y])
      {
        inv--;
      }
      else
      {
        inv++;
      }

      swap(a[x], a[y]);
      sum += max(a[x] - x, 0);
      sum += max(a[y] - y, 0);
      lesgo.update(x, a[x]);
      lesgo.update(y, a[y]);
    }
    cout << sum + sum - inv << '\n';
  }
}

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

#define ll long long
#define ii pair<int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

struct FEN{ //we want to count the reverse
	int arr[500005];
	
	void update(int i,int k){
		i=500005-i;
		
		while (i<500005){
			arr[i]+=k;
			i+=i&-i;
		}
	}
	
	int query(int i){
		i=500005-i;
		
		int res=0;
		while (i){
			res+=arr[i];
			i-=i&-i;
		}
		return res;
	}
} fen;

int n,q;
int arr[500005];
long long ans[50005];

void dnc(int l,int r,vector<i4> upd,vector<i4> que){
	vector<i4> updl,updr;
	vector<i4> quel,quer;
	
	int m=l+r>>1;
	
	for (auto [a,b,c,d]:upd){
		if (c<=m) updl.pub({a,b,c,d});
		else updr.pub({a,b,c,d});
	}
	
	for (auto [a,b,c,d]:que){
		if (c<=m) quel.pub({a,b,c,d});
		else quer.pub({a,b,c,d});
	}
	
	int i=0;
	for (auto it:quer){
		while (i<sz(updl) && get<0>(updl[i])<get<0>(it)){
			fen.update(get<1>(updl[i]),get<3>(updl[i]));
			i++;
		}
		
		ans[get<2>(it)]+=fen.query(get<1>(it))*get<3>(it);
	}
	while (i){
		i--;
		fen.update(get<1>(updl[i]),-get<3>(updl[i]));
	}
	
	if (l!=m) dnc(l,m,updl,quel);
	if (m+1!=r) dnc(m+1,r,updr,quer);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n>>q;
	rep(x,1,n+1) cin>>arr[x];
	
	vector<i4> upd,que;
	
	rep(x,1,n+1) upd.pub({x,arr[x],-1,1});
	rep(x,1,n+1) que.pub({x,arr[x],0,-1});
	rep(x,1,n+1) ans[0]+=abs(x-arr[x]);
	
	rep(x,1,q+1){
		int a,b;
		cin>>a>>b;
		
		if (a==b) continue;
		if (arr[a]<arr[b]) ans[x]--;
		else ans[x]++;
		
		upd.pub({a,arr[a],x-1,-1});
		upd.pub({b,arr[b],x-1,-1});
		ans[x]-=abs(a-arr[a])+abs(b-arr[b]);
		
		swap(arr[a],arr[b]);
		
		upd.pub({a,arr[a],x,1});
		upd.pub({b,arr[b],x,1});
		ans[x]+=abs(a-arr[a])+abs(b-arr[b]);
		
		que.pub({b,arr[b],x,-2});
		que.pub({b,arr[a],x,2});
		que.pub({a,arr[b],x,2});
		que.pub({a,arr[a],x,-2});
		
	}
	
	sort(all(upd)),sort(all(que));
	
	dnc(-1,q,upd,que);
	
	rep(x,1,q+1) ans[x]+=ans[x-1];
	rep(x,1,q+1) cout<<ans[x]<<" "; cout<<endl;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$dp_i$$$ be the maximum sum of costs of activated points that are $$$< i$$$ over all states that has point $$$i$$$ activated.

When we transition from $$$dp_i$$$ to $$$dp_j$$$, we need to add the cost contributed by point $$$i$$$. The number of ranges where point $$$i$$$ is the largest coordinate within it are the ranges $$$[l,r]$$$ which satisfy $$$l \leq i \leq r < j$$$. So we have $$$dp_j = \max\limits_{i < j}(dp_i + p_i \cdot S_{i,j})$$$ where $$$S_{i,j}$$$ is the number of ranges $$$[l,r]$$$ which satisfy $$$l \leq i \leq r < j$$$. Now, we note that $$$S_{i,j} z$$$

With some work, we can get calculate this $$$dp$$$ in $$$O(n^2)$$$. But this will be too slow, let's try to speed this up.

Let us define $$$dp_{i,j} = \max\limits_{k \leq i}(dp_k + p_k \cdot S_{k,j})$$$. We have $$$dp_{j-1,j}=dp_j$$$. Our goal is to go from (implictly) storing $$$dp_{i,i+1},dp_{i,i+2},\ldots,dp_{i,n}$$$ to $$$dp_{i+1,i+2},dp_{i+1,i+3},\ldots,dp_{i+1,n}$$$. As $$$dp_i + p_i \cdot S_{i,j}$$$ looks like a linear function w.r.t. $$$S_{i,j}$$$, we can try to use convex hull data structures to maintain it.

Let's figure out how $$$S_{i+1,j}$$$ relates to $$$S_{i,j}$$$. We need to subtract the number of ranges with $$$r=i$$$ and add the number of ranges with $$$l=i+1$$$ and $$$r < j$$$. This corresponds to $$$S_{i,*}$$$ and $$$S_{i+1,*}$$$ differing by amortized $$$O(1)$$$ suffix increment updates. Also, note that $$$S_{i,*}$$$ is non-decreasing.

So we want to support the following data structure: Initially we have an arrays $$$A$$$ and $$$X$$$ that are both initially $$$0$$$. Handle the following updates:

• 1 m c $$$A_i \gets \max(A_i,m \cdot X_i + c)$$$ for all $$$i$$$
• 2 j k $$$X_i \gets X_i + k$$$ for all $$$j \leq i$$$. It is guaranteed that $$$X$$$ will always be non-decreasing.
• 3 i find $$$A_i$$$

This can be maintained in a lichao tree in $$$O(log ^2)$$$ time. In each lichao node, we need to store $$$s,m,e$$$, the start, middle and end indices and their corresponding $$$X$$$ values $$$X_s,X_m,X_e$$$ respectively. This way, we can support operations $$$1$$$ and $$$3$$$ already.

To support operation $$$2$$$, note that in a lichao tree, you can use $$$O(log^2)$$$ time to push down all lines that covers a certain point (refer to https://codeforces.com/blog/entry/86731). This way, all lines in the li chao tree are in $$$[1,j)$$$ or $$$[j,n]$$$, so you can do lazy updates on both the coordinates of the lines and the $$$X$$$ values.

The time complexity is $$$O(n \log^2)$$$.

There is another solution that works in $$$O(m \log^3)$$$ that we are unable to optimize further yet. Let us flip the array so that the condition is on the activated point with the smallest coordinate. Then we have $$$dp_j = \max\limits_{i < j}(dp_i + p_j \cdot S_{i,j})$$$ where $$$S_{i,j}$$$ counts the number of ranges $$$[l,r]$$$ such that $$$i< l \leq j \leq r$$$.

Now, we want to store the linear function $$$dp_i + x \cdot S_{i,j}$$$ in some sort of data structure so that we can evaluate the maximum value with $$$x=p_j$$$. Unfortunately, the value of $$$S_{i,j}$$$ can change by suffix additions, similar to above.

But since $$$S_{i,j}$$$ is non-increasing here, that means the optimal $$$i$$$ that maximizes $$$dp_i + x \cdot S_{i,j}$$$ decreases when $$$x$$$ increases. That is, for $$$l_1 \leq r_1< l_2 \leq r_2$$$ and we have two data structures that can get the maximum $$$f_j(x)=dp_i+x \cdot S_{i,j}$$$ for $$$l_j \leq i \leq r_j$$$ respectively. We can combine these $$$2$$$ data structures to make it for $$$[l_1,r_1] \cup [l_2,r_2]$$$ by binary searching the point $$$X$$$ where for all $$$x \leq X$$$, $$$f_1(x) \leq f_2(x)$$$ and for all $$$X \leq x,f_1(x) \geq f_2(x)$$$. Since querying this data structure takes $$$O(\log n)$$$, it takes $$$O(\log ^2)$$$ time to combine two such data structures. If we use a segment tree, we only need to rebuild $$$O(\log^3)$$$ different data structures (the rest can be handled using lazy tags), giving us a time complexity of $$$O(\log^3)$$$.

//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const ll INF=1e18;

struct line{
	ll m,c;
	
	line (ll _m,ll _c){
		m=_m,c=_c;
	}
	
	ll get(ll x){
		return m*x+c;
	}
};

struct node{
	int s,e,m;
	int vs=0,ve=0,vm=0;
	line val={0,-INF};
	int lazy=0;
	node *l,*r;
	
	node(int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void propo(){
		if (lazy==0) return;
		
		val.c-=val.m*lazy;
		vs+=lazy;
		ve+=lazy;
		vm+=lazy;
		
		if (s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
	}
	
	void update(int i){
		if (s==i) lazy++;
		else{
			if (val.c!=-INF){
				l->propo(),r->propo();
				l->update(val),r->update(val);
				val={0,-INF};
			}
			
			if (m<i) r->update(i);
			else l->update(i),r->update(m+1);
			
			l->propo(),r->propo();
			vs=l->vs,vm=l->ve,ve=r->ve;
		}
	}
	
	void update(line i){
		bool lo=i.get(vs)>val.get(vs);
		bool mi=i.get(vm)>val.get(vm);
		bool hi=i.get(ve)>val.get(ve);
		
		if (mi) swap(i,val);
		
		if (s==e || i.c==-INF || lo==hi) return;
		
		l->propo(),r->propo();
		if (lo!=mi) l->update(i);
		else r->update(i);
	}
	
	ii query(ll i){
		propo();
		
        if (s==e) return {val.get(vs),vs};
		else if (i<=m){
			auto temp=l->query(i);
			return {max(temp.fi,val.get(temp.se)),temp.se};
		}
		else{
			auto temp=r->query(i);
			return {max(temp.fi,val.get(temp.se)),temp.se};
		}
	}
} *root;

const int maxn = 1e6;
const int maxm = 1e6;

int n,m;
ii arr[maxn+1];
ii brr[maxm+1];

int ans[maxm+1];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	int TC;
	cin>>TC;
	while (TC--){
		cin>>n>>m;
		rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
		rep(x,1,m+1){
            cin>>brr[x].se;
            brr[x].fi = x;
        }
    
		sort(arr+1,arr+n+1);
		
		root=new node(0,m+1);
		root->update({0,0});
		
		int curr=1;
		rep(x,0,m+2){
			while (curr<=n && arr[curr].fi==x) root->update(arr[curr++].se+1);
			auto temp=root->query(x);
			root->update({brr[x].se,temp.fi-brr[x].se*temp.se});
		}
		
		cout<<root->query(m+1).fi<<endl;
	}
}

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<ll,ll>;
using tii = tuple<int,int,int>;

const int nmax = 5e5 + 5, qmax = 2e6 + 5;
const ll inf = 1e18 + 5; 

struct line {
  ll m = 0, b = -inf;
  ll operator()(const ll& x) const {
     return m * x + b;
  }
  bool operator ==(const line& x) const { return m == x.m && b == x.b; }
};

int M;

namespace AINT {
  struct Node {
    int vl = 0, vmid = 0, vr = 0;
    line val = line{0, -inf};
    Node() {;}
    void operator += (const int &x) { vl += x, vmid += x, vr += x; val.b -= val.m * x; }
  } aint[qmax * 4];
  int lazy[qmax * 4];
  
  void push(int node) {
    lazy[2 * node] += lazy[node];
    aint[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    aint[2 * node + 1] += lazy[node];
    lazy[node] = 0;
  }
  void pushline(line x, int node = 1, int cl = 0, int cr = M) {
    bool l = x(aint[node].vl) > aint[node].val(aint[node].vl), m = x(aint[node].vmid) > aint[node].val(aint[node].vmid), r = x(aint[node].vr) > aint[node].val(aint[node].vr);
    if(m) swap(x, aint[node].val);
    if(cl == cr || x == line() || l == r) return;
    
    int mid = cl + cr >> 1;
    push(node);
    if(m != l) pushline(x, 2 * node, cl, mid);
    else pushline(x, 2 * node + 1, mid + 1, cr);
    return;
  }
  void add(int l, int node = 1, int cl = 0, int cr = M) {
    if(cl >= l) {
      lazy[node]++;
      aint[node] += 1;
      return;
    }
    if(cr < l) return;
    int mid = cl + cr >> 1;
    
    push(node);
    
    pushline(aint[node].val, 2 * node, cl, mid);
    pushline(aint[node].val, 2 * node + 1, mid + 1, cr);
    aint[node].val = line{0, -inf};
    
    add(l, 2 * node, cl, mid);
    add(l, 2 * node + 1, mid + 1, cr);
    aint[node].vl = aint[2 * node].vl;
    aint[node].vmid = aint[2 * node].vr;
    aint[node].vr = aint[2 * node + 1].vr;
  }
  pii query(ll p, int node = 1, int cl = 0, int cr = M) {
    if(cl == cr) return pii{aint[node].val(aint[node].vl), aint[node].vl};
    int mid = cl + cr >> 1;
    push(node);
    auto [mxv, atrv] = p <= mid? query(p, 2 * node, cl, mid) : query(p, 2 * node + 1, mid + 1, cr);
    return pii{max(mxv, aint[node].val(atrv)), atrv};
  } 
  
  void init(int node = 1, int cl = 0, int cr = M) {
    aint[node] = Node();
    lazy[node] = 0;
    if(cl == cr) return;
    int mid = cl + cr >> 1;
    init(2 * node, cl, mid);
    init(2 * node + 1, mid + 1, cr);
    return;
  }
};

vector<int> atraddp[qmax];
ll val[qmax];

void testcase() {
  int n, m;
  cin >> n >> m;
  M = m + 2;
  for(int i = 0, l, r; i < n; i++) {
    cin >> l >> r;
    atraddp[l].emplace_back(r + 1);
  }
  for(int i = 1; i <= m; i++)
    cin >> val[i];
  
  AINT::init();
  AINT::pushline({0, 0});
  
  for(int i = 0; i < m + 2; i++) {
    for(auto x : atraddp[i])
      AINT::add(x);
    auto [a, b] = AINT::query(i);
    //cerr << a << ' ' << b << '\n';
    AINT::pushline({val[i], a - val[i] * b});
  }
  
  for(int i = 0; i < m + 2; i++)
    atraddp[i].clear();
  
  cout << AINT::query(m + 1).first << '\n';
}

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

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

Good problem

Ok problem

Bad problem

Didn't solve it, idk

First and foremost, it can be proven that $$$(a \oplus b) + (b \oplus c) + (a \oplus c)$$$ is always even, for all possible non-negative values of $$$a$$$, $$$b$$$ and $$$c$$$.

Therefore, if $$$n$$$ is even, one possible solution is $$$a=0$$$, $$$b=0$$$ and $$$c=\frac{n}{2}$$$. In this case, $$$(a \oplus b) + (b \oplus c) + (a \oplus c)= 0+\frac{n}{2}+\frac{n}{2}=n$$$. Otherwise, there are no solutions.

Time complexity per testcase: $$$O(1)$$$.

#include<bits/stdc++.h>

using namespace std;

void testcase(){
    int n;
    cin>>n;

    if(n%2==0)
        cout<<"0 "<<n/2<<' '<<n/2<<'\n';
    else
        cout<<"-1\n";
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--)
        testcase();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

This is actually the third iteration of the problem, which was suggested by antontrygubO_o.

The first iteration had $$$|a-b|+|b-c|+|a-c|=n$$$, and the second one had $$$gcd(a,b)+gcd(b,c)+gcd(a,c)=n$$$.

The general construction consists of a $$$2 \times 2$$$ checkerboard with a $$$1$$$-thick border. Here is the intended solution for $$$n=6$$$ and $$$m=8$$$:

Time complexity per testcase: $$$O(nm)$$$.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

void testcase(){
    ll n,m;
    cin>>n>>m;

    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cout<<((i%4<=1)!=(j%4<=1))<<" \n"[j==m];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--)
        testcase();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$p[x]$$$ be the position of $$$x$$$ in permutation $$$a$$$.

Since $$$MEX([a_{p[0]}])=1$$$, the only possible position of $$$0$$$ in permutation $$$b$$$ is exactly $$$p[0]$$$.

Without loss of generality, we will assume that $$$p[0] \lt p[1]$$$. For every interval $$$[l,r]$$$ ($$$l \le p[0] \lt p[1]\le r$$$), $$$MEX([b_l,\ldots,b_r])$$$ must be at least $$$2$$$. For every other interval, $$$MEX([b_l,\ldots,b_r])$$$ cannot exceed $$$2$$$. The only position for $$$1$$$ which satisfies both of these constraints is exactly $$$p[1]$$$.

Let's consider the current interval $$$[l,r]$$$ as being $$$[p[0],p[1]]$$$.

If $$$p[2] \in [l,r]$$$, we can say that, for every interval $$$[x,y]$$$ ($$$x \le l \lt r \le y$$$), $$$MEX([b_x,\ldots,b_y])$$$ must be at least $$$3$$$. Similarly, for every other interval, $$$MEX([b_x,\ldots,b_y])$$$ cannot exceed $$$3$$$. Both of these constraints are only met if $$$2$$$ occurs in permutation $$$b$$$ on some position $$$p \in [l,r]$$$. Since only $$$2$$$ positions are currently occupied in $$$[l,r]$$$, the total number of similar permutations will be multiplied by $$$(r-l+1)-2$$$.

Otherwise, $$$2$$$ can be placed in permutation $$$b$$$ only on $$$p[2]$$$. Additionally, the current interval will be "extended" to include $$$p[2]$$$, resuting in either $$$[p[2],r]$$$ or $$$[l,p[2]]$$$.

After processing $$$0,1, \ldots, k-2$$$ and $$$k-1$$$, the algorithm for processing $$$k$$$ is very similar to the one presented earlier. If $$$p[k] \in [l,r]$$$, the answer gets multiplied by $$$(r-l+1)-k$$$. Otherwise, the current interval is extended to include $$$p[k]$$$.

Time complexity per testcase: $$$O(n)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=1e5+5,MOD=1e9+7;
ll v[NMAX],pos[NMAX];
void tc(){
    ll n,l,r,ans=1;
    cin>>n;
    for(ll i=0;i<n;i++){
        cin>>v[i];
        pos[v[i]]=i;
    }
    l=r=pos[0];
    for(ll i=1;i<n;i++){
        if(pos[i]<l) l=pos[i];
        else if(pos[i]>r) r=pos[i];
        else ans=ans*(r-l+1-i)%MOD;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll t;
    cin>>t;
    while(t--)
        tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Lemma: An array $$$a_1,a_2,\ldots, a_n$$$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints:

• $$$n$$$ is even

• The maximum frequency of any element in the array is at most $$$\frac n2$$$.

Since the maximum frequency of a value for every subarray $$$[a_l,a_{l+1},\ldots,a_r]$$$ can be computed in $$$O(n^2)$$$, it is possible to precompute all subarrays which can be deleted via a sequence of operations.

Let $$$dp[i]$$$ be the maximum length of a final array consisting of $$$a_i$$$ and some subsequence from the first $$$i-1$$$ elements. Initially, $$$dp[i]$$$ is set to $$$1$$$ if the prefix $$$[a_1,a_2,\ldots, a_{i-1}]$$$ can be fully deleted. Otherwise, $$$dp[i]=0$$$.

For every pair of indices $$$i$$$ and $$$j$$$ ($$$1 \le j \lt i \le n, a_i=a_j$$$), if we can fully delete the subarray $$$[a_{j+1},a_{j+2},\ldots a_{i-1}]$$$, then we can append $$$a_i$$$ to any final array ending in $$$a_j$$$. Naturally, $$$dp[i]$$$ will be strictly greater than $$$dp[j]$$$. This gives us the following recurrence:

$$$dp[i]=\max_{j=1}^{i-1}(dp[j]>0 \text{ and } a_i=a_j \text{ and } [a_{j+1},a_{j+2},\ldots,a_{i-1}] \text{ is deletable}) \cdot (dp[j]+1)$$$

If we define a final array as a subsequence of equal elements from the array $$$a$$$, to which $$$a_{n+1}$$$ is forcefully appended, then the final answer can be written as $$$dp[n+1]-1$$$. Note that, when computing $$$dp[n+1]$$$, $$$a_j$$$ should not be compared to $$$a_{n+1}$$$.

Total time complexity per testcase: $$$O(n^2)$$$.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=5e3+5;
ll dp[NMAX],v[NMAX],fr[NMAX];
void testcase(){
    ll n,ans=0;
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>v[i];
        dp[i]=0;
    }
    for(ll i=0;i<=n;i++){

        if(i && dp[i]==0) continue;
        ll frmax=0;
        for(int j=1;j<=n;j++) fr[j]=0;

        for(int j=i+1;j<=n;j++){
            if((j-i)%2 && frmax<=(j-i)/2 && (i==0 || v[i]==v[j]))
                dp[j]=max(dp[j],dp[i]+1);
            frmax=max(frmax,++fr[v[j]]);
        }
    }

    ll frmax=0;
    for(int j=1;j<=n;j++) fr[j]=0;

    for(int i=n;i>=0;i--){
        if((n-i)%2==0 && frmax<=(n-i)/2) ans=max(ans,dp[i]);
        frmax=max(frmax,++fr[v[i]]);
    }
    cout<<ans<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--)
        testcase();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

We can see that in the final multiset, each number $$$A_i$$$ from the initial multiset will be assigned to a subset of values $$$x_1, x_2,....,x_k$$$ such that their product is $$$A_i$$$. Every such multiset can be created. Also let $$$vmax$$$ be the maximum value in the initial multiset.

Consider iterating through the minimum value. To get the best maximum value that has this minimum we fixed, one can use dynamic programming $$$dp[i][j] = $$$the best possible maximum if we had number $$$i$$$ and the minimum value in the product is $$$j$$$, $$$j$$$ is a divisor of $$$i$$$. This dp can be calculated in $$$O(vmax \cdot log^2(vmax))$$$ for all values. We can also process all updates when incrementing the minimum and keeping the result with a total effort of $$$O(vmax \cdot log^2(vmax))$$$. Thus we have a total time complexity of $$$O(vmax \cdot log^2(vmax))$$$. However, this ( we hope ) won't pass.

Here is a way more elegant solution ( thanks to valeriu ):

To get things straight, we observe that when we decompose a number, we just actually write it as a product of numbers. We still consider fixing the minimum value used in our multiset, call it $$$L$$$. We will further consider that we iterate $$$L$$$ from the greatest possible value (i.e. $$$vmax$$$) to $$$1$$$, and as such, we try at each iteration to calculate the minimum possible value which will appear in any decomposition as the maximum value in said decomposition.

We shall now retain for each element the minimal maximum value in a decomposition where the minimum of that decomposition is $$$L$$$, let's say for element $$$i$$$, this value will be stored in $$$dp[i]$$$. Naturally, after calculating this value for every number, we now try to tweak the calculated values as to match the fact that, after this iteration concluded, we will decrease $$$L$$$. For further simplicity, we denote $$$L' = L - 1$$$.

So, we changed the minimum value allowed. What changes now? Well, it is easy to see that any element that is not divisible by $$$L'$$$ won't be affected by this modification, as much as it is impossible to include $$$L'$$$ in any decomposition of said number. So it remains to modify the multiples of $$$L'$$$. Let's take a such number, $$$M$$$. How can we modify $$$dp[M]$$$? Well, we can include $$$L'$$$ in the decomposition as many times as we want, and then when we decide to stop including it, we remain with a number which needs to be further decomposed. The attributed maximum of this value should already be calculated, so we can consider it as a new candidate for the update of $$$dp[M]$$$. This idea could be implemented simpler by going through multiples of $$$L'$$$, and for an element, updating $$$dp[i]$$$ with $$$dp[i / L']$$$ (by taking the minimum of either)

We now need for each iteration to keep track of the attributed maximums of each element that actually appears in our initial list. This can be done by keeping a frequency of all these elements, and after all updates, taking the (already known) maximum of the previous iteration and decreasing it until we find another element that actually appears in our set (this can be verified by simply checking the frequency). This is correct, as much as all the values gradually decrease as $$$L$$$ decreases, so their maximum would have to decrease as well.

Final time complexity: $$$O(vmax * log(vmax))$$$

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int nmax = 5e6 + 5;
int appear[nmax];
int mxval[nmax];
int toggle[nmax];

int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, mn = nmax, mx = 0;
        cin >> n >> m;
        for (int i = 0; i <= m; ++i)
        {
            appear[i] = toggle[i] = mxval[i] = 0;
        }
        for (int i = 0, x; i < n; i++)
        {
            cin >> x;
            appear[x] = 1;
            toggle[x] = 1;
            mn = min(mn, x);
            mx = max(mx, x);
        }
        for (int i = 0; i <= mx; i++)
        {
            mxval[i] = i;
        }
        int ptr = mx, smax = mx - mn;
        for (int i = mx; i >= 1; i--)
        {
            for (ll j = (ll)i * i; j <= mx; j += i)
            {
                if (appear[j])
                    toggle[mxval[j]]--;
                mxval[j] = min(mxval[j], mxval[j / i]);
                if (appear[j])
                    toggle[mxval[j]]++;
            }
            while (toggle[ptr] == 0)
                ptr--;
            if (i <= mn)
                smax = min(smax, ptr - i);
        }
        cout << smax << '\n';
    }
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

If $$$n$$$ is odd, let $$$k=\frac{n+1}{2}$$$ be the width of the last block. It is possible to create a square of side length $$$k$$$ using every block as follows:

• Line $$$1$$$ contains a $$$1 \times k$$$ block;
• Line $$$2$$$ contains a $$$1 \times 1$$$ block and a $$$1 \times (k-1)$$$ block;
• Line $$$3$$$ contains a $$$1 \times 2$$$ block and a $$$1 \times (k-2)$$$ block;
• $$$\ldots$$$
• Line $$$i$$$ contains a $$$1 \times (i-1)$$$ block and a $$$1 \times (k-i+1)$$$ block;
• $$$\ldots$$$
• Line $$$k$$$ contains a $$$1 \times (k-1)$$$ block and a $$$1 \times 1$$$ block.

Since the area of this square is $$$k^2$$$, and the $$$n+1$$$-th block has a width of $$$k$$$ tiles, the total area of the first $$$n+1$$$ blocks is equal to $$$k^2+k \lt (k+1)^2$$$. Therefore, the answer for $$$n+1$$$ is also $$$k$$$.

In conclusion, the answer for each testcase is $$$\lfloor \frac{n+1}{2} \rfloor$$$.

Time complexity per testcase: $$$O(1)$$$.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
void testcase(){
    ll n;
    cin>>n;
    cout<<(n+1)/2<<'\n';
}
int main()
{
    ll t; cin>>t; while(t--)
       testcase();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

In a diverse string, there are at most $$$10$$$ distinct characters: '0', '1', $$$\ldots$$$, '9'. Therefore, each of these characters can appear at most $$$10$$$ times in a diverse string.

With all this in mind, the maximum possible length of a diverse string is $$$10^2=100$$$. To solve this problem, we only need to check whether each substring of length $$$l \le 100$$$ is diverse.

Time complexity per testcase: $$$O(n \cdot 10^2)$$$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
void tc(){
    ll n;
    string s;
    cin>>n>>s;
    ll ans=0;

    for(ll i=0;i<s.size();i++){

        int fr[10]{}, distinct=0, max_freq=0;

        for(ll j=i;j<s.size() && (++fr[s[j]-'0'])<=10;j++){

            max_freq=max(max_freq,fr[s[j]-'0']);
            if(fr[s[j]-'0']==1) distinct++;

            if(distinct>=max_freq) ans++;
        }
    }
    cout<<ans<<'\n';
}
int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll t; cin>>t; while(t--) tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let's consider the prefix sum array $$$s=[a_1,a_1+a_2,\ldots,a_1+a_2+\ldots+a_n]$$$.

For every index $$$i$$$ such that $$$a_i=0$$$, if we change the value of $$$a_i$$$ to $$$x$$$, then every element from the suffix $$$[s_i,s_{i+1},\ldots,s_n]$$$ will be increased by $$$x$$$. Therefore, if $$$a_{i_1}=a_{i_2}=\ldots=a_{i_k}=0$$$, we'll partition array $$$s$$$ into multiple subarrays:

• $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$;
• $$$[s_{i_1},s_{i_1+1},\ldots,s_{i_2-1}]$$$;
• $$$[s_{i_2},s_{i_2+1},\ldots,s_{i_3-1}]$$$;
• $$$\ldots$$$
• $$$[s_{i_k},s_{i_{k+1}},\ldots,s_n]$$$;

Since none of the elements from the first subarray can be changed, it will contribute with the number of occurences of $$$0$$$ in $$$[s_1,s_2,\ldots,s_{i_1-1}]$$$ towards the final answer.

For each of the other subarrays $$$[s_l,s_{l+1},\ldots,s_r]$$$, let $$$x$$$ be the most frequent element in the subarray, appearing $$$fr[x]$$$ times. Since $$$a_l=0$$$, we can change the value of $$$a_l$$$ to $$$-x$$$. In this case, every $$$x$$$ in this subarray will become equal to $$$0$$$, and our current subarray will contribute with $$$fr[x]$$$ towards the final answer.

Time complexity per testcase: $$$O(NlogN)$$$

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;

ll a[MAXN];
map<ll,ll> freq;

void tc(){
    ll n;
    cin>>n;
    ll maxfr=0,current_sum=0,ans=0;
    bool found_wildcard=0;
    freq.clear();
    for(ll i=0;i<n;i++){
        cin>>a[i];

        if(a[i]==0){

            if(found_wildcard) ans+=maxfr;
            else ans+=freq[0];

            found_wildcard=1;

            maxfr=0,freq.clear();
        }

        current_sum+=a[i];
        maxfr=max(maxfr,++freq[current_sum]);
    }
    if(found_wildcard) ans+=maxfr;
    else ans+=freq[0];

    cout<<ans<<'\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll t; cin>>t; while(t--)
        tc();
    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$k=\text{lsb}(d)$$$, where $$$\text{lsb}(d)$$$ represents the least significant bit of $$$d$$$.

Since $$$a|x$$$ and $$$b|x$$$ are multiples of $$$d$$$, the last $$$k$$$ bits of $$$a$$$ and $$$b$$$ (and also $$$x$$$) must be equal to $$$0$$$.

Otherwise, there are no solutions and we can print $$$-1$$$.

To simplify the construction process, we will try to find some $$$x$$$ such that $$$a|x=b|x=x$$$. Since we already know that the last $$$k$$$ bits of $$$a$$$, $$$b$$$ and $$$x$$$ are $$$0$$$, we will consider that the other $$$30-k$$$ of the $$$30$$$ least significant bits of $$$x$$$ are equal to $$$1$$$:

This gives the following general formula for $$$x$$$:

Now, we'll try to find some $$$p$$$ for which $$$x$$$ is a multiple of $$$d=2^k \cdot d'$$$:

Time complexity per testcase: $$$O(log d)$$$

Note that if $$$a|b$$$ is already a multiple of $$$d$$$, we can consider $$$x=a|b$$$.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
void tc(){
    ll a,b,d,k=0,inverse_of_2,total_inverse=1;
    cin>>a>>b>>d;
    a|=b;
    if(a%d==0){
        cout<<a<<'\n';
        return;
    }
    while(a%2==0 && d%2==0)
        a/=2,d/=2,k++;
    inverse_of_2=(d+1)/2;
    if(a%2==1 && d%2==0){
        cout<<"-1\n";
        return;
    }

    for(ll i=0;i<30-k;i++)
        total_inverse=total_inverse*inverse_of_2%d;

    cout<<((total_inverse<<(30-k))-1)*(1ll<<k)<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    ll t; cin>>t; while(t--)
        tc();
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

Let $$$f(i,j)$$$ be the position of the leftmost maximum in the interval $$$(i;j)$$$, $$$1 \le i \le j \le n$$$.

Let's consider an interval $$$(l;r)$$$ such that $$$f(l,r)=m$$$. For the sake of simplicity, let's assume that $$$l \lt m \lt r$$$.

Let $$$p=f(l,m-1)$$$ and $$$p_2=f(m+1,r)$$$. Since $$$a_m$$$ is the leftmost maximum in $$$(l;r)$$$, $$$p \lt m$$$ and $$$p_2 \gt m$$$, the following conditions must hold for array $$$b$$$:

• $$$b_m \gt b_p$$$
• $$$b_m \ge b_{p_2}$$$

Let's consider a binary tree where the children of node $$$u=f(l,r)$$$ are nodes $$$p=f(l,u-1)$$$ and $$$p_2=f(u+1,r)$$$, for every $$$1 \le u \le n$$$.

Note that if $$$u=l$$$, $$$f(l,l-1)$$$ is not defined, and, as such, node $$$u$$$ will have no left child. Similarly, if $$$u=r$$$, then node $$$u$$$ will have no right child.

Let $$$dp[u][x]$$$ be equal to the number of ways to assign values to every element $$$b_v$$$ from the subtree rooted in $$$u$$$, if $$$b_u=x$$$.

• If $$$u$$$ has a left child and $$$x=1$$$, then $$$dp[u][x]=0$$$;
• Otherwise, if $$$u$$$ has two children, then $$$dp[u][x]=(\sum_{i=1}^{x-1}dp[p][i]) \cdot(\sum_{i=1}^{x}dp[p_2][i])$$$;
• If $$$u$$$ only has a left child, then $$$dp[u][x]=\sum_{i=1}^{x-1}dp[p][i]$$$;
• If $$$u$$$ only has a right child, then $$$dp[u][x]=\sum_{i=1}^{x}dp[p_2][i]$$$;
• If $$$u$$$ has no children, then $$$dp[u][x]=1$$$.

To optimise the transitions, we'll also need to compute $$$sum[u][x]=\sum_{i=1}^{x} dp[u][x]$$$ alongside our normal $$$dp$$$.

Intended time complexity per testcase: $$$O(n \cdot m+n \cdot log(n))$$$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll NMAX=2e5+5,LGMAX=18,MOD=1e9+7;
int n,m;

int leftmost_maximum[LGMAX][NMAX],msb[NMAX];
int v[NMAX];

vector<vector<ll>> dp,sum;

int leftmost_maximum_query(int l, int r){
    int bit=msb[r-l+1];
    if(v[leftmost_maximum[bit][l]]>=v[leftmost_maximum[bit][r-(1<<bit)+1]]) return leftmost_maximum[bit][l];
    else return leftmost_maximum[bit][r-(1<<bit)+1];
}
int divide(int l, int r){

    if(l>r) return -1;

    int mid=leftmost_maximum_query(l,r);

    int p=divide(l,mid-1),p2=divide(mid+1,r);

    for(int i=1;i<=m;i++){
        if(p!=-1 && i==1) dp[mid][1]=0;
        else dp[mid][i]=(p>=0?sum[p][i-1]:1ll)*(p2>=0?sum[p2][i]:1ll)%MOD;

        sum[mid][i]=(sum[mid][i-1]+dp[mid][i])%MOD;
    }
    return mid;
}
void tc(){

    cin>>n>>m;
    dp.resize(n),sum.resize(n);
    for(int i=0;i<n;i++){
        cin>>v[i];

        leftmost_maximum[0][i]=i;

        dp[i].resize(m+1),sum[i].resize(m+1);
        for(int j=0;j<=m;j++) dp[i][j]=sum[i][j]=0;
    }

    for(int bit=1;bit<LGMAX;bit++){
        for(int i=0;i+(1<<bit)<=n;i++){
            if(v[leftmost_maximum[bit-1][i]]>=v[leftmost_maximum[bit-1][i+(1<<(bit-1))]])
                leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i];
            else
                leftmost_maximum[bit][i]=leftmost_maximum[bit-1][i+(1<<(bit-1))];
        }
    }

    divide(0,n-1);

    cout<<sum[leftmost_maximum_query(0,n-1)][m]<<'\n';
}
int main()
{
    for(int i=2;i<NMAX;i++)
        msb[i]=msb[i-1]+((i&(i-1))==0); /// msb = floor(log2)

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin>>t; while(t--)
        tc();

    return 0;
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

If $$$m=dist(i,j)=((j+n-i) \mod n)$$$, $$$m \gt 0$$$ and $$$b_k=a_{(i+k) \mod n}$$$, let $$$f(i,j)$$$ be a sequence of operations that performs:

• $$$b_0 = b_0 \oplus b_{m-1}$$$;
• $$$b_1 = b_1 \oplus b_{m-2}$$$;
• $$$b_2 = b_2 \oplus b_{m-3}$$$;
• $$$\ldots$$$
• $$$b_{\lfloor\frac{m-1}{2} \rfloor } = b_{\lfloor \frac{m-1}{2} \rfloor} \oplus b_{\lfloor \frac{m+2}{2} \rfloor}$$$

If $$$n$$$ is even, we can reverse array $$$a$$$ by performing $$$f(0,n-1)$$$, $$$f(\frac{n}{2},\frac{n}{2}-1)$$$ and $$$f(0,n-1)$$$, in this order.

Otherwise, if $$$n$$$ is odd, we can perform $$$f(0,n-1)$$$, $$$f(\frac{n+1}{2},\frac{n-3}{2})$$$ and $$$f(0,n-1)$$$, in this order.

One possible way to construct $$$f(i,j)$$$ is as follows:

• Perform an operation on every $$$i$$$ from $$$m-1$$$ to $$$0$$$:

• Perform an operation on every $$$i$$$ from $$$1$$$ to $$$m-1$$$:

• Perform an operation on every $$$i$$$ from $$$m-2$$$ to $$$1$$$:

• Perform an operation on every $$$i$$$ from $$$2$$$ to $$$m-2$$$:

• $$$\ldots$$$

• The last step is to perform an operation on every $$$i$$$ from $$$0$$$ to $$$\lfloor\frac{m-2}{2}\rfloor$$$:

Here, $$$(l..r)$$$ denotes $$$b_l \oplus b_{l+1} \oplus \ldots \oplus b_r$$$.

The number of operations needed for $$$f(i,j)$$$ is equal to $$$m+(m-1)+\ldots+1+(\frac{m}{2})=\frac{m\cdot(m+1)}{2}+\frac{m}{2}=\frac{m^2+2\cdot m}{2}$$$, therefore the total number of operations needed to reverse the array is $$$\frac{3}{2} \cdot (m^2+2\cdot m)$$$. Since $$$m \le n-1$$$, $$$\frac{3}{2} \cdot (m^2+2\cdot m) \le \frac{3}{2} \cdot (399^2 + 2\cdot 399) \lt 250\,000$$$.

Time complexity per testcase: $$$O(N^2)$$$

#include <bits/stdc++.h>

using namespace std;

vector<int> ans;
int n;
void add_op(int pos){
    ans.push_back(pos%n);
}
void f(int l, int r){

    if(r<l) r+=n;

    int m=r-l,direction=0,start=l;
    r--;
    while(l<=r){

        if(direction==0){
            for(int i=r;i>=l;i--)
                add_op(i);
            l++;
        }
        else{
            for(int i=l;i<=r;i++)
                add_op(i);
            r--;
        }

        direction=1-direction;
    }
    for(int i=start;i<start+m/2;i++)
        add_op(i);
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0);
    cin>>n;

    f(0,n-1);

    f((n+1)/2,(n-2)/2);

    f(0,n-1);

    cout<<ans.size()<<'\n';

    for(auto it : ans) cout<<it<<' ';
}

Good problem

Ok problem

Bad problem

Didn't solve it, idk

1700 or less

1800

1900

2000

2100 or more

Didn't solve it, idk

Subtask 1 : $$$N \le 10^2$$$

This subtask is easy : Iterate through all pairs an check whether they are winning or not. If you do the check in $$$O(N)$$$ , the total time complexity will be $$$O(N^3)$$$.

Subtask 2 : $$$N \le 10^3$$$

Here we need to find a better way to find if the pair is winning or not. We can use data structures such as : segment tree , RMQ , treaps... The easiest way to do this whatsoever is to just calculate the maximum values "in-place" as you walk through the pairs. Thus we get $$$O(N^2)$$$.

Subtask 3 : $$$N \le 10^5$$$

Let's use a divide and conquer algorithm. Let's say $$$solve(st,dr)$$$ gives us the answer for the range $$$st...dr$$$. Let $$$mid = \frac{st+dr}{2}$$$. Add $$$solve(st,mid)$$$ and $$$solve(mid+1,dr)$$$ to the answer. The only sequences we've not counted are the ones passing through $$$mid$$$. So , we need to find the number of pairs $$$(i,j)$$$ such that $$$mid$$$ is in range $$$i...j$$$ and they hold the propriety. One can notice that every such pair is a reunion of a suffix in $$$st...mid$$$ and a prefix in $$$mid+1...dr$$$. The maxim value in $$$A$$$ will be present in either a prefix or a suffix. Let's iterate through it , and count the good sequences using binary search in the other half. We will count duplicates... But fortunately , we can get rid of them by just using the following trick : When we refer to the position of the maximum value , we will be talking about its leftmost appearance. One can see that this solution runs in $$$O(N \cdot log^2N)$$$

Subtask 4 : $$$N \le 10^6$$$ ( Credits to Gheal )

Let $$$dp_k$$$ store the number of winning pairs (i,j) such that $$$i=k$$$. We need to look for the next "event". By event we mean when either the maximum value in $$$A$$$ changes or the maximum value of $$$B$$$ changes. We need to always go to the next event and use the dp from there. To count the number of pairs until we reach the next event ,we just need to check whether the current maximum in $$$B$$$ is greater or equal to the one in $$$A$$$. Having next[k] = the index where the next change happens if we currently are at index $$$k$$$ , we conclude the recurrence

To calculate $$$next$$$ we can just use two stacks with complexity $$$O(N)$$$. Thus , our final time complexity will be $$$O(N)$$$.

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX = 1e6 + 5;
ll a[NMAX], b[NMAX], nxtgt[NMAX], nxtge[NMAX], dp[NMAX];
ll nxt[NMAX];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    //freopen("in.txt","r",stdin);
    ll n;
    cin >> n;
    for (ll i = 0; i < n; i++)
        cin >> b[i];

    for (ll i = 0; i < n; i++)
        cin >> a[i];

    stack<ll> cndgt, cndge;
    for (ll i = n - 1; i >= 0; i--) {
        while (!cndgt.empty() && a[i] >= max(a[cndgt.top()], b[cndgt.top()]))
            cndgt.pop();
        nxtgt[i] = (cndgt.empty() ? n : cndgt.top());

        while (!cndge.empty() && b[i] > max(a[cndge.top()], b[cndge.top()]))
            cndge.pop();
        nxtge[i] = (cndge.empty() ? n : cndge.top());

        nxt[i] = (a[i] >= b[i] ? nxtgt[i] : nxtge[i]);

        cndge.push(i), cndgt.push(i);
    }
    ll ans = 0;
    for (ll i = n - 1; i >= 0; i--) {
        dp[i] = dp[nxt[i]] + (nxt[i] - i) * (a[i] >= b[i]);
        ans += dp[i];
    }
    cout << ans;
    return 0;
}

1700 or less

1800

1900

2000

2100 or more

Didn't solve it, idk

Subtask 1 : $$$N \le 50$$$

For this subtask it is enough to loop through all possible tuples and increment the answer if a valid tuple is found. Time complexity $$$O(N^4)$$$.

Subtask 2 : $$$N \le 2000$$$

We can easily notice how $$$\lfloor \frac{A_i}{A_j} \rfloor$$$ and $$$\lfloor \frac{A_k}{A_l} \rfloor$$$ are basicly indpendent. Thus make an array containing $$$\lfloor \frac{A_x}{A_y} \rfloor$$$ for every pair $$$(x,y)$$$ and count the number of solutions that sum up to $$$T$$$. This can be easily done in $$$O(N^2)$$$ or $$$O(N^2logN)$$$.

Subtask 3 : $$$A_i \le 10^5$$$

We will use the fact that $$$\lfloor \frac{A_x}{A_y} \rfloor$$$ for a fixed $$$A_x$$$ has at most $$$2 \cdot \sqrt{A_x}$$$ distinct values. We will use prefix sums on a frequency array to update the count of each value. This way , we can get an $$$O(10^5 \sqrt{10^5})$$$ time complexity per worst case.

Subtask 4 : $$$A_i \le 5 \cdot 10^5$$$

We can try to go through $$$A_y$$$ instead of $$$A_x$$$. We can see that $$$\lfloor \frac{A_x}{A_y} \rfloor$$$ equals $$$0$$$ in the range $$$0...A_y-1$$$ , equals $$$1$$$ in range $$$A_y....2 \cdot A_y - 1$$$ and so on. Thus we will go through multiples of each value and with the help of prefix sums we can compute the answer quickly.

Time complexity $$$O(5 \cdot 10^5 \cdot log(5 \cdot 10^5))$$$.

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, t, mod;
    cin >> n >> t >> mod;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    int maxi = *max_element(a.begin() + 1, a.end());
    vector<int> f(maxi + 1);
    for (int i = 1; i <= n; ++i) {
        f[a[i]]++;
    }
    for (int i = 1; i <= maxi; ++i) {
        f[i] += f[i - 1];
    }
    function<int(int, int)> query = [&](int st, int dr) {
        if (st == 0) {
            return f[dr];
        }
        return f[dr] - f[st - 1];
    };
    vector<int> cnt(maxi + 1);
    for (int i = 1; i <= maxi; ++i) {
        if (query(i, i)) {
            for (int j = 0; j <= maxi; j += i) {
                int st = j;
                int dr = min(maxi, j + i - 1);
                cnt[j / i] += (1ll * query(i, i) * query(st, dr)) % mod;
                if (cnt[j / i] >= mod) {
                    cnt[j / i] -= mod;
                }
            }
        }
    }
    int st = 0, dr = t;
    int ans = 0;
    while (st <= t) {
        if (st <= maxi && dr <= maxi) {
            ans += (1ll * cnt[st] * cnt[dr]) % mod;
            if (ans >= mod) {
                ans -= mod;
            }
        }
        st++;
        dr--;
    }
    cout << ans;
}

1500 or less

1600

1700

1800

1900 or more

Didn't solve it, idk

When do we know for certain that no solution exists?

If a solution exists, then pretty much any greedy approach works.

First and foremost, any element $$$ans[i][j]$$$ occurs exactly once in the product of all $$$a_i$$$, and exactly once in the product of all $$$b_j$$$. Therefore, we can conclude that, in order to have a solution, $$$a_1 \cdot a_2 \cdot \ldots a_n$$$ must be equal to $$$b_1 \cdot b_2 \cdot \ldots b_m$$$.

This properity gives us the following inefficient greedy algorithm:

1. Initialize all $$$ans[i][j]$$$ with $$$1$$$;
2. Select some prime divisor $$$k$$$ of $$$a_1 \cdot a_2 \cdot \ldots a_n$$$;
3. Find some indices $$$i$$$ and $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$) for which both $$$a[i]$$$ and $$$b[j]$$$ are multiples of $$$k$$$;
4. Divide both $$$a[i]$$$ and $$$b[j]$$$ by $$$k$$$ and multiply $$$ans[i][j]$$$ by $$$k$$$;
5. Repeat steps $$$2$$$ through $$$4$$$ until all $$$a[i]$$$ are equal to $$$1$$$.

The $$$2,3,4$$$ loop in the previous algorithm can be greatly optimized, as follows:

1. For all pairs of indices $$$(i,j)$$$, find the largest prime number $$$k$$$ that is a divisor of both $$$a[i]$$$ and $$$b[j]$$$.
2. Divide both $$$a[i]$$$ and $$$b[j]$$$ by $$$k$$$ and multiply $$$ans[i][j]$$$ by $$$k$$$;
3. Repeat until there are no primes remaining which are divisors of both $$$a[i]$$$ and $$$b[j]$$$.

This algorithm is already much better, giving us a time complexity of $$$O(N \cdot M \cdot \sqrt{VMAX})$$$, or $$$O((N \cdot M + VMAX)\cdot log(VMAX))$$$, if a sieve is used to precompute the largest prime divisor for all numbers up to $$$VMAX$$$.

Coming up with a more efficient solution requires the following observation: For every pair of indices $$$(i,j)$$$, the second algorithm multiplies, in the end, $$$a[i][j]$$$ by $$$gcd(a[i],b[j])$$$. In conclusion, the most efficient algorihthm would be as follows:

1. For all pairs of indices $$$(i,j)$$$, calculate $$$k=gcd(a[i],b[j])$$$;
2. Divide both $$$a[i]$$$ and $$$b[j]$$$ by $$$k$$$ and multiply $$$ans[i][j]$$$ by $$$k$$$.

Total time complexity: $$$O((\sum N \cdot M)\cdot log(VMAX))$$$

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

typedef long long ll;
const ll NMAX=2e3+5;
int l[NMAX],c[NMAX];
int ans[NMAX][NMAX];
int Gcd(int a, int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void tc(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>l[i];
    for(int i=0;i<m;i++)
        cin>>c[i];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ans[i][j]=Gcd(l[i],c[j]);
            l[i]/=ans[i][j],c[j]/=ans[i][j];
        }
    }
    bool good=1;
    for(int i=0;i<n;i++)
        if(l[i]>1)
            good=0;

    for(int i=0;i<m;i++)
        if(c[i]>1)
            good=0;

    if(!good) cout<<"-1\n";
    else{
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                cout<<ans[i][j]<<" \n"[j==m-1];
    }
}
int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin>>t; while(t--)
        tc();
    return 0;
}

This problem is very classic and much easier than most 9th grade ONI problems. We have decided to include it in the problemset because it's quite fun and instructive (especially for less experienced coders).

I would like to apologise for the weak tests that didn't focus enough on testcases with no solutions.

2100 or less

2200-2300

2400-2500

2600-2700

2800 or more

Didn't solve it, idk

Do note that the solution presented might be one among many. If your solution differs, you are welcome to share it here.

Gheal: This is by far the hardest Div.1 problem, I'm really sorry for everyone who read the innocent-looking statement thinking that this problem is fairly trivial.

Apparently, the tests aren't that great, but we had a lot of trouble getting our solutions to pass them.

valeriu: As much as this problem wasted a lot of my time, I find myself very lucky to have implemented such a problem outside of competition for the first time. Nevertheless, I spent 5 straight hours trying to repair and restructure code, while my colleague admittedly spent 4 days :)). Hope this problem didn't make you want to quit CP.

2000 or less

2100

2200

2300

2400 or more

Didn't solve it, idk

We will use the following inequality : If we have three integers $$$A,B,C$$$ satisfying $$$A \le B \le C$$$, then $$$min(A \oplus B, B \oplus C) \le A \oplus C$$$. This can be extended for $$$N$$$ integers and it shows us that the minimum xor pair is the minimum xor beetween adjacent values after sorting the array.

Subtask 1 : $$$N,M \le 100$$$

In this subtask we can use the above fact and build $$$dp[i][j]$$$ = how many subsets have minimum xor of adjacent values equal to $$$j$$$ if we only had the first $$$i$$$ elements of the initial array. It is easy to transition in $$$O(N)$$$ and get $$$O(N^2 \cdot M)$$$.

Subtask 2 : $$$N \cdot M \le 10^6$$$

We will use the following trick : The number of subsets having minimum xor equal to k is the number of subsets having xor greater than k-1 — the number of subsets having xor greater than k. Using this observation we can solve $$$f(x)$$$ = the number of subsets having minimum xor greater than x for every x in $$$O(NlogM)$$$ using dynamic programming. Thus , we've reduced the complexity to $$$O(NMlogM)$$$ which is fast enough to get 100 points.

#include <bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m, mod;
    cin >> n >> m >> mod;
    int lg = 0;
    for (int i = 0; (1 << i) <= m; ++i) {
        lg = i;
    }
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a.begin() + 1, a.end());
    vector<vector<int>> cnt(2 * m, vector<int>(lg + 1));
    function<int(int)> solve = [&](int lim) {
        if (lim == -1) {
            int ans = 1;
            for (int i = 1; i <= n; ++i) {
                ans += ans;
                if (ans >= mod) {
                    ans -= mod;
                }
            }
            return (ans - n - 1 + mod) % mod;
        }
       
        vector<int> dp(n + 1);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            int qui = 0;
            for (int j = lg; j >= 0; --j) {
                if (lim & (1 << j)) {
                    qui += (a[i] ^ (1 << j)) & (1 << j);
                }
                else {
                    dp[i] += cnt[qui + ((a[i] ^ (1 << j)) & (1 << j))][j];
                    if (dp[i] >= mod) {
                        dp[i] -= mod;
                    }
                    qui += (a[i] & (1 << j));
                }
            }
            qui = 0;
            for (int j = lg; j >= 0; --j) {
                qui += (a[i] & (1 << j));
                cnt[qui][j] += dp[i];
                cnt[qui][j]++;
                if (cnt[qui][j] >= mod) {
                    cnt[qui][j] -= mod;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            int qui = 0;
            for (int j = lg; j >= 0; --j) {
                qui += (a[i] & (1 << j));
                cnt[qui][j] = 0;
            }
        }
        for (int i = 1; i <= n; ++i) {
            ans += dp[i];
            if (ans >= mod) {
                ans -= mod;
            }
        }
        return ans;
    };
    function<int(int)> solve_brute = [&](int lim) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; ++i) {
            for (int j = i - 1; j >= 1; --j) {
                if ((a[i] ^ a[j]) > lim) {
                    dp[i] += dp[j];
                    dp[i]++;
                    if (dp[i] >= mod) {
                        dp[i] -= mod;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans += dp[i];
            if (ans >= mod) {
                ans -= mod;
            }
        }
        return ans;
    };
    vector<int> greater(1 << (lg + 1));
    for (int i = 0; i < 1 << (lg + 1); ++i) {
        greater[i] = solve(i - 1);
    }
    int ans = 0;
    for (int i = 0; i < (1 << (lg + 1)); ++i) {
        int cnt = (greater[i] - (i == (1 << (lg + 1)) - 1 ? 0 : greater[i + 1]) + mod) % mod;
        ans += (1ll * cnt * i) % mod;
        if (ans >= mod) {
            ans -= mod;
        }
    }
    cout << ans;
}

1900 or less

2000

2100

2200

2300 or more

Didn't solve it, idk

Part 1: Solving the problem without updates:

Firstly, there are quite a few edge cases:

1. It is impossible to get from ($$$X_1,Y_1$$$) to ($$$X_2,Y_2$$$) if $$$X_2 \lt X_1$$$;
2. It is impossible to get from ($$$X_1,Y_1$$$) to ($$$X_2,Y_2$$$) if $$$X_1 = X_2$$$ and $$$Y_1 \neq Y_2$$$;
3. There exists exactly one path from ($$$X_1,Y_1$$$) to ($$$X_1,Y_1$$$).

Otherwise, $$$X_2$$$ must be greater than $$$X_1$$$. Let's consider the following example:

In this example there are $$$9$$$ active points ($$$A,B,C,D,E,F,G,H,K$$$) and two auxiliary points ($$$I$$$ and $$$J$$$). Additionally, $$$X_B=X_C=X_D=X_E=X_I$$$ and $$$X_F=X_G=X_H=X_J$$$. Note that a new auxiliary point has been added for every $$$x$$$-value between $$$X_A$$$ and $$$X_K$$$.

Each path between $$$A$$$ and $$$K$$$ passes through every $$$x$$$-coordinate between $$$X_A$$$ and $$$X_K$$$. For each $$$x$$$-coordinate, a path can either pass through exactly one point ($$$x,y$$$) or through none at all. The latter possibility can be solved by adding one auxiliary point at every $$$x$$$-coordinate between $$$X_A$$$ and $$$X_K$$$. More specifically, if some path skips an $$$x$$$-coordinate, then we can assume that it visits the auxiliary point of that $$$x$$$-coordinate.

With all this in mind, the $$$3$$$ paths highlighted in the image are actually $$$A \to K$$$ (orange), $$$A \to B \to H \to K$$$ (magenta) and $$$A \to D \to K$$$ (lime).

Therefore, the answer is $$$(cnt[X_A+1]+1)\cdot (cnt[X_A+2]+1) \cdot \ldots \cdot (cnt[X_K-1]+1)$$$, where $$$cnt[x]$$$ represents the number of points with that $$$x$$$-coordinate.

It is possible to answer each query in $$$O(log(MOD))$$$ by precomputing an array $$$prod$$$ for every $$$x$$$-coordinate which contains at least one active point:

.

Using this array, the number of ways to get from a point $$$(X_1,Y_1)$$$ to another point $$$(X_2,Y_2)$$$ will be equal to:

.

Part 2: Solving the problem with updates:

Instead of making $$$prod$$$ a prefix array, we can make it a Fenwick tree. Since the values of $$$X_i$$$ are in an inconvenient range, namely $$$[-1e9,1e9]$$$, we can map them to the smaller interval of $$$[1,N+Q]$$$ using coordinate compression.

If a new point $$$(x,y)$$$ is activated, then $$$cnt[x]$$$ will be increased by $$$1$$$. To update $$$prod$$$, a normal BIT update is enough, in which case all affected elements will be multiplied by $$$\frac{cnt[x]+2}{cnt[x]+1} (\text{mod } 10^9+7)$$$. Similarly, if some point $$$(x,y)$$$ is deactivated, all affected elements will be multiplied by $$$\frac{cnt[x]}{cnt[x]+1} (\text{mod } 10^9+7)$$$.

Total time complexity: $$$O((N+Q) log(N+Q))$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll NMAX=6e5+5,MOD=1e9+7;
ll bit[NMAX],fr[NMAX];
map<ll,ll> compressed;
unordered_set<ll> active;
set<ll> distinctx;
ll inx[NMAX],iny[NMAX];
char t[NMAX];
ll qx1[NMAX],qx2[NMAX],qy1[NMAX],qy2[NMAX],inv[NMAX];
ll binPow(ll x, ll y){
    ll ans=1;
    for(;y;y>>=1,x=x*x%MOD)
        if(y&1)
           ans=ans*x%MOD;
    return ans;
}
void mul(ll pos, ll val){
    while(pos<NMAX)
        bit[pos]=bit[pos]*val%MOD,pos+=pos&-pos;
}
ll query(ll pos){
    ll ans=1;
    while(pos)
        ans=ans*bit[pos]%MOD,pos-=pos&-pos;
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    for(ll i=0;i<NMAX;i++) bit[i]=1,inv[i]=binPow(i,MOD-2);
    ll n,q;
    cin>>n>>q;
    for(ll i=0;i<n;i++){
        cin>>inx[i];
        distinctx.insert(inx[i]);
    }
    for(ll i=0;i<n;i++) cin>>iny[i];

    for(ll i=0;i<q;i++){
        cin>>t[i]>>qx1[i]>>qy1[i];
        distinctx.insert(qx1[i]);
        if(t[i]=='?') cin>>qx2[i]>>qy2[i];
    }
    for(auto it : distinctx)
        compressed[it]=compressed.size()+1;
    for(ll i=0;i<n;i++){
        inx[i]=compressed[inx[i]];
        mul(inx[i],binPow(fr[inx[i]]+1,MOD-2));
        ++fr[inx[i]];
        mul(inx[i],fr[inx[i]]+1);
        active.insert(iny[i]*NMAX+inx[i]);
    }
    for(ll i=0;i<q;i++){
        if(t[i]=='!'){
            qx1[i]=compressed[qx1[i]];
            mul(qx1[i],inv[fr[qx1[i]]+1]);
            if(active.count(qy1[i]*NMAX+qx1[i]))
                --fr[qx1[i]],active.erase(qy1[i]*NMAX+qx1[i]);
            else
                ++fr[qx1[i]],active.insert(qy1[i]*NMAX+qx1[i]);
            mul(qx1[i],fr[qx1[i]]+1);
        }
        else{
            qx1[i]=compressed[qx1[i]];
            qx2[i]=compressed[qx2[i]];
            if(qx2[i]<qx1[i] || (qx2[i]==qx1[i] && qy1[i]!=qy2[i]))
                cout<<"0\n";
            else if(qx1[i]==qx2[i] && qy1[i]==qy2[i])
                cout<<"1\n";
            else
                cout<<query(qx2[i]-1)*binPow(query(qx1[i]),MOD-2)%MOD<<'\n';
        }
    }
    return 0;
}

Definitely the easiest Div.1 problem. The time limit is pretty tight because andrei_boaca's SQRT decomposition solutions kept getting 100 points.

It is always optimal to add the smallest integer which is not already in the array.

The number of operations will never exceed $$$\sqrt{2 \cdot s}.$$$

Based on the first hint, the final array will be equal to $$${v_1,v_1,\ldots, v_n} \cup [1,x]$$$, for some $$$x$$$.

Hint 4: How can we find the value of $$$x$$$ faster than $$$O(\sqrt{s})$$$?

Lemma: The number of operations will never exceed $$$\sqrt{2 \cdot s}$$$.

Since we need to maximize the final length of the array, it is always optimal to add the smallest integer which is not already present in $$$a$$$.

The naive implementation of this idea has a runtime complexity of $$$O(n \cdot \sqrt s)$$$, although this can be easily optimized to $$$O((n+ \sqrt s)log(n))$$$, if binary search is used to check whether the new elements are already present in $$$a$$$.

The optimal solution has a runtime complexity of $$$O(N log S)$$$. Based on hints $$$3$$$ and $$$4$$$, we can find the value of $$$x$$$ with binary search. For some $$$x$$$, the sum of the elements in $$$a$$$ will be equal to $$$sum(x)=\frac{x\cdot(x+1)}{2}+\sum_1 v_i$$$, where $$$\sum_1 v_i$$$ is the sum of the elements greater than $$$x$$$.

Since the sum of elements $$$sum(x)$$$ is a monotonous function, we can use binary search on the interval $$$[1,\sqrt{2 \cdot s}]$$$ to find the exact value of $$$x$$$.

Final time complexity: $$$O(N log S)$$$

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll NMAX=2e5+5;

ll v[NMAX];
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll n,s;
    cin>>n>>s;

    for(ll i=0;i<n;i++)
        cin>>v[i];
    ll l=0,r=2e9,ans=0;

    while(l<=r){
        ll m=(l+r)/2;
        ll sum=m*(m+1)/2;

        for(ll i=0;i<n;i++)
            if(v[i]>m)
                sum+=v[i];

        if(sum>=s)
            ans=m,r=m-1;
        else
            l=m+1;
    }

    ll len=ans;

    for(ll i=0;i<n;i++)
        len+=(v[i]>ans);

    cout<<len;

    return 0;
}

The numbers are printed in ``layers''.

Try to represent the layers as a binary tree.

To better understand the solution, let's consider $$$n=12$$$. The final array is the BFS traversal starting from the root of the following binary tree:

This binary tree was generated by starting with the root $$$m=\lfloor \frac{n+1}{2} \rfloor=6$$$. Each node $$$m=\lfloor \frac{l+r}{2}\rfloor$$$ has up to two children: $$$m_1=\lfloor \frac{l+(m-1)}{2} \rfloor$$$ and $$$m_2=\lfloor \frac{r+(m+1)}{2} \rfloor$$$.

If our given integer $$$k$$$ is in a complete layer, then we can employ a binary search-type algorithm to find the position of $$$k$$$:

l = 1, r = n, position = 1, visited_nodes = 1
while(visited_nodes<=n){
    m = (l + r) / 2

    if(k==m){
        print position
        return
    }
    
    if(k<m) position = position * 2
    else position = position * 2 + 1

    visited_nodes = visited_nodes * 2 + 1
}

This algorithm has the added benefit of not printing anything if $$$k$$$ is not in a complete layer. In this case, the position of $$$k$$$ in the last layer can be determined from $$$position$$$, although this isn't very straightforward. If the binary tree were complete, then the position of $$$k$$$ in the last layer would be $$$position-\frac{\text{visited_nodes}-1}{2}$$$, since there are $$$\frac{\text{visited_nodes}-1}{2}$$$ nodes on the other layers, all of which will be printed before $$$k$$$.

By looking at the missing nodes from the binary tree for $$$n=12$$$, one may make the crucial observation that the general case position for $$$k$$$ in the last layer is equal to $$$k-(position-\frac{\text{visited_nodes}-1}{2})$$$.

In conclusion, the final position for $$$k$$$ will be $$$k-(position-\frac{\text{visited_nodes}-1}{2})+\frac{\text{visited_nodes}-1}{2}=k+\text{visited_nodes}-position-1$$$.

Time complexity per testcase: $$$O(log n)$$$

#include<bits/stdc++.h>
#define NMAX 1000005

using namespace std;
typedef long long ll;
void tc(){
    ll n,p;
    cin>>n>>p;
    ll cntLess=0,cnt=1,currentId=1;
    ll l=1,r=n;
    while(cnt<=n){
        ll m=(l+r)/2;
        cntLess=cntLess*2+(p>=m);
        if(m==p){
            cout<<currentId<<' ';
            return;
        }
        else if(p<m) r=m-1,currentId*=2;
        else l=m+1,currentId=currentId*2+1;
        cnt=cnt*2+1;
    }
    cout<<p+cnt/2-cntLess<<' ';
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--)
        tc();

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long dfs(pair<long long, long long> interv, long long k) {
    long long mid = (interv.first + interv.second) / 2;
    if (k == mid) {
        return 1ll;
    }
    if (k < mid) {
        return 1ll + dfs({ interv.first,mid - 1 }, k);
    }
    else {
        return 1ll + dfs({ mid + 1,interv.second }, k);
    }
}
long long count(pair<long long, long long> interv, long long lvl) {
    long long lg = interv.second - interv.first + 1;
    return min((1ll << (lvl - 1)), lg - ((1ll << (lvl - 1)) - 1));
}
long long solve(pair<long long, long long> interv, long long k, long long lvl) {
    long long mid = (interv.first + interv.second) / 2;
    if (mid == k) {
        return 1;
    }
    if (mid < k) {
        return count({ interv.first,mid - 1 }, lvl - 1) + solve({ mid + 1,interv.second }, k, lvl - 1);
    }
    else {
        return solve({ interv.first,mid - 1 }, k, lvl - 1);
    }
}
long long solve_brute(long long n, long long k) {
    vector<long long> a(n + 1);
    long long p = 0;
    queue<pair<long long, long long>> q;
    q.push({ 1,n });
    while (!q.empty()) {
        pair<long long, long long> current = q.front();
        long long mid = (current.first + current.second) / 2;
        a[++p] = mid;
        if (mid > current.first) {
            q.push({ current.first , mid - 1 });
        }
        if (mid < current.second) {
            q.push({ mid + 1,current.second });
        }
        q.pop();
    }
    for (long long i = 1; i <= n; ++i) {
        if (a[i] == k) {
            return i;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long q;
    cin >> q;
    while (q--) {
        long long n, k;
        cin >> n >> k;
        long long lvl = dfs({ 1,n }, k);
        cout << ((1ll << (lvl - 1)) - 1) + solve({ 1,n }, k, lvl) << ' ';
    }
}

Any final configuration can be uniquely determined by a permutation of $$${1,2,3,\ldots, k}$$$

$$$k \le 20$$$

Note: $$$getBit(a,b)$$$ is the the value of the $$$b$$$-th least significant bit of $$$a$$$. For example, $$$getBit(6,0)=1$$$, $$$getBit(6,1)=0$$$, and $$$getBit(6,2)=1$$$.

Let dp[mask] be the minimum number of moves required to cover the first $$$\Sigma_{i=1}^k getBit(mask,i)*p_i$$$ slots with all plates of colours $$$c_1,c_2,\ldots$$$ where $$$getBit(mask,c_i)=1, \forall i$$$. Naturally, $$$dp[0]=0$$$.

Transitioning from $$$dp[mask]$$$ to $$$dp[mask+2^k]$$$, where $$$getBit(mask,k)=0$$$ can be done fairly easily. Let $$$pos=\Sigma_{i=1}^k getBit(mask,i)*p_i$$$ and $$$cntdiff(l,r,k)$$$ be the number of plates in the initial configuration $$$a_i$$$ which satisfy the following requirements:

• $$$l \le i \le r$$$;
• $$$a_i \neq 0$$$;
• $$$a_i \neq k$$$.

From these definitions, the value of $$$dp[mask+2^k]$$$ can be computed using the following formula:

$$$cntdiff(l,r,k)$$$ can be calculated in $$$O(1)$$$ per query using prefix sums. Calculating the prefix sums has a time complexity of $$$O(n \cdot k)$$$.

Intended time complexity: $$$O(n\cdot k + 2^k \cdot k)$$$

Reconstructing the final configuration will also require an auxiliary array $$$prev[mask]$$$ — the last colour added to $$$mask$$$.

#include<bits/stdc++.h>

using namespace std;
const int NMAX=1e5+1,KMAX=21;
int dp[1<<KMAX],lastAdded[1<<KMAX],cnt[KMAX],n,k;
bool visited[1<<KMAX];
int freq[NMAX][KMAX];
int cnteq(int l, int r, int num){
    if(r<l)
        return 0;
    return freq[r][num]-(l?freq[l-1][num]:0);
}
int cntdiff(int l, int r, int num){
    if(r<l)
        return 0;
    return r-l+1-cnteq(l,r,num)-cnteq(l,r,0);
}
void iterativeBt(){
    queue<pair<int,int>> q; /// (bitmask, pos)
    q.push({0,0});
    visited[0]=1;
    while(!q.empty()){
        int bm=q.front().first,pos=q.front().second;
        for(int i=0;i<k;i++){
            if(!(bm>>i&1)){
                if(dp[bm]+cntdiff(pos,pos+cnt[i]-1,i+1)<dp[bm|(1<<i)]){
                    lastAdded[bm|(1<<i)]=i;
                    dp[bm|(1<<i)]=dp[bm]+cntdiff(pos,pos+cnt[i]-1,i+1);
                }
                if(!visited[bm|(1<<i)]){
                    q.push({bm|(1<<i),pos+cnt[i]});
                }
                visited[bm|(1<<i)]=1;
            }
        }
        q.pop();
    }
}
int main()
{
    for(int i=1;i<(1<<KMAX);i++) dp[i]=INT_MAX; /// dp[0]=0
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        if(i) for(int j=0;j<=k;j++)
            freq[i][j]=freq[i-1][j];
        freq[i][x]++;
    }
    for(int i=0;i<k;i++){
        scanf("%d",&cnt[i]);
    }
    iterativeBt();
    stack<int> ans; int pos=(1<<k)-1;
    printf("%d\n",dp[pos]);
    while(pos){
        ans.push(lastAdded[pos]);
        pos^=(1<<lastAdded[pos]);
    }
    while(!ans.empty()){
        for(int i=0;i<cnt[ans.top()];i++)
            printf("%d ",ans.top()+1);
        ans.pop();
    }
    return 0;
}