Problem: expl-ore-ation_ch1 (2021 round3)

**Note: Chapters [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D2) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D3) are strictly more difficult versions of this problem, with differences highlighted in bold. Solutions to later chapters can be directly applied to solve earlier ones.**

Facebulk Inc. is a mining company who just released its latest performance reports. Backed by strong earnings, the company is now seeking to grow its infrastructure by surveying ore samples across \(T\) new sites using its patented robotics tech.

A given site has been excavated after much drilling and blasting, forming a rectangular pit that's \(R\) rows long (numbered from \(1\) to \(R\)) by \(C\) columns wide (numbered from \(1\) to \(C\)) by \(10^9\) cm deep. The pit consists of a grid of \(R*C\) platforms, where the platform at row \(i\) and column \(j\) (denoted as platform \((i, j)\)) is at height \(H_{i,j}\) cm from the bottom of the pit.

Unfortunately, there's a forecast of heavy rain — rainwater is about to start slowly flooding the pit. The water level is initially at height \(0\), and will eventually fill up the entire pit at height \(10^9\) cm.

Your supervisor wants \(R*C\) ore samples to be collected and analyzed, one from each platform, based on the following humidity requirements: the sample from platform \((i, j)\) is *only* worthwhile if collected at some point while the water level is strictly between \(S_{i,j}\) and \(S_{i,j}+1\) cm.

In an attempt to accomplish this, you'll dispatch \(0\) or more remote-control robots before it starts to rain, each at an initial platform of your choice. Multiple robots may occupy the same platform. At any point in time, you can command any robot at some platform \((i, j)\) to move to an adjacent platform (any platform \((i', j')\) such that \(|i-i'| + |j-j'| = 1\)), or to collect an ore sample from its current platform. Rainwater will flood slowly enough that the robots have time to execute an arbitrary number of commands before water increases from any height of \(x\) to \(x+1\) cm.

If a robot is ever on platform \((i, j)\) while the water level is greater than or equal to \(H_{i,j}\) (either because the robot moved to that platform or because the water level increased while the robot was present on it), the robot will short circuit and stop executing any more commands.

Let \(X\) be the maximum number of desired ore samples which can be collected, and let \(Y\) be the minimum number of robots which must be dispatched to collect that many samples. Please compute \(X\) and \(Y\).


# Constraints

\(1 \le T \le 55\)
\(1 \le R, C \le 1{,}000{,}000\)
\(R*C \le 1{,}000{,}000\)
\(1 \le H_{i,j} \le 10^9\)
\(0 \le S_{i,j} < 10^9\)

The sum of \(R*C\) across all sites is at most \(5{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of sites to be surveyed. For each site, there is first a line containing \(2\) space-separated integers, \(R\) and \(C\). Then, \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers, \(H_{i,1..C}\). Then, another \(R\) lines follow, the \(i\)th of which consists of \(C\) space-separated integers \(S_{i,1..C}\).


# Output

For the \(i\)th site, print a line containing *"Case #i: "* followed by \(2\) space-separated integers, the maximum number of desired ore samples which can be collected, and the minimum number of robots which must be dispatched to collect that many samples.


# Sample Explanation

At the first site, if you dispatch a single robot at platform \((1, 2)\), it can wait there until the water level exceeds \(98\) cm, collect an ore sample from platform \((1, 2)\), move to platform \((1, 3)\), wait until the water level exceeds \(99\) cm, and finally collect an ore sample from platform \((1, 3)\). No matter how many robots are dispatched, they cannot collect an ore sample from platform \((1, 1)\) after the water level exceeds \(98\) cm (as the platform would already be flooded), meaning that \(1\) robot collecting \(2\) samples is the best that can be done.

At the second site, a single robot dispatched anywhere can move around and collect samples from all \(6\) platforms before the water level reaches \(1\) cm.

At the third site, no samples can be collected before all \(6\) platforms get flooded.

At the fourth site, samples at platforms \((1, 1)\) and \((1, 3)\), but not by a single robot.


Sample input:
6
1 3
98 99 100
98 98 99
2 3
5 2 4
3 2 1
0 0 0
0 0 0
2 3
5 2 4
3 2 1
5 5 5
5 5 5
2 3
5 2 4
3 2 1
3 3 3
3 3 3
2 3
5 2 4
3 2 1
1 2 2
2 1 3
5 20
3308 1437 4018 2971 1243 3361 3246 2698 2738 987 3955 1653 3888 955 4788 350 4560 4422 2066 3542
40 3734 1789 3672 4538 4549 3885 512 1272 4530 2713 3582 1328 3902 3886 3349 1351 1950 4761 755
906 3101 3289 1741 927 2172 2931 2833 3146 4489 2536 1151 3788 2562 1540 3844 149 428 237 28
1754 4444 3020 3571 2770 1417 4680 2289 1202 45 3509 3856 2936 2310 1428 4051 4565 4357 4884 2380
2076 1593 1342 2066 2151 2657 3734 1982 2616 989 2365 1480 4245 279 4012 2435 3709 1892 2579 2969
2082 2722 762 649 272 2024 2776 303 3637 4524 3423 3555 2809 2697 3859 2143 2158 286 1358 1321
3525 4306 2486 691 3942 1317 224 1143 4540 916 1957 1447 3207 2640 2650 4215 1715 3852 2398 3688
4926 1649 3197 289 4479 897 434 1499 4490 4380 4993 970 2600 2305 2305 411 1219 4237 3984 1239
4159 3617 305 483 115 2403 1225 2264 2695 3460 3824 4245 4304 2425 4658 951 3335 2872 1813 283
2711 3369 2757 4184 2437 4086 1818 1628 402 1953 3811 2257 1836 3545 996 1555 491 800 4387 3256


Sample output:
Case #1: 2 1
Case #2: 6 1
Case #3: 0 0
Case #4: 2 2
Case #5: 4 2
Case #6: 54 11


Solution: We'll simulate the entire process in reverse, with the water level decreasing and gradually uncovering all of the platforms while rock samples need to be collected at certain times. As we go, we'll want to maintain a set of groups of platforms such that all platforms in each group are currently reachable from one another, which we can represent as a [disjoint-set data structure](https://en.wikipedia.org/wiki/Disjoint-set_data_structure). Each pair of adjacent platforms \((i_1, j_1)\) and \((i_2, j_2)\) will become directly reachable from one another when the water level reaches height \(\min(H_{i_1,j_1}, H_{i_2,j_2})\). Based on this, we can assemble a list of \(O(RC)\) events for when pairs of adjacent platforms will become reachable, combine them with another \(RC\) events for when samples need to be collected, and process all of these events in non-increasing order of height. When adjacent platforms become reachable, we'll merge their respective groups together.

When processing a sample collection event for platform \((i, j)\), the sample cannot be collected if \(S_{i,j} \ge H_{i,j}\). Otherwise, it can be, with the question being how to allocate robots to collect it and other samples. We can take a greedy approach involving reusing a previously-allocated robot to handle the sample if possible, and otherwise allocating a new robot to it. To do so, we'll augment our disjoint-set data structure to store a flag per group for whether or not a robot has already been allocated to that group, the idea being that a robot allocated to a group can also handle any more samples within the same group. When merging groups together, the resulting group is considered to have an allocated robot if at least one of the two existing groups did. All that remains is checking and potentially setting this flag for each sample's platform's group.

The most expensive part of this algorithm is sorting of the events, taking \(O(RC \log(RC))\) time.

Other solutions also exist, such as different implementations of the general concept described above (for example, by replacing the disjoint-set data structure with a gradual flood fill of which cells are reachable by robots allocated so far).

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/w6Xvy0c876o)


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

const int LIM = 1000002;

struct UnionFind {
  int N;
  vector<int> root, rank;
  vector<bool> hasR;

  UnionFind(int _N): N(_N), root(_N), rank(_N, 0), hasR(_N, false) {
    for (int i = 0; i < N; i++) {
      root[i] = i;
    }
  }

  int find(int i) {
    if (root[i] != i) {
      root[i] = find(root[i]);
    }
    return root[i];
  }

  void merge(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) {
      return;
    }
    if (rank[i] > rank[j]) {
      swap(i, j);
    }
    root[i] = j;
    hasR[j] = hasR[j] || hasR[i];
    if (rank[i] == rank[j]) {
      rank[j]++;
    }
  }
};

int R, C, N;
int H[LIM];
vector<tuple<int, int, int>> A;

pair<int, int> solve() {
  A.clear();
  // Input.
  cin >> R >> C;
  N = R * C;
  for (int i = 0, j; i < N; i++) {
    cin >> H[i];
    if ((j = i - C) >= 0) {  // Up.
      A.emplace_back(-min(H[i], H[j]), i, j);
    }
    if (i % C > 0 && (j = i - 1) >= 0) {  // Left.
      A.emplace_back(-min(H[i], H[j]), i, j);
    }
  }
  for (int i = 0, s; i < N; i++) {
    cin >> s;
    A.emplace_back(-s, -1, i);
  }
  // Process edges/samples in non-increasing order of elevation.
  UnionFind U(N);
  sort(A.begin(), A.end());
  pair<int, int> ans{0, 0};
  for (const auto &t : A) {
    int h = -get<0>(t), a = get<1>(t), b = get<2>(t);
    if (a < 0) {  // Sample.
      if (H[b] <= h) {  // Impossible to collect.
        continue;
      }
      ans.first++;  // Collect it.
      b = U.find(b);
      if (!U.hasR[b]) {  // Add new robot if necessary.
        U.hasR[b] = true;
        ans.second++;
      }
      continue;
    }
    U.merge(a, b);  // Edge.
  }
  return ans;
}

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