Notifications

Good job! You’re all caught up

Join challenges and check your notification settings if you don’t receive notifications. We’re actively adding new notifications. Read our blog post for more info

Notifications
TOSCA Editor - Web Application Wireframe Challenge (1)
Dismiss notification
Earlier Dismiss All
You have no more notifications

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


Harshit Mehta

Sr. Community Evangelist



UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds