Problem: table_flipping (2021 finals)

Tabitha is tired of tricky Hacker Cup problems, and is hosting a table flipping after-party for the finalists to let out some steam. Her party will be held with finalists distributed across \(T\) rooms.

A given room has \(N\) tables (numbered from \(1\) to \(N\)), with one finalist at each table. Each table \(i\) is represented as an axis-aligned rectangle of positive area on a 2D plane, with bottom-left vertex at \((X_i, Y_i)\), a width of \(W_i\), and a height of \(H_i\). No two tables overlap (intersect with positive area).

Finalists will take turns flipping their tables in one of the \(4\) cardinal directions by reflecting the rectangle across an edge. Table \(i\) must be flipped in direction \(D_i\) (`"U"` if the table is to be flipped over its upper edge, `"D"` for its lower edge, `"L"` for its left edge, or `"R"` for its right edge). Finalists must flip their tables one-by-one, i.e., no two tables may be flipped at the exact same time.

Every finalist knows which direction each table must be flipped, and do not wish to interfere with each other. Tabitha would like to know if there exists some permutation in which the tables can be flipped, such that at no time do any two tables overlap (intersect with positive area).

# Constraints

\(1 \le T \le 70\)
\(1 \le N \le 300{,}000\)
\(0 \le X_i, Y_i \le 500{,}000{,}000\)
\(1 \le W_i, H_i \le 500{,}000{,}000\)
\(D_i \in \{\)`"U"`, `"D"`, `"L"`, `"R"`\(\}\)

The sum of \(N\) across all test cases is at most \(3{,}000{,}000\).

# Input

Input begins with a single integer \(T\), the number of rooms. For each room, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains \(4\) space-separated integers, \(X_i\), \(Y_i\), \(W_i\), and \(H_i\), followed by a space-separated character \(D_i\).

# Output

For the \(i\)th room, print a line containing *"Case #i: "* followed by `"YES"` if there exists a permutation of tables as described above, or `"NO"` otherwise.

# Sample Explanation

In the first room, the two tables (along with their flipping directions) are arranged as follows:

{{PHOTO_ID:616805819746914|WIDTH:420}}

Flipping the left table first would result in it overlapping with the right table. On the other hand, if the right table is flipped first, then the left table can be validly flipped as well, leaving the tables looking as follows:

{{PHOTO_ID:382533823663612|WIDTH:420}}

In the second room, the left table is to be flipped to the right instead. No matter which order the tables are flipped in, they will overlap with one another at some point.

The third room is arranged as follows:

{{PHOTO_ID:462323098803710|WIDTH:420}}
  
No matter which order the tables are flipped in, they will touch but not overlap with one another.
  
The fourth room is arranged as follows, and has no valid table-flipping order:

{{PHOTO_ID:1268827100291056|WIDTH:320}}



Sample input:
7
2
0 0 10 10 R
15 5 10 10 R
2
0 0 10 10 R
15 5 10 10 L
2
0 0 10 10 R
30 5 10 10 L
4
0 0 1 3 U
0 4 3 1 R
4 2 1 3 D
2 0 3 1 L
4
6 5 2 1 L
7 1 1 3 U
4 2 1 6 U
1 6 2 1 R
5
6 6 2 3 D
11 7 1 3 D
2 8 3 5 R
7 2 3 3 R
6 9 4 1 R
15
23 11 3 1 L
11 19 1 4 R
3 26 1 5 D
10 19 1 3 R
18 2 4 1 L
17 2 1 1 D
24 4 3 1 L
17 3 1 5 R
23 5 1 1 U
18 3 4 3 D
10 18 1 1 U
12 19 4 2 D
23 4 1 1 U
23 6 4 2 R
4 26 5 1 L


Sample output:
Case #1: YES
Case #2: NO
Case #3: YES
Case #4: NO
Case #5: YES
Case #6: NO
Case #7: YES


Solution: For each table, we know which direction it is going to be flipped over, so we can create two rectangle objects for each table. The rectangle of the starting position will be denoted as \(S\), and the rectangle for the ending position will be denoted as \(E\). We can coordinate compress all the values across these rectangles to make the problem slightly easier.

First, we can check if any of the tables overlap in their ending states. A standard line sweep can be done over all of the \(E\) rectangles in one dimension, with a segment tree of ongoing rectangles maintained over the other dimension. If any overlap is found, the answer for the test case is `"NO"`.

The tables must start in a valid position, and now we know that they also end in a valid position. We must now check if there is an ordering where they stay valid at each step. Let’s create a graph \(G\) with \(N\) nodes, one for each table. Let there be a directed edge from table \(A\) to table \(B\) if flipping over table \(A\) would cause it to intersect with a non-flipped over table \(B\) (\(E\) rectangle from \(A\) intersects with \(S\) rectangle from \(B\)). This means that rectangle \(B\) must be flipped over before rectangle \(A\). If this graph is acyclic then an ordering exists such that the tables never overlap at any step. The ordering would be the reverse of the topological sort based on how edges are defined above. This leads to a simple \(O(N^2)\) solution. Construct the graph above naively by checking every pair of rectangles and adding the edge if it exists, then run a cycle check or topological sorting on the graph. There are \(N\) vertices and \(N^2\) edges so any cycle check or topo sort algorithm will take \(O(V+E) = O(N^2)\).

Due to the properties of the graph, it is actually possible to perform a cycle check on this graph on the order of number of vertices, and not edges. Consider the following interactive problem:

There is a graph \(G\) with \(V\) vertices and \(E\) edges. There are no self-loops or multi-edges. You are not given the graph, only the number of vertices \(V\) (labeled \(1\) to \(V\)). You may perform \(2\) queries on this graph:

Query 1) Remove vertex with label \(X\) from the graph. This will remove all incoming and outgoing edges from this node.

Query 2) Ask for any outgoing edge from vertex \(X\). If vertex \(X\) contains any outgoing edges, this will return the vertex of any of them at random. If vertex \(X\) is already removed or contains no outgoing edges, this will return \(-1\).

Your task is to determine whether the original graph (before removing any vertices) contains a cycle in no more than \(4*V\) queries. 

This can be solved via the following algorithm:
```
  void dfs(int n) {
    seen[n] = true;
    while (!hasCycle) {
      int to = query2(n);
      if (to == -1) break;
      else if (seen[to]) hasCycle = true;
      else dfs(to);
    }
    query1(n);
  }

  boolean hasCycle = false;
  boolean[] seen = new boolean[N];
  for (int i = 0; i < N; i++) if (!seen[i]) dfs(i);
```

Query 1 is performed on each node at most once amounting to \(N\) queries. For query 2, if a returned node has previously been visited then a cycle is found and the process ends. Otherwise we visit that node, so query 2 is performed at most once for each time a node is entered, and then potentially once more on each node when no more edges are found. The total amount of queries is at most \(N + N + N + 1\). 

Since this DFS only follows edges of the original graph, it is easy to see that if no cycle exists in the original graph, no false positive will be found. If a cycle exists, this solution will find it. Consider the initial path of nodes the DFS visits right before calling query 1 on any node:

\(A \to B \to C \to D \to E\)

We know each of these nodes are distinct because if there were any duplicates, a cycle would be found. We also know that node \(E\) has no outgoing edges in the original graph since no node has been destroyed yet and query 1 is about to be called (if \(E\) had an outgoing edge to \(A-D\), then this cycle would get found and the process would end). Since node \(E\) has no outgoing edges, we can guarantee that it is not part of any cycle in the graph. Node \(E\) then gets safely removed and now the stack looks like

\(A \to B \to C \to D\)

Now we will take any outgoing edge from \(D\) (if any exist) until we reach another point where a node has no more outgoing edges:

\(A \to B \to C \to D \to F \to G\)

If we do not reach a point where a node has no more outgoing edges, that means a cycle will get reached and be found.

If none of the nodes reachable from \(A\) (including \(A\) itself) are part of a cycle, then this function will eventually remove all of these nodes from the graph and finish without finding a cycle. Then search then starts from another node (if available).

Let’s consider the case where one of the reachable nodes is part of a cycle. Let’s consider the stack right after the first node that is part of a cycle is reached:

\(A \to B \to C \to D\)

Here \(D\) is the first node on the stack that is part of a cycle. It has been shown that nodes are only removed when they are not part of any cycle, and if we call DFS on node \(X\) then eventually all nodes reachable from \(X\) including \(X\) itself will be removed if they are not part of a cycle. This means that we will certainly find and reach any outgoing edges from \(D\) to nodes that also belong to a cycle containing \(D\). This logic continues until we eventually reach a node with an outgoing edge to \(D\) itself. Once we process this edge, we find the cycle and the process ends. 

Now that we’ve shown we can do cycle section on a graph with these two queries, the original problem needs to be translated to this new problem. We can create a data structure to store/remove rectangles and query for some rectangle if there is another rectangle that intersects with it, and return one of them. 

Create a segment tree across the \(X\) values of the rectangles. Each node stores an implicit segment tree across \(Y\) values. When adding a rectangle, for its left \(X\) and right \(X\) boundaries, for all \(\log(N)\) nodes including that \(X\), set the index of the lower \(Y\) to be the value of the upper \(Y\). To support insertion and deletion of multiple rectangles with the same lower \(Y\) without disrupting each other, one approach is to give each rectangle a unique lower \(Y\) "key" rather than compressing them all to exactly the same one.

Add all the \(S\) rectangles to this data structure. Now to check if a node has any outgoing edges, query from left X to right X for the corresponding \(E\) rectangle of that node. For each \(\log(N)\) nodes in this range, query the max from \([0, \) upper \(Y]\) and check if that value is \(\ge\) lower \(Y\). If this is true, then there is some intersecting rectangle and we can return the index of it by storing extra data.

There is one case this will not find: If the intersecting \(S\) rectangle starts at a smaller \(X\) and ends at a larger \(X\) than the \(E\) rectangle we are checking, the \(\log(N)\) nodes in the segment tree will not find this rectangle. If we rotate the problem and also check by having a segment tree across \(Y\) values and implicit segment tree across \(X\), then it will be instead found in the other structure. Since \(E\) rectangles are formed by reflecting across its corresponding \(S\) rectangle, then if there were any case such that an \(E\) rectangle is completely contained inside an \(S\) rectangle (without touching its borders) then there would be an intersection between the two \(S\) rectangles and this would be found during the sweep line.

Each insertion into and deletion from this data structure takes \(O(\log^2(N))\) time, and querying for an intersecting rectangle also takes \(O(\log^2(N))\) time. Since these queries are called \(O(N)\) times in the algorithm described above, the overall runtime of this solution is \(O(N \log^2(N))\).


Code: #include <algorithm>
#include <cstring>
#include <iostream>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

const int LIM = 300003;
using pii = pair<int, int>;
#define x first
#define y second

struct Compressor {
  int N;
  vector<pii> V;

  Compressor() {}
  Compressor(vector<pii> _V) {
    V = _V;
    comp();
  }

  void insert(pii v) {
    V.push_back(v);
  }

  void comp() {
    sort(V.begin(), V.end());
    N = unique(V.begin(), V.end()) - V.begin();
    V.resize(N);
  }

  int get(pii v) {
    return lower_bound(V.begin(), V.end(), v) - V.begin();
  }
};

const int TLIM = 2100000;
const int ZERO_VAL = 0;
const int ZERO_LAZY = 0;

struct MaxRangeSegTree {
  static void update_value(int &a, int v, int r1, int r2) { a += v; }
  static void update_lazy(int &a, int v, int r1, int r2) { a += v; }
  static int join_values(int v1, int v2) { return max(v1, v2); }

  int N, sz;
  int tree[TLIM];
  int lazy[TLIM];

  MaxRangeSegTree() {}
  MaxRangeSegTree(int _N) { init(_N); }

  void init(int _N) {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1)
      ;
    clear();
  }

  void clear() {
    for (int i = 0; i < (sz << 1); i++) {
      tree[i] = ZERO_VAL;
      lazy[i] = ZERO_LAZY;
    }
  }

  void propagate(int i, int r1, int r2) {
    int v = lazy[i];
    lazy[i] = ZERO_LAZY;
    update_value(tree[i], v, r1, r2);
    if (i < sz) {
      int m = (r1 + r2) >> 1, c1 = i << 1, c2 = c1 + 1;
      update_lazy(lazy[c1], v, r1, m);
      update_lazy(lazy[c2], v, m + 1, r2);
    }
  }

  void comp(int i) {
    int c1 = i << 1, c2 = c1 + 1;
    tree[i] = join_values(tree[c1], tree[c2]);
  }

  int query(int a, int b, int i = 1, int r1 = 0, int r2 = -1) {
    if (r2 < 0) {
      a = max(a, 0);
      b = min(b, sz - 1);
      if (a > b) {
        return ZERO_VAL;
      }
      r2 = sz - 1;
    }
    propagate(i, r1, r2);
    if (a <= r1 && r2 <= b) {
      return tree[i];
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    int res = ZERO_VAL;
    if (a <= m) {
      res = join_values(res, query(a, b, c, r1, m));
    }
    if (b > m) {
      res = join_values(res, query(a, b, c + 1, m + 1, r2));
    }
    return res;
  }

  void update(int a, int b, int v, int i = 1, int r1 = 0, int r2 = -1) {
    if (r2 < 0) {
      a = max(a, 0);
      b = min(b, sz - 1);
      if (a > b) {
        return;
      }
      r2 = sz - 1;
    }
    if (r2 < 0) {
      r2 = sz - 1;
    }
    propagate(i, r1, r2);
    if (a <= r1 && r2 <= b) {
      update_lazy(lazy[i], v, r1, r2);
      propagate(i, r1, r2);
      return;
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    if (a <= m) {
      update(a, b, v, c, r1, m);
    }
    if (b > m) {
      update(a, b, v, c + 1, m + 1, r2);
    }
    propagate(c, r1, m);
    propagate(c + 1, m + 1, r2);
    comp(i);
  }
};

const pii NONE{-1, -1};

struct MaxElemSegTree {
  pii join_values(pii v1, pii v2) { return max(v1, v2); }

  int N, sz;
  vector<pii> tree;

  MaxElemSegTree() {}
  MaxElemSegTree(int _N) { init(_N); }

  void init(int _N) {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1)
      ;
    clear();
  }

  void clear() {
    tree.clear();
    tree.resize(sz << 1, NONE);
  }

  void comp(int i) {
    int c1 = i << 1, c2 = c1 + 1;
    tree[i] = join_values(tree[c1], tree[c2]);
  }

  pii query(int a, int b, int i = 1, int r1 = 0, int r2 = -1) {
    if (r2 < 0) {
      a = max(a, 0);
      b = min(b, sz - 1);
      if (a > b) {
        return NONE;
      }
      r2 = sz - 1;
    }
    if (a <= r1 && r2 <= b) {
      return tree[i];
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    pii res = NONE;
    if (a <= m) {
      res = join_values(res, query(a, b, c, r1, m));
    }
    if (b > m) {
      res = join_values(res, query(a, b, c + 1, m + 1, r2));
    }
    return res;
  }

  void update_one(int i, pii p) {
    i += sz;
    tree[i] = p;
    while (i > 1) {
      i >>= 1;
      comp(i);
    }
  }
};

struct NestedSegTree {
  int N, sz;
  bool has_init_keys;
  vector<int> keys[TLIM];
  MaxElemSegTree T[TLIM];

  NestedSegTree() {}
  NestedSegTree(int _N) { init(_N); }

  void init(int _N) {
    N = _N;
    for (sz = 1; sz < N; sz <<= 1)
      ;
    has_init_keys = false;
  }

  void init_keys() {
    for (int i = sz; i < sz + N; i++) {
      auto &k = keys[i];
      sort(k.begin(), k.end());
      k.resize(unique(k.begin(), k.end()) - k.begin());
      T[i].init(k.size());
    }
    for (int i = sz - 1; i >= 1; i--) {
      auto &k = keys[i], &c1 = keys[i << 1], &c2 = keys[(i << 1) + 1];
      int a = 0, b = 0;
      while (a < c1.size() || b < c2.size()) {
        if (a < c1.size() && b < c2.size() && c1[a] == c2[b]) {
          k.push_back(c1[a++]);
          b++;
        } else if (b == c2.size() || (a < c1.size() && c1[a] < c2[b])) {
          k.push_back(c1[a++]);
        } else {
          k.push_back(c2[b++]);
        }
      }
      T[i].init(k.size());
    }
    has_init_keys = true;
  }

  pii query_max_up_to_k(int a, int b, int k, int i = 1, int r1 = 0, int r2 = -1) {
    if (r2 < 0) {
      a = max(a, 0);
      b = min(b, sz - 1);
      if (a > b) {
        return NONE;
      }
      r2 = sz - 1;
    }
    if (a <= r1 && r2 <= b) {
      k = lower_bound(keys[i].begin(), keys[i].end(), k + 1) - keys[i].begin() - 1;
      return T[i].query(0, k);
    }
    int m = (r1 + r2) >> 1, c = i << 1;
    pii res = NONE;
    if (a <= m) {
      res = max(res, query_max_up_to_k(a, b, k, c, r1, m));
    }
    if (b > m) {
      res = max(res, query_max_up_to_k(a, b, k, c + 1, m + 1, r2));
    }
    return res;
  }

  void update_one(int i, int k, pii p) {
    i += sz;
    if (!has_init_keys) {
      keys[i].push_back(k);
      return;
    }
    while (i >= 1) {
      T[i].update_one(
        lower_bound(keys[i].begin(), keys[i].end(), k) - keys[i].begin(), p
      );
      i >>= 1;
    }
  }
};

int N;
pair<pii, pii> A[LIM], B[LIM];
int Axx[LIM], Axy[LIM];
int lowerX[3 * LIM], lowerY[3 * LIM];
bool visit[LIM];
NestedSegTree STX, STY;

void update_A_rect(int i, bool ins) {
  STX.update_one(A[i].x.x, Axy[i], ins ? make_pair(A[i].y.y, i) : NONE);
  STX.update_one(A[i].y.x, Axy[i], ins ? make_pair(A[i].y.y, i) : NONE);
  STY.update_one(A[i].x.y, Axx[i], ins ? make_pair(A[i].y.x, i) : NONE);
  STY.update_one(A[i].y.y, Axx[i], ins ? make_pair(A[i].y.x, i) : NONE);
}

int get_A_rect_for_B_rect(int i) {
  pii p = STX.query_max_up_to_k(B[i].x.x, B[i].y.x, B[i].y.y);
  if (p.x >= B[i].x.y) {
    return p.y;
  }
  p = STY.query_max_up_to_k(B[i].x.y, B[i].y.y, B[i].y.x);
  if (p.x >= B[i].x.x) {
    return p.y;
  }
  return -1;
}

bool rec(int i) {
  visit[i] = true;
  for (;;) {
    int j = get_A_rect_for_B_rect(i);
    if (j < 0) {
      break;
    }
    if (visit[j]) {
      return true;
    }
    if (rec(j)) {
      return true;
    }
  }
  update_A_rect(i, 0);
  return false;
}

bool solve() {
  Compressor cx, cy;
  // Input, and compute flipped rectangles.
  cin >> N;
  for (int i = 0; i < N; i++) {
    char c;
    cin >> A[i].x.x >> A[i].x.y >> A[i].y.x >> A[i].y.y >> c;
    B[i] = A[i];
    switch (c) {
      case 'U': B[i].x.y += A[i].y.y; break;
      case 'D': B[i].x.y -= A[i].y.y; break;
      case 'L': B[i].x.x -= A[i].y.x; break;
      case 'R': B[i].x.x += A[i].y.x; break;
    }
    A[i].y.x += A[i].x.x;
    A[i].y.y += A[i].x.y;
    B[i].y.x += B[i].x.x;
    B[i].y.y += B[i].x.y;
    cx.insert({A[i].x.x, i});
    cx.insert({A[i].y.x, i}),
    cx.insert({B[i].x.x, i});
    cx.insert({B[i].y.x, i});
    cy.insert({A[i].x.y, i});
    cy.insert({A[i].y.y, i});
    cy.insert({B[i].x.y, i});
    cy.insert({B[i].y.y, i});
  }
  // Compress coordinates.
  cx.comp(), cy.comp();
  auto V = cx.V;
  for (int i = 0; i < V.size(); i++) {
    lowerX[i] = (i == 0 || V[i - 1].x != V[i].x) ? i : lowerX[i - 1];
  }
  V = cy.V;
  for (int i = 0; i < V.size(); i++) {
    lowerY[i] = (i == 0 || V[i - 1].x != V[i].x) ? i : lowerY[i - 1];
  }
  for (int i = 0; i < N; i++) {
    A[i].x.x = cx.get({A[i].x.x, i});
    A[i].x.y = cy.get({A[i].x.y, i}),
    A[i].y.x = cx.get({A[i].y.x, i});
    A[i].y.y = cy.get({A[i].y.y, i});
    B[i].x.x = cx.get({B[i].x.x, i});
    B[i].x.y = cy.get({B[i].x.y, i}),
    B[i].y.x = cx.get({B[i].y.x, i});
    B[i].y.y = cy.get({B[i].y.y, i});
    // Remember exact (unique) lower coordinates.
    Axx[i] = A[i].x.x, Axy[i] = A[i].x.y;
    // Round coordinates up to value boundaries (with exclusive upper
    // coordinates).
    A[i].x.x = lowerX[A[i].x.x];
    B[i].x.x = lowerX[B[i].x.x];
    A[i].x.y = lowerY[A[i].x.y];
    B[i].x.y = lowerY[B[i].x.y];
    A[i].y.x = lowerX[A[i].y.x] - 1;
    B[i].y.x = lowerX[B[i].y.x] - 1;
    A[i].y.y = lowerY[A[i].y.y] - 1;
    B[i].y.y = lowerY[B[i].y.y] - 1;
  }
  // Check for any overlap between final tables via line sweep.
  vector<tuple<int, int, int, int>> E;
  for (int i = 0; i < N; i++) {
    E.emplace_back(B[i].x.y, 1, B[i].x.x, B[i].y.x);
    E.emplace_back(B[i].y.y + 1, -1, B[i].x.x, B[i].y.x);
  }
  sort(E.begin(), E.end());
  MaxRangeSegTree ST(cx.V.size());
  for (auto e : E) {
    ST.update(get<2>(e), get<3>(e), get<1>(e));
    if (ST.query(0, cx.V.size() - 1) > 1) {
      return false;
    }
  }
  // Initialize segment trees of initial tables, over x and y coordinates.
  STX = NestedSegTree(cx.V.size());
  STY = NestedSegTree(cy.V.size());
  for (int j : {0, 1}) {
    if (j) {  // Initialize keys second time around.
      STX.init_keys();
      STY.init_keys();
    }
    for (int i = 0; i < N; i++) {
      // Set up keys first time around, then perform actual updates.
      update_A_rect(i, 1);
    }
  }
  // Search for cycles via DFS.
  memset(visit, 0, sizeof visit);
  for (int i = 0; i < N; i++) {
    if (!visit[i]) {
      if (rec(i)) {
        return false;  // Cycle found.
      }
    }
  }
  return true;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << (solve() ? "YES" : "NO") << endl;
  }
  return 0;
}