ARCRT - Editorial

[alei]

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Aman Gupta
Coauthor & Tester: Radoslav Dimitrov
Editorialist: Alei Reyes

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Dynamic Connectivity, Link-cut trees

PROBLEM:

You are given two arrays (A_1, A_2,...,A_N) and (B_1, B_2,...,B_N).
For each index i, find the number of distinct arrays (C_1,C_2,...C_M) of maximum length such that C_{j} is either equal to A_{i+j-1} or B_{i+j-1}, and all the elements of C are distinct.

QUICK EXPLANATION:

Represent the sequence C as a graph with edges (A_i,B_i). Use two pointers to keep the largest pseudoforest, for each tree of K vertices there are K different sequences, and for each tree+cycle there are two ways. Is possible to use dnamic connectivity data structures like link-cut trees to keep the pseudoforest after the remove and insertion of edges.

EXPLANATION:

First let’s count the number of possible sequences that starts from the beginning of the array. Let (C_1,C_2,...,C_M) be any of the possible sequences, note that C_i \in \{A_i,B_i \} because in each position we have to decide to use either A_i or B_i.

We can represent all the possible sequences as a graph G where each entry C_i is an undirected edge connecting vertices A_i and B_i. The problem is transformed to assign directions to the edges, an edge A_i \rightarrow B_i means we decided to use B_i, similarly the reverse edge A_i \leftarrow B_i means we decided to use A_i. Moreover since the array contains distinct integers, the indegree of each vertex should be at most 1.

We can assign directions independently for each connected componente of G, the total number of ways of assigning directions, is the product of the number of ways of each connected component.

Let’s focus in a single connected component H, Let V denote the number of vertices and E the number of edges. It turns out that E can be either equal to V or V-1, because with less than V-1 edges the graph becomes disconnected and with more than V edges at least one of the vertices gets an indegree greater than 1 (each edge increases by one the number of used vertices). Let’s analyze both cases:

• E=V-1
  Tthe graph is a tree, we can root the tree on any of its vertices and make each node point to each of its chidren. There are V ways of assigning directions, one for each possible root.

• E=V
  The graph is a tree plus a cycle, I call this type of graph octopus (the cycle is the head of the octopus, and the outgoing trees the tentacles). A cycle has only two possible directions (clockwise or counter-clockwise). Once we have assigned one of the possible directions for the head of the octoups the directions of the tentacles are uniquely determined (the roots are in the head). For the degenerate case of a self-loop there is only one way.

The problem is reduced to find for each index i, the maximum integer r_i such that the graph consisting of the edges from i through r_i is a pseudoforest. This can be easily done in N^2 \cdot log(N) using DSU (which solves the first subtask).

To improve the solution we can use two pointers, note that r_{i+1} \geq r_i. So once we found the maximum subarray for index i, we can remove the edge (A_i,B_i) and start adding more edges starting from r_{i}+1 (if it doesn’t add additional cycles to an octopus). The problem of adding and removing edges from a graph and keeping which vertices are connected is called dynamic connectivity, and for the special case of trees it can be solved with a Link-cut tree. However it requires some tweaks to keep which connected component contains a cycle, in some approaches is necessary to find the LCA of two nodes (take a look to CF88E ) and it is even harder to modify the data structure to keep the number of vertices of each connected component. During testing phase Nishant realized that the edges are added and removed not randomly, but in queue order, so it is possible to do the rollbacks with DSU, he implemented a solution based in this cf post

About ARCRT:

Initially the problem only asked to find the longest subarray starting from position 1, however we were aware of an undesirable binary search + bipartite matching solution, so I suggested to find the longest subarray starting from any position (a “simple” link-cut tree problem). However during testing Radoslav squeezed a two-pointer + incremental matching solution! and it was hard to create tests against it, so I came up with the final combinatorial problem. The setter was not familiar with Link-cut trees, however that didn’t prevent him to prepare test data by running a quadratic DSU for a couple of hours. Radoslav provided the final implementation (an algorithm must be seen to be believed ).

Setter's Solution (first subtask)

#include <bits/stdc++.h>

using namespace std;

struct DisjointSets {
  int n;
  vector<int> id;
  vector<int> size_n, cycleFlag;
  
  DisjointSets(int n) {
    this-> n = n;
    id = vector<int>(n+1);
    size_n = vector<int>(n+1, 1);
    cycleFlag = vector<int>(n+1, 0);
    iota(id.begin(), id.end(), 0);
  }

  int findSet(int v) {
    while(id[v] != v) {
      id[v] = id[id[v]];
      v = id[v]; 
    }
    return v;
  }

  bool weighted_union(int x, int y) {
    int set1 = findSet(x);
    int set2 = findSet(y);

    if(cycleFlag[set1] > 0 && cycleFlag[set2] > 0) {
      return false;
    }

    if(x == y) {
      cycleFlag[set1] = 2;
      return true;
    }

    if(set1 == set2) {
      cycleFlag[set1] = 1;
      return true;
    }

    if(size_n[set1] > size_n[set2]) {
        id[set2] = id[set1];
        size_n[set1] += size_n[set2];
        cycleFlag[set1] = max(cycleFlag[set1], cycleFlag[set2]);
    }
    else {
      id[set1] = id[set2];
      size_n[set2] += size_n[set1];
      cycleFlag[set2] = max(cycleFlag[set1], cycleFlag[set2]);
    }
    return true;
  }
};

const int MOD = 1e9+7;

inline long long multiply(long long x, long long y) {
  return ((x % MOD) * (y % MOD)) % MOD;
}


int main() {

  int T;
  cin >> T;
  
  while(T--) {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    unordered_map<int, int> mp;
    int nodesCount = 1;
    for(int i = 0; i < n; i++) {
      cin >> a[i];
      if(mp.count(a[i])) {
        a[i] = mp[a[i]];
      }
      else {
        mp[a[i]] = nodesCount;
        a[i] = nodesCount;
        nodesCount++;
      }
    }
    for(int i = 0; i < n; i++) {
      cin >> b[i];
      if(mp.count(b[i])) {
        b[i] = mp[b[i]];
      }
      else {
        mp[b[i]] = nodesCount;
        b[i] = nodesCount;
        nodesCount++;
      }
    }
    nodesCount--;
    vector<int> res(n);

    for(int i = 0; i < n; i++) {
      DisjointSets st(nodesCount);
      vector<int> done(nodesCount+1);
      vector<int> comps;
      int last = i;

      for(int j = i; j < n; j++) {
        if(!st.weighted_union(a[j], b[j])) break;
        last = j;
      }

      for(int j = i; j <= last; j++) {
        int setId = st.findSet(a[j]);
        if(!done[setId]) {
          comps.push_back(setId);
          done[setId] = true;
        }
      }

      int ans = 1;
      for(int j : comps) {
        if(st.cycleFlag[j] == 2) continue;
        else if(st.cycleFlag[j] == 1) ans = multiply(ans, 2);
        else ans = multiply(ans, st.size_n[j]);
      }
      res[i] = ans;
    }
    for(int i : res) cout << i << ' ';
    cout << '\n';
  }
}

Tester's Solution (Full solution)

#include <bits/stdc++.h>
#define endl '\n'

#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back

using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (int)2e5 + 42;
const int mod = (int)1e9 + 7;

int pw2[MAXN];
int pw(int x, int p) {
  int r = 1;
  while(p) {
    if(p % 2 == 1) r = r * 1ll * x % mod;
    x = x * 1ll * x % mod;
    p >>= 1;
  }

  return r;
}

int inv[MAXN], fact[MAXN], ifact[MAXN];

void prepare() {
  pw2[0] = 1;
  for(int i = 1; i < MAXN; i++) {
    pw2[i] = (2 * pw2[i - 1]) % mod;
  }

  fact[0] = 1;
  for(int i = 1; i < MAXN; i++) {
    fact[i] = fact[i - 1] * 1ll * i % mod;
  }

  ifact[MAXN - 1] = pw(fact[MAXN - 1], mod - 2);
  for(int i = MAXN - 2; i >= 0; i--) {
    ifact[i] = (i + 1) * 1ll * ifact[i + 1] % mod;
    inv[i + 1] = ifact[i + 1] * 1ll * fact[i] % mod;
  }
}

random_device rd;
mt19937_64 mt(rd());

struct node
{
  int sz, prior, id, rev;
  int num_pp, comp_sz;
  node *par, *pp, *l, *r;
  node() { id = 0; sz = 0; rev = 0; prior = 0; comp_sz = 0; par = nullptr; l = nullptr; r = nullptr; pp = nullptr; }
  node(int v) { id = v; num_pp = 0; comp_sz = 1; sz = 1; rev = 0; prior = mt(); l = nullptr; r = nullptr; par = nullptr; pp = nullptr; }
};

typedef node* pnode;

int size(pnode v) { return v ? v->sz : 0; }
int comp_size(pnode v) { return v ? v->comp_sz : 0; }

void push(pnode &t) {
  if(!t) return;
  if(t->rev) {
    swap(t->l, t->r);
    if(t->l) t->l->rev ^= 1;
    if(t->r) t->r->rev ^= 1;
    t->rev = 0;
  }
}

void pull(pnode &v) { 
  if(!v) return;

  push(v->l);
  push(v->r);

  v->par = nullptr;
  v->sz = size(v->l) + size(v->r) + 1; 
  v->comp_sz = comp_size(v->l) + comp_size(v->r) + 1 + v->num_pp;

  if(v->l) v->l->par = v;
  if(v->r) v->r->par = v;

  if(v->l && v->l->pp) v->pp = v->l->pp, v->l->pp = nullptr;
  if(v->r && v->r->pp) v->pp = v->r->pp, v->r->pp = nullptr;
}

void merge(pnode &t, pnode l, pnode r) {
  push(l), push(r);
  if(!l) { t = r; return; }
  if(!r) { t = l; return; }

  if(l->prior > r->prior)
    merge(l->r, l->r, r), t = l;
  else
    merge(r->l, l, r->l), t = r;

  pull(t);
}

void split(pnode t, pnode &l, pnode &r, int k, int add = 0) {
  push(t);
  if(!t) { l = nullptr; r = nullptr; return; }

  int idx = add + size(t->l);
  if(idx <= k)
    split(t->r, t->r, r, k, idx + 1), l = t;
  else
    split(t->l, l, t->l, k, add), r = t;

  pull(t);
}

pnode get_root(pnode t) { if(!t) return nullptr; while(t->par) t = t->par; return t; }

void pull_up(pnode t) {
  pnode tmp = t;
  while(tmp != nullptr) {
    tmp->comp_sz = 1 + tmp->num_pp + comp_size(tmp->l) + comp_size(tmp->r);
    tmp = tmp->par;
  }
}

pnode remove_right(pnode t) {
  pnode rt = t;
  int pos = size(rt->l);
  if(rt->rev) pos = size(rt) - pos - 1;
  while(rt->par) {
    if(rt->par->r == rt) pos += size(rt->par->l) + 1;
    if(rt->par->rev) pos = size(rt->par) - pos - 1;
    rt = rt->par;
  }

  pnode l, r, pp = rt->pp;
  rt->pp = nullptr;
  split(rt, l, r, pos);

  l->pp = pp;
  t->num_pp += comp_size(r);
  if(r) r->pp = t;
  pull_up(t);

  return l;
}	

pnode remove_left(pnode t) {
  // happens only in cut
  pnode rt = t;

  int pos = size(rt->l);
  if(rt->rev) pos = size(rt) - pos - 1;
  while(rt->par) {
    if(rt->par->r == rt) pos += size(rt->par->l) + 1;
    if(rt->par->rev) pos = size(rt->par) - pos - 1;
    rt = rt->par;
  }

  pnode l, r;
  assert(rt->pp == nullptr);
  split(rt, l, r, pos - 1);
  return r;
}

pnode merge_trees(pnode u, pnode t) {
  u = get_root(u);
  t = get_root(t);

  if(t->pp) {
    t->pp->num_pp -= comp_size(t);
    pull_up(t->pp);
  }

  t->pp = nullptr;
  merge(u, u, t);
  return u;
}

struct link_cut_tree {
  pnode ver[MAXN];

  pnode access(pnode t) {
    t = remove_right(t);
    while(t->pp) {
      pnode u = t->pp;
      u = remove_right(u);
      t = merge_trees(u, t);
    }

    return t;
  }

  pnode find_root(pnode u) {
    u = access(u);
    push(u); while(u->l) u = u->l, push(u);
    access(u);
    return u;
  }

  void make_root(pnode u) {
    u = access(u);
    u->rev ^= 1;
    push(u);
  }

  void link(pnode u, pnode w) {
    make_root(u);
    access(w);
    merge_trees(w, u);
  }

  void cut(pnode p) {
    access(p);
    remove_left(p);
  }

  /// normal functions
  void init(int c) { for(int i = 0; i <= c; i++) ver[i] = new node(i); }

  int root(int u) { return find_root(ver[u])->id; }
  int comp_size(int u) { return ::comp_size(get_root(find_root(ver[u]))); }

  void link(int u, int v) { link(ver[u], ver[v]); }
  void cut(int u) { cut(ver[u]); }

  void make_root(int u) { make_root(ver[u]); }
} t;

int n, a[MAXN], b[MAXN];

void read() {
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < n; i++) cin >> b[i];
}

int bonus_edge[MAXN];
int answer, cnt_oct, cnt_oct_same;

bool match(int i) {
  int r1 = t.root(a[i]);
  int r2 = t.root(b[i]);

  if(bonus_edge[r1] != -1 && bonus_edge[r2] != -1) {
    return false;
  } else if(r1 != r2) {
    if(bonus_edge[r1] == -1) answer = answer * 1ll * inv[t.comp_size(r1)] % mod;
    else cnt_oct--, cnt_oct_same -= (a[bonus_edge[r1]] == b[bonus_edge[r1]]);

    if(bonus_edge[r2] == -1) answer = answer * 1ll * inv[t.comp_size(r2)] % mod;
    else cnt_oct--, cnt_oct_same -= (a[bonus_edge[r2]] == b[bonus_edge[r2]]);

    //cout << "add edge " << a[i] << " " << b[i] << endl; 
    t.link(a[i], b[i]);

    int bonus = bonus_edge[r1] == -1 ? bonus_edge[r2] : bonus_edge[r1];
    bonus_edge[r1] = -1;
    bonus_edge[r2] = -1;
    bonus_edge[t.root(a[i])] = bonus; 

    if(bonus == -1) {
      answer = answer * 1ll * t.comp_size(a[i]) % mod; 
    } else {
      cnt_oct++;
      cnt_oct_same += a[bonus] == b[bonus];
    }

    return true;
  } else {
    assert(bonus_edge[r1] == -1);
    bonus_edge[r1] = i;
    cnt_oct_same += a[i] == b[i];
    cnt_oct++;
    answer = answer * 1ll * inv[t.comp_size(r1)] % mod; 
    return true;
  }
}

void solve() {
  vector<int> sorted;
  for(int i = 0; i < n; i++) sorted.pb(a[i]);
  for(int i = 0; i < n; i++) sorted.pb(b[i]);
  sort(ALL(sorted));
  sorted.erase(unique(ALL(sorted)), sorted.end());
  for(int i = 0; i < n; i++) {
    a[i] = L_B(ALL(sorted), a[i]) - sorted.begin();
    b[i] = L_B(ALL(sorted), b[i]) - sorted.begin();
  }

  t.init(SZ(sorted));
  for(int i = 0; i < SZ(sorted); i++) {
    bonus_edge[i] = -1; 
  }

  int r = 0;
  answer = 1;
  cnt_oct = 0;
  cnt_oct_same = 0;
  for(int l = 0; l < n; l++) {
    while(r < n && match(r)) r++;

    cout << (answer * 1ll * pw2[cnt_oct - cnt_oct_same] % mod) << " ";

    int rt = t.root(a[l]);
    if(bonus_edge[rt] == l) {
      bonus_edge[rt] = -1;
      answer = answer * 1ll * t.comp_size(rt) % mod;
      cnt_oct_same -= a[l] == b[l];
      cnt_oct--;
    } else {
      int to_add = bonus_edge[rt], whole_size = t.comp_size(rt);
      bonus_edge[rt] = -1;

      if(to_add == -1) answer = answer * 1ll * inv[whole_size] % mod;
      else {
        cnt_oct_same -= a[to_add] == b[to_add];
        cnt_oct--;
      }

      t.make_root(a[l]);
      t.cut(b[l]);
      
      answer = answer * 1ll * t.comp_size(a[l]) % mod;
      answer = answer * 1ll * t.comp_size(b[l]) % mod;
      if(to_add != -1) assert(match(to_add) == true);
    }
  }

  cout << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  prepare();

  int T;
  cin >> T;
  while(T--) {
    read();
    solve();
  }
  return 0;
}

Nishant's solution

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

#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>

const int MOD = 1e9+7;
const int N = 1e5 + 10;
int inv[N];

int res = 1;

struct dsu_save {
    int v, szv, cyv, u, szu , cyu;

    dsu_save() {}

    dsu_save(int _v, int _szv, int _cyv , int _u, int _szu, int _cyu)
        : v(_v), szv(_szv),cyv(_cyv), u(_u), szu(_szu) ,cyu(_cyu) {}
};

int get_ans(int cc,int ss)
{
    if(cc == 0) return ss;
    else return cc;
}

struct dsu_with_rollbacks 
{
    vector<int> p,sz,cyc;
    stack<dsu_save> op;

    dsu_with_rollbacks() {}

    dsu_with_rollbacks(int n) 
    {
        p.resize(n);
        sz.resize(n);
        cyc.resize(n);
        
        for (int i = 0; i < n; i++) {
            p[i] = i;
            sz[i] = 1;
            cyc[i] = 0;
        }
    }

    int find_set(int v) {
        return (v == p[v]) ? v : find_set(p[v]);
    }
    
    bool tryy(int u,int v)
    {
        int a = find_set(v);
        int b = find_set(u);
        
        if(cyc[a] > 0 && cyc[b] > 0) return 0;
        return 1;
    }

    bool unite(int v, int u) 
    {
        int a = find_set(v);
        int b = find_set(u);
        
        if(cyc[a] > 0 && cyc[b] > 0) return 0;
        
        op.push(dsu_save(a, sz[a], cyc[a], b, sz[b] , cyc[b]));
        
        if(a == b)
        {
            res = (res*inv[sz[a]])%MOD;
            
            if(u == v) cyc[a] = 1;
            else cyc[a] = 2;
            
            res = (res*get_ans(cyc[b],sz[b]))%MOD;
            
            return 1;
        }
        
        res = (res*inv[get_ans(cyc[a],sz[a])])%MOD;
        res = (res*inv[get_ans(cyc[b],sz[b])])%MOD;
        
        if(sz[a] > sz[b]) swap(a,b);
        p[a] = b;
        sz[b]+=sz[a];
        cyc[b] = max(cyc[a],cyc[b]);
        
        res = (res*get_ans(cyc[b],sz[b]))%MOD;
        
        return 1;
    }

    void rollback() 
    {
        if (op.empty()) return;
        
        dsu_save x = op.top();
        op.pop();
        
        int gg = find_set(x.v);
        res = (res*inv[get_ans(cyc[gg],sz[gg])])%MOD;
        
        p[x.v] = x.v;
        sz[x.v] = x.szv;
        cyc[x.v] = x.cyv;
        p[x.u] = x.u;
        sz[x.u] = x.szu;
        cyc[x.u] = x.cyu;
        
        res = (res*get_ans(x.cyv,x.szv))%MOD;
        if(x.u != x.v) res = (res*get_ans(x.cyu,x.szu))%MOD;
    }
};

struct Upd {
  int type, a, b;
};

void solve()
{
    int n;
    cin >> n;
    
    int a[n],b[n];
    f(i,n) cin >> a[i];
    f(i,n) cin >> b[i];
    
    int c[n+n];
    
    f(i,n) c[i] = a[i],c[i+n] = b[i];
    sort(c,c+n+n);
    f(i,n) a[i] = lower_bound(c,c+n+n,a[i]) - c;
    f(i,n) b[i] = lower_bound(c,c+n+n,b[i]) - c;
    
    res = 1;
    dsu_with_rollbacks go(n+n+5);
    int ptr = 0;

    vector<Upd> upds, tmp[2];
    int last_id = -1;
    
    f(i,n)
    {
        while(ptr < n && go.unite(a[ptr],b[ptr])) 
        {
            upds.push_back(Upd({1,a[ptr],b[ptr]}));
            ptr++;
        }
        
        cout << res << ' ';

        if (upds.back().type == 1) {
          while (upds.size() > 0) {
            auto upd = upds.back();
            upds.pop_back();
            go.rollback();
            tmp[upd.type].push_back(upd);
            if (tmp[0].size() == tmp[1].size())
              break;
          }
          if (tmp[0].empty()) {
            assert(upds.empty());
            for (auto& upd : tmp[1]) {
              upd.type = 0;
              go.unite(upd.a, upd.b);
            }
            swap(tmp[1], upds);
          } else {
            for (int z : {1, 0}) {
              for (; tmp[z].size(); tmp[z].pop_back()) {
                auto upd = tmp[z].back();
                go.unite(upd.a, upd.b);
                upds.push_back(upd);
              }
            }
          }
        }

        assert(upds.back().type == 0);
        upds.pop_back();
        go.rollback();

    }

    cout << '\n';
}

signed main()
{
    inv[0] = inv[1] = 1;
    
    for(int i=2;i<N;i++) 
        inv[i] = inv[MOD%i]*(MOD - MOD/i) % MOD;
    
    fast;
    
    int t = 1;
    
    cin >> t;
    
    while(t--)
        
    solve();
}

VIDEO EDITORIAL:

[run_timeterror]

I also did it using queue undoing trick and btw a really fantastic question.