Problem: ssssss (2021 finals)

The mining company Facebulk Inc. has just rebranded to Metal Platforms Inc. In order to move fast with stable infrastructure, Metal has contracted the serpentine safety inspector, Solid Snake, to inspect \(T\) walls across its mine shafts.

A given wall has \(N\) vertical ladders (numbered from \(1\) to \(N\)) for Solid Snake to inspect. The wall can be represented as a 2D plane, with \(y=0\) being the lowest part of the wall, where it touches the ground. The \(i\)th ladder is positioned at x-coordinate \(i\), with its bottom at y-coordinate \(A_i\) and its top at y-coordinate \(B_i\).

Solid Snake is initially on the ground at coordinates \((0, 0)\) and hopes to inspect as many ladders as possible, ensuring they meet Solid Snake's Strict Serpentine Safety Specifications (SSSSSS), before finally returning to any position on the ground.

For example, the fourth sample case is depicted below:

{{PHOTO_ID:426120359137830|WIDTH:300}}

Solid Snake can perform the following actions:

1. If he's on the ground, he can freely move left and right, and can climb onto any ladder \(i\) which touches the ground at his current x-coordinate (i.e. \(A_i = 0\))
2. If he's on a ladder \(i\), he can:
    1. **Inspect** it (if he hasn't already inspected that ladder)
    2. Freely move up and down on that ladder — in other words, decrease his y-coordinate as low as \(A_i\) or increase it as high as \(B_i\) (while keeping his x-coordinate equal to \(i\))
    3. Freely move onto the ground if the ladder touches the ground (i.e. \(A_i = 0\))
    4. **Jump** horizontally to any other ladder \(j\) such that \(A_j \le y \le B_j\), where \(y\) is his current y-coordinate (note that he can jump directly to *any* such ladder, potentially passing by and ignoring other ladders along the way)

Please help Solid Snake determine the maximum number of ladders that he can inspect. Furthermore, determine the minimum number of jumps required for him to inspect that many ladders and then end up back on the ground at the end. Note that Solid Snake is allowed to intermediately return to the ground before he's done with all of his ladder inspections.


# Constraints

\(1 \le T \le 80\)
\(1 \le N \le 800{,}000\)
\(0 \le A_i < B_i \le 1{,}000{,}000{,}000\)

The sum of \(N\) across all walls is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of mine shaft walls to be inspected. For each wall, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which consists of \(2\) space-separated integers, \(A_i\) and \(B_i\).


# Output

For the \(i\)th wall, print a line containing *"Case #i: "* followed by \(2\) space-separated integers, the maximum number of ladders which Solid Snake can inspect and the minimum number of jumps required for him to do so.


# Sample Explanation

On the first wall, Solid Snake can move along the ground to each ladder, climb onto it, inspect it, and return to the ground, all without performing any jumps.

{{PHOTO_ID:525571725505702|WIDTH:240}}

On the second wall, Solid Snake cannot climb onto or inspect any ladders.

{{PHOTO_ID:247278897354943|WIDTH:240}}

On the third wall, one possible solution is for Solid Snake to:
- climb onto (and inspect) the third ladder at coordinates \((3, 0)\),
- move up to \((3, 10)\),
- jump to (and inspect) the second ladder at \((2, 10)\),
- move up to \((2, 15)\),
- jump to (and inspect) the first ladder at \((1, 15)\), and
- retrace his path by jumping to the second ladder, jumping to the third ladder, and finally returning to the ground.

Along the way, he will have inspected all \(3\) ladders while performing \(4\) jumps.

{{PHOTO_ID:436214534714219|WIDTH:240}}


Sample input:
5
3
0 3
0 2
0 1
2
1 3
1 2
3
11 19
10 20
0 10
4
0 2
2 3
4 5
2 3
12
17 39
41 52
25 27
0 11
57 64
8 32
36 43
58 61
12 20
43 54
52 55
11 22


Sample output:
Case #1: 3 0
Case #2: 0 0
Case #3: 3 4
Case #4: 3 3
Case #5: 10 12


Solution: If there are no ladders touching the ground, the answer is \(0\). Otherwise, those can all be inspected for free, and only the one with the largest \(B\) value is relevant.

We can perform a line sweep upwards over the ladders' endpoints (including the top of the tallest grounded ladder) while greedily constructing \(2\) "paths" of ladders simultaneously (one for the way up from the ground, and another for the way back down).

We'll maintain the ongoing ladders \(a\) and \(b\) for the \(2\) paths (not necessarily distinct, and both initially equal to the grounded ladder), the set \(U\) of ongoing ladders not yet used in either path (ordered by their \(B\) values, and initially empty), and the number of ladders inspected \(I\) and number of jumps used \(J\). We'll maintain an invariant that \(B_b\) is always greater than or equal to the \(B\) values of all other ongoing ladders not in \(U\) (including \(a\)). For convenience, we'll also assume that \(b\)'s top comes after \(a\)'s top in the line sweep (in case \(a \ne b\) and \(B_a = B_b\)).

When we encounter the bottom of a ladder, we'll simply add it to \(U\).

When we encounter the top of ladder \(i\), if \(i\) is in \(U\), then this is our last chance to visit it. So, we'll jump from ladder a to ladder \(i\) (leaving ladder \(b\) alone), removing \(i\) from \(U\), setting a to equal \(i\), and incrementing \(I\) and \(J\).

Either way, ladder \(i\)'s top being reached is then only relevant if \(i = a\) (and potentially also \(i = b\)), as we must jump to different ladder(s) to continue the path(s). One of the following situations will apply:

  1. If \(U\) is empty and \(i = a = b\), we should terminate the line sweep, as both paths have converged and there are no higher ladders to jump to.
  
  2. If \(U\) is empty but \(a \ne b\) (with \(i = a\)), we'll jump from ladder \(a\) to ladder \(b\) (necessary to attempt to continue \(a\)'s path or at least converge with \(b\)'s path), setting \(a\) to equal \(b\) and incrementing \(J\).

  3. Otherwise, if \(U\) is non-empty, we'll jump from ladder \(a\) to the ladder \(j\) in \(U\) with the smallest \(B\) value, removing \(j\) from \(U\), setting \(a\) to equal \(j\), and incrementing \(I\) and \(J\). If \(i = b\), then we'll repeat this process to similarly jump from ladder \(b\) to the ladder in \(U\) with the next-smallest \(B\) value (though if \(U\) has become empty, then we'll instead need to jump from ladder \(b\) to the new ladder \(a\)). We may need to then swap \(a\) and \(b\) to maintain the aforementioned invariant regarding ladder \(b\).
  
The time complexity of this algorithm is \(O(N \log(N))\).


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

const int LIM = 800008;

int N;
int A[LIM], B[LIM];

void solve() {
  vector<tuple<int, bool, int>> E;
  set<pair<int, int>> S;
  // Input, while finding tallest grounded ladder.
  int ng = 0, mg = -1;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    if (!A[i]) {
      ng++;
      if (mg < 0 || B[i] > B[mg]) {
        mg = i;
      }
    } else {
      E.emplace_back(A[i], 0, i);
      E.emplace_back(B[i], 1, i);
    }
  }
  // None grounded?
  if (ng == 0) {
    cout << "0 0" << endl;
    return;
  }
  // Sort endpoints (including tallest grounded ladder).
  E.emplace_back(B[mg], 1, mg);
  sort(E.begin(), E.end());

  // Line sweep.
  int ans1 = ng, ans2 = 0;
  int a = mg, b = mg;
  S.clear();
  for (auto e : E) {
    int i = get<2>(e);
    if (!get<1>(e)) {
      // Bottom of ladder i.
      S.emplace(B[i], i);
      continue;
    }
    // Top of ladder i.
    if (B[a] > B[b]) {
      swap(a, b);
    }
    auto it = S.find(make_pair(B[i], i));
    if (it != S.end()) {
      // Ladder i not used yet, so jump from ladder a to it.
      S.erase(it);
      ans1++;
      ans2++;
      a = i;
    } else if (i == b) {
      // Consider ladder i to be ladder a rather than b.
      swap(a, b);
    } else if (i != a) {
      // Ladder i is irrelevant.
      continue;
    }
    // Top of ladder a, so need to jump off of it.
    if (!S.empty()) {
      // There are other unused ladders, so jump from ladder a to the one with
      // lowest top.
      bool isB = a == b;
      a = S.begin()->second;
      S.erase(make_pair(B[a], a));
      ans1++;
      ans2++;
      if (isB) {
        // This is also ladder b, so repeat for it.
        if (!S.empty()) {
          // Jump from ladder b to another unused ladder.
          b = S.begin()->second;
          S.erase(make_pair(B[b], b));
          ans1++;
          ans2++;
        } else {
          // Jump from ladder b to the new ladder a.
          ans2++;
          b = a;
        }
      }
    } else if (a != b) {
      // Jump from ladder a to ladder b.
      ans2++;
      a = b;
    } else {
      // Nowhere else to go, so stop.
      break;
    }
  }
  cout << ans1 << " " << ans2 << endl;
}

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