# March 20, 2019 Single Round Match 753 Editorials

## Div II Easy: KerimJavati

For each l like L, it takes 2 * distance(‘a’, L) + 1 seconds for Kerim to type it.

Time complexity is O(text.size())

public static int howLong(String text) {   int ans = 0;   for (char c : text.toCharArray())       ans += 1 + 2 * (c - 'a');   return ans;}

## Div II Medium: CCChecker2

Simulate the process, several things to check:

• All elements in arrays int[] moveStartRow, int[] moveStartCol, int[] moveDestRow, int[] moveDestCol, must be between 1 and n.
• Never two cubes could take the same position.
• Cubes must arrive at their destination at the end.
• Moves must be valid.

Time complexity is O(moves * m), could be improved to O(moves + m + n ^ 2).

public static String check(int n, int[] startRow, int[] startCol, int[] destRow, int[] destCol, int[] moveStartRow, int[] moveStartCol, int[] moveDestRow, int[] moveDestCol){   int m = startCol.length, moves = moveStartCol.length;   if (checkArray(n, moveDestRow) || checkArray(n, moveStartRow) || checkArray(n, moveDestCol) || checkArray(n, moveStartCol))       return "invalid";   for(int i = 0; i < moves; i++) {       int id = -1;       for(int j = 0; j < m; j++)           if(startRow[j] == moveStartRow[i] && startCol[j] == moveStartCol[i])               id = j;       for(int j = 0; j < m; j++)           if(startRow[j] == moveDestRow[i] && startCol[j] == moveDestCol[i])               return "invalid";       if(abs(moveStartCol[i] - moveDestCol[i]) + abs(moveStartRow[i] - moveDestRow[i]) != 1)           return "invalid";       if(id == -1)           return "invalid";       startCol[id] = moveDestCol[i];       startRow[id] = moveDestRow[i];   }   for(int j = 0; j < m; j++)       if(startRow[j] != destRow[j] || startCol[j] != destCol[j])           return "invalid";   return "valid";}private static boolean checkArray(int n, int[] destRow) {   for(int x : destRow)       if(x < 1 || x > n)           return true;   return false;}

## Div II Hard: MaxCutFree

Consider bridges, they form a forest graph, solve the problem for each tree of this forest independently. Now the problem is converted to find the maximum independent set in a tree (a set that no two vertices out of that are adjacent). Use Dynamic Programming. For each vertex, keep two values:

• Close: Answer for the subtree of this vertex.
• Open: Answer for the subtree of this vertex if you don’t choose this vertex.

public static class Edge{   int v, u;   public Edge(int v, int u) {       this.v = v;       this.u = u;   }}public static class Dp{   int open, close;   public Dp(int open, int close) {       this.open = open;       this.close = close;   }}public static final int maxn = (int) 3e5 + 17;static int edge[], comp[], h[], gp, d[], cnt[];static boolean bl[];static boolean seen[];static ArrayList<ArrayList<Integer> > g = new ArrayList<>();static Edge e[] = new Edge[maxn];static int hi(int v, int p){   int ret = h[v];   seen[v] = true;   int parEdge = 0;   for(int i : g.get(v)){       int u = edge[i] ^ v;       if(!seen[u]){           h[u] = h[v] + 1;           int t = hi(u, v);           if(t == h[u])               bl[i] = true;           ret = min(ret, t);       }       else if(u != p && u != v)           ret = min(ret, h[u]);       else if (u == p)           parEdge++;   }   if(parEdge > 1)       ret = min(ret, h[v] - 1);   return ret;}static void hello(int v){   cnt[ comp[v] = gp ]++;   for(int i : g.get(v)){       int u = edge[i] ^ v;       if(!bl[i] && comp[u] == -1)           hello(u);   }}static void build_tree(int m){   for(int i = 0; i < m; i++)       if(bl[i]) {           g.get(e[i].v).add(e[i].u);           g.get(e[i].u).add(e[i].v);       }}static Dp dfs(int v, int p){   seen[v] = true;   Dp ans = new Dp(0, 1);   for(int u : g.get(v))       if(u != p) {           Dp child = dfs(u, v);           ans.open += child.close;           ans.close += child.open;       }   ans.close = max(ans.close, ans.open);   return ans;}static public int solve(int n, int a[], int b[]){   int m = a.length;   edge = new int[maxn];   comp = new int[maxn];   h = new int[maxn];   d = new int[maxn];   cnt = new int[maxn];   bl = new boolean[maxn];   seen = new boolean[maxn];   comp = new int[n];   g = new ArrayList<>();   for(int i = 0; i < n; i++)       g.add(new ArrayList<>());   Arrays.fill(comp, -1);   for(int i = 0; i < m; i++) {       int v = a[i];       int u = b[i];       //System.err.println(v + " " + u);       e[i] = new Edge(v, u);       edge[i] = v ^ u;       g.get(v).add(i);       g.get(u).add(i);   }   for(int i = 0; i < n; i++)       if(!seen[i])           hi(i, -1);   for(int i = 0; i < n; i++)       if(comp[i] == -1){           hello(i);           cnt[gp] = cnt[gp] - 1;           gp++;       }   g = new ArrayList<>(n);   for(int i = 0; i < n; i++)       g.add(new ArrayList<>());   build_tree(m);   Arrays.fill(seen, false);   int ans = 0;   for(int i = 0; i < n; i++)       if(!seen[i])           ans += dfs(i, -1).close;   return ans;

## MojisBag:

Keep trie of numbers at each moment and two elements that maximize the answer, e1, and, e2.

• If number x added to the bag, at first try to update the answer and if updated, update e1 and e2. Then add x to trie. Time complexity: O(log MAXV).
• If number x become removed from the bag, remove it from trie. If it’s e1 or e2, clear trie, insert elements one by one again and update the answer. Time complexity: O(q * log MAXV) if x is e1 or e2, O(log MAXV) otherwise.

What do you think about time complexity? The point is because queries are generated randomly, the probability of that x equals to e1 or e2 is 2 / n. So the mathematical expectation of time complexity is: q * (2 / q * q * log MAXV + (q – 2) / q * log MAXV) = q log (q).

static class Node {   int cnt, index;   Node left;   Node right;   public Node() {       cnt = 0;       left = null;       right = null;       index = -1;   }}static class Pair {   int key, value;   public Pair(int key, int value) {       this.key = key;       this.value = value;   }}static Node root = new Node();static void insert(int value, int index) {   Node cur = root;   cur.cnt++;   for (int i = 31; i >= 0; i--) {       if (((1 << i) & value) == 0) {           if (cur.left == null) {               cur.left = new Node();           }           cur = cur.left;       }       else {           if (cur.right == null) {               cur.right = new Node();           }           cur = cur.right;       }       cur.cnt++;   }   cur.index = index;}static void remove(int value) {   Node cur = root;   root.cnt--;   for (int i = 31; i >= 0; i--) {       if (((1 << i) & value) == 0) {           cur = cur.left;       }       else {           cur = cur.right;       }       cur.cnt--;   }}static Pair getMax(int value) {   Node cur = root;   if(root.cnt == 0)       return new Pair(-1, 0);   int res = 0;   for (int i = 31; i >= 0; i--) {       int add = 0;       if (((1 << i) & value) == 0) {           if (cur.right != null && cur.right.cnt != 0) {               cur = cur.right;               add++;           }           else {               cur = cur.left;           }       }       else {           if (cur.left != null && cur.left.cnt != 0) {               cur = cur.left;               add++;           }           else {               cur = cur.right;           }       }       res = 2 * res + add;   }   return new Pair(cur.index, res);}public static int maximumXor(int q, int base, int add, int rate) {   final int Mod = (int) 1e9 + 7;   int ans = 0;   int a[] = new int[q];   int y[] = new int[q];   int z[] = new int[q];   boolean deleted[] = new boolean[q];   int cur = 0, sz = 0, cera = -1, cerb = -1;   for(int i = 0; i < q; i++){       cur = (int) (((long) cur * base + add) % Mod);       if(cur % rate != 0){           //System.out.println("+ " + cur);           Pair tmp = getMax(cur);           if(ans < tmp.value){               ans = tmp.value;               cera = sz;               cerb = tmp.key;           }           insert(cur, sz);           a[sz++] = cur;       }       else if(sz > 0){           int remIndex = cur % sz;           //System.out.println("- " + remIndex + " (" + a[remIndex] + ")");           if(!deleted[remIndex]) {               deleted[remIndex] = true;               remove(a[remIndex]);               if (remIndex == cera || remIndex == cerb) {                   root = new Node();                   ans = 0;                   cera = cerb = -1;                   for (int j = 0; j < sz; j++)                       if(!deleted[j]){                           Pair tmp = getMax(a[j]);                           if (ans < tmp.value) {                               ans = tmp.value;                               cera = j;                               cerb = tmp.key;                           }                           insert(a[j], j);                       }               }           }       }       y[i] = ans;       //System.out.println("= " + ans);   }   z[0] = y[0];   for(int i = 1; i < q; i++)       z[i] = (int) (((long) z[i - 1] * base + y[i]) % Mod);   return z[q - 1];}

## MojiDeletes:

Consider xor of range [L, R] be X, we are searching for some i (L <= i <= R), such that maximizes the value X ^ a[i];

We know how to find value maximizing xor in a trie (like problem 706D from codeforces). Let’s keep a trie for each prefix of the array, name the trie constructed from numbers in the range [0, i], t[i]. For each node, keep count of the number of nodes in its subtree. Now, for answering query [L, R], we can subtract values written on nodes in t[L] from t[R + 1], from this trie we can find the answer.

One problem remains. Time complexity is now O(n ^ 2 * log MAXV). The key idea is to use persistent trie instead of constructing n tries, it reduces the time complexity to O(n * log MAXV).

private final static int Mod = (int) 1e9 + 7;static class PersistentTrie{   int node;   int left[],right[],data[];   int maxN=20000001;   PersistentTrie()   {       node=0;//0 is dummy node       left=new int[maxN];       right=new int[maxN];       data=new int[maxN];   }   /**Finds the number in this trie which maximizes xor with val.    * @param n is the root number of the version which is being queried.    * @param val is a 32 bit positive integer.    * @return A value from trie which maximizes the xor with val.    */   int queryMax(int n, int m, int val)   {       int ans=0;       int y=1<<30;       while(y>0)       {           if((val&y)>0)//current bit is 1           {               if(data[left[m]] - data[left[n]]!=0)               {                   ans+=y;                   n = left[n];                   m = left[m];               }               else if(data[right[m]] - data[right[n]]!=0) {                   n = right[n];                   m = right[m];               }               else                   return ans;           }           else//current bit is 0           {               if(data[right[m]] - data[right[n]]!=0)               {                   n=right[n];                   m = right[m];                   ans+=y;               }               else if(data[left[m]] - data[left[n]]!=0)               {                   m = left[m];                   n=left[n];               }               else                   return ans;           }           y>>=1;       }       return ans;   }   /**    * Insert the value val in the trie version with root n.    * @param n Root number of trie version in which insertion is to be done.    * @param val Value to be inserted.    * @param y pow(2,30) in this case.    * @return    */   int insert(int n,int val,int y)//returns the root of new trie   {       //create a new node       int cur=++node;       if(y==0)       {           data[cur]=1+data[n];           return cur;       }       if((val&y)>0)//current bit is 1       {           left[cur]=left[n];           data[cur]=data[left[n]];           int r=insert(right[n],val,y>>1);           right[cur]=r;           data[cur]+=data[r];       }       else       {           right[cur]=right[n];           data[cur]=data[right[n]];           int l=insert(left[n],val,y>>1);           left[cur]=l;           data[cur]+=data[l];       }       return cur;   }}public static long maximumXor(int n, int q, int base, int add, int qBase, int qAdd){   PersistentTrie pt = new PersistentTrie();   int a[] = new int[n + 1];   int ps[] = new int[n + 1];   int root[] = new int[n + 1];   root[0] = ps[0] = a[0] = 0;   for(int i = 1; i <= n; i++) {       a[i] = (int) (((long) a[i - 1] * base + add) % Mod);       root[i] = pt.insert(root[i - 1], a[i], 1 << 30);       ps[i] = ps[i - 1] ^ a[i];       //System.out.print(String.valueOf(a[i]) + ' ');   }   //System.out.println();   int cur = 0;   long ans = 0;   while(q-- > 0){       cur = (int) (((long) cur * qBase + qAdd) % n);       int l = cur;       cur = (int) (((long) cur * qBase + qAdd) % n);       int r = cur;       if(r < l) {           int t = l;           l = r;           r = t;       }       ans += pt.queryMax(root[l], root[r + 1], ps[r + 1] ^ ps[l]);       //System.out.println(String.valueOf(l + 1) + ", " + String.valueOf(r + 1) + " = " + pt.queryMax(root[l], root[r + 1], ps[r + 1] ^ ps[l]));   }   return ans;}

Harshit Mehta

Sr. Community Evangelist

categories & Tags

Close