🏆 Meta Hacker Cup 2021 — Final Round: Table Flipping

Difficulty: Hard Topic: Computational Geometry, Rectangle Intersection, Constraint Propagation 📄 View original problem statement

Problem Summary

Tabitha is hosting a table-flipping after-party. There are N tables in a room, each represented as an axis-aligned rectangle with a direction (L/R/U/D) indicating which way it will flip.

Each table i has a bottom-left corner (x_i, y_i), a width w_i, and a height h_i, plus a flip direction d_i. When a table flips:

• L (Left): The table slides/flips to the left by its width. New position: (x_i − w_i, y_i)
• R (Right): Slides right. New position: (x_i + w_i, y_i)
• U (Up): Slides up. New position: (x_i, y_i + h_i)
• D (Down): Slides down. New position: (x_i, y_i − h_i)

After all tables flip simultaneously, determine if any two tables overlap in their final positions. Output “YES” if no overlaps, “NO” if there are overlaps.

Understanding the Problem

Let’s trace Sample Case 1 (N=1, a single table):

1 table: (bottom=0, left=0, height=3, width=1) direction=L

After flip L: moves left by width=1 → new bottom-left = (-1, 0)
Single table never overlaps with itself → YES

For Case 3 (4 tables), after each table flips in its direction, the final positions must be non-overlapping:

Table 1: (6,5) w=2 h=1 → flip L → (4,5) w=2 h=1
Table 2: (7,1) w=1 h=3 → flip U → (7,4) w=1 h=3
Table 3: (4,2) w=1 h=6 → flip U → (4,8) w=1 h=6... wait
Table 4: (1,6) w=2 h=1 → flip R → (3,6) w=2 h=1

Expected: YES (no overlaps after flipping)

Step-by-Step Solution Guide

Step 1: Compute Final Positions

Each table’s flip is straightforward — it moves by exactly its own dimensions in one direction:

function flipTable(x, y, w, h, dir) {
  switch (dir) {
    case 'L': return { x: x - w, y, w, h };
    case 'R': return { x: x + w, y, w, h };
    case 'U': return { x, y: y + h, w, h };
    case 'D': return { x, y: y - h, w, h };
  }
}

💡 Why simple translation? “Table flipping” in real life is more complex, but the problem models it as a rigid translation — the table moves its own size in the flip direction. This is a common simplification in competitive programming.

Step 2: Detect Rectangle Overlaps

Two axis-aligned rectangles overlap if and only if they are NOT separated along either axis:

function rectanglesOverlap(r1, r2) {
  // r1 and r2: { x, y, w, h } — x,y is bottom-left corner
  const noOverlap =
    r1.x + r1.w <= r2.x ||  // r1 is fully to the left of r2
    r2.x + r2.w <= r1.x ||  // r2 is fully to the left of r1
    r1.y + r1.h <= r2.y ||  // r1 is fully below r2
    r2.y + r2.h <= r1.y;    // r2 is fully below r1
    return !noOverlap;
}

⚠️ Edge case: touching is not overlapping. Two rectangles that share only an edge (one’s right edge equals the other’s left edge) are NOT considered overlapping — the condition uses strict <= not <.

Step 3: Naive Check — All Pairs

function solve(tables) {
  // Compute final positions
  const finalPositions = tables.map(t => flipTable(t.x, t.y, t.w, t.h, t.dir));
  // Check all pairs
  const n = finalPositions.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (rectanglesOverlap(finalPositions[i], finalPositions[j])) {
        return 'NO';
      }
    }
  }
  return 'YES';
}

💡 Time complexity: O(N²) — checking all pairs. For small N (say ≤ 1000), this is fast enough. For the Final Round constraints (potentially N up to 100,000), we need a sweep line approach.

Step 4: Optimized Sweep Line for Large N

For large N, use a sweep line along the x-axis with an interval tree or coordinate-compressed segment tree on the y-axis:

function solveOptimized(finalRects) {
  // Create events: each rectangle generates two events (enter/exit along x)
  const events = [];
  for (let i = 0; i < finalRects.length; i++) {
    const { x, y, w, h } = finalRects[i];
    events.push({ x: x, type: 'enter', yLo: y, yHi: y + h, id: i });
    events.push({ x: x + w, type: 'exit', yLo: y, yHi: y + h, id: i });
  }
  events.sort((a, b) => a.x - b.x || (a.type === 'exit' ? -1 : 1));
  // Active set: rectangles currently "open" (entered but not exited)
  const active = new Map(); // id → rect
  for (const ev of events) {
    if (ev.type === 'enter') {
      // Check if this new rectangle overlaps with any active rectangle
      for (const [id, rect] of active) {
        if (intervalsOverlap(ev.yLo, ev.yHi, rect.yLo, rect.yHi)) {
          return 'NO';
        }
      }
      active.set(ev.id, ev);
    } else {
      active.delete(ev.id);
    }
  }
  return 'YES';
}
function intervalsOverlap(lo1, hi1, lo2, hi2) {
  return lo1 < hi2 && lo2 < hi1;
}

Step 5: Further Optimization — Segment Tree on Y

To avoid O(N) inner loop in the sweep, use a segment tree or interval treeon the y-axis:

class IntervalSet {
  constructor() {
    this.intervals = []; // sorted by y-start
  }
  addInterval(lo, hi) {
    // Check if any existing interval overlaps [lo, hi)
    for (const [eLo, eHi] of this.intervals) {
      if (lo < eHi && eLo < hi) return false; // overlap found
    }
    this.intervals.push([lo, hi]);
    this.intervals.sort((a, b) => a[0] - b[0]);
    return true;
  }
  removeInterval(lo, hi) {
    const idx = this.intervals.findIndex(iv => iv[0] === lo && iv[1] === hi);
    if (idx >= 0) this.intervals.splice(idx, 1);
  }
}

Complete JavaScript Solution

'use strict';

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
  let idx = 0;
  const T = parseInt(lines[idx++]);
  const results = [];
  for (let t = 1; t <= T; t++) {
    const N = parseInt(lines[idx++]);
    const tables = [];
    for (let i = 0; i < N; i++) {
      const parts = lines[idx++].split(' ');
      tables.push({
        x: parseInt(parts[0]),
        y: parseInt(parts[1]),
        w: parseInt(parts[2]),
        h: parseInt(parts[3]),
        dir: parts[4]
      });
    }
    results.push(`Case #${t}: ${solve(tables)}`);
  }
  console.log(results.join('\n'));
});
function flipTable({ x, y, w, h, dir }) {
  switch (dir) {
    case 'L': return { x: x - w, y, w, h };
    case 'R': return { x: x + w, y, w, h };
    case 'U': return { x, y: y + h, w, h };
    case 'D': return { x, y: y - h, w, h };
  }
}
function rectOverlap(a, b) {
  return a.x < b.x + b.w && b.x < a.x + a.w &&
         a.y < b.y + b.h && b.y < a.y + a.h;
}
function solve(tables) {
  const flipped = tables.map(flipTable);
  const n = flipped.length;
  // Sweep line approach for efficiency
  // Create enter/exit events sorted by x
  const events = [];
  for (let i = 0; i < n; i++) {
    const { x, y, w, h } = flipped[i];
    events.push([x, 0, y, y + h, i]);        // enter at x
    events.push([x + w, 1, y, y + h, i]);    // exit at x+w
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  // Active intervals in y, stored as sorted array
  const active = []; // { yLo, yHi, id }
  for (const [xVal, type, yLo, yHi, id] of events) {
    if (type === 0) {
      // Enter: check overlap with all active intervals
      for (const act of active) {
        if (yLo < act.yHi && act.yLo < yHi) {
          return 'NO'; // Overlap found
        }
      }
      active.push({ yLo, yHi, id });
    } else {
      // Exit: remove from active
      const idx = active.findIndex(a => a.id === id);
      if (idx >= 0) active.splice(idx, 1);
    }
  }
  return 'YES';
}

⏱️ Complexity Analysis

- Time (naive pairs) → O(N²): All pairs - Time (sweep line) → O(N² worst) / O(N log N avg): Sweep + active set - Time (optimal) → O(N log N): Sweep + segment tree - Space → O(N): Active set + events

Why sweep line helps: In practice, most rectangles don’t overlap, so the active set stays small. In the worst case (all rectangles stacked in the same x-range), it degrades to O(N²). A proper interval tree gives O(N log N) guaranteed.

Testing

// Case 1: 1 table → always YES (no pairs to compare)
console.assert(solve([{x:0, y:0, w:3, h:1, dir:'L'}]) === 'YES');

// Case 2: 2 tables flipping away from each other → YES
// Table 1 at (0,0) w=2 h=2 L → moves to (-2,0)
// Table 2 at (2,0) w=2 h=2 R → moves to (4,0)
// No overlap → YES
// Case 2b: 2 tables flipping into each other → NO
// Table 1 at (0,0) w=2 h=2 R → moves to (2,0)
// Table 2 at (2,0) w=2 h=2 L → moves to (0,0)
// They swap positions - they now fully overlap → NO
const overlapping = solve([
  {x:0, y:0, w:2, h:2, dir:'R'},
  {x:2, y:0, w:2, h:2, dir:'L'}
]);
console.assert(overlapping === 'NO');

Key Takeaways

• Rectangle overlap detection is a fundamental building block — memorize the condition: no overlap means separated on at least one axis (r1.x + r1.w <= r2.x || r2.x + r2.w <= r1.x || r1.y + r1.h <= r2.y || r2.y + r2.h <= r1.y).
• Sweep line algorithms convert 2D geometric problems into 1D problems by “sweeping” along one axis and maintaining a dynamic set of active intervals on the other axis.
• Strict vs non-strict inequalities matter: tables that only share an edge are NOT overlapping (strict < in the overlap condition), but this depends on the problem statement.
• Simulation problems in competitive programming often have the bulk of complexity in handling edge cases (touching rectangles, very small/large coordinates, collinear points).
• For Final Round problems, the stated time limit is tight — always think about whether O(N²) will pass or if you need O(N log N).

If you liked the article please clap and follow :) Thx and stay tuned 🚀 **Linkedin**