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.

Now, dp[root].close is the answer.

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;
}