Problem: balance_sheet (2022 round2)

Metal Platforms, Inc. (a.k.a. Metal), formerly a mining company, now offers a service to facilitate sheet metal sales. It has \(N\) clients, where client \(i\) wants to buy *only on* day \(A_i\) for \(\$X_i\) per sheet, and sell *only on* a strictly later day \(B_i\) for \(\$Y_i\) per sheet.

Client \(i\) can sell to client \(j\) if \(B_i = A_j\), and if client \(j\) is buying for a *strictly higher* price than what client \(i\) is selling for, i.e. if \(X_j > Y_i\). If Metal facilitates the sale, they earn a profit of \(\$(X_j - Y_i)\).

A *path* is any ordered sequence of clients where each client can sell to the next. A path's profit is the total profit that Metal would make if a single sheet were theoretically sold along it.

Metal would like to know the total profit across the \(K\) most profitable paths (or across all distinct paths if there are fewer than \(K\)). Since this may be large, please print it modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 35\)
\(1 \le N, K \le 1{,}000{,}000\)
\(1 \le N * K \le 1{,}000{,}000\)
\(1 \le A_i < B_i \le 10^9\)
\(1 \le X_i, Y_i \le 10^9\)

The sum of \(N\) over all test cases is at most \(6{,}000{,}000\).
The sum of \(N*K\) over all cases is at most \(20{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing two space-separated integers \(N\) and \(K\). Then, \(N\) lines follow, the \(i\)th of which contains four space-separated integers \(A_i\), \(B_i\), \(X_i\), and \(Y_i\).


# Output Format

For the \(i\)th test case, output a single line containing `"Case #i: "` followed by a single integer, the total profit of the \(K\) most profitable paths, modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

The first case is depicted below, with buy prices in green and sell prices in red. The figure on the right outlines all potential sales, along with how much profit Metal would make.

{{PHOTO_ID:5415230591886835|WIDTH:700}}

The valid paths are:

- \(P_1 = [1, 2]\) with profit \(\$25 - \$20 = \$5\).
- \(P_2 = [1, 2, 4]\) with profit \((\$25 - \$20) + (\$35 - \$30)\) \(= \$10\).
- \(P_3 = [1, 2, 4, 6]\) with profit \((\$25 - \$20) + (\$35 - \$30) + (\$45 - \$20)\) \(= \$35\).
- \(P_4 = [2, 4]\) with profit \(\$5\).
- \(P_5 = [2, 4, 6]\) with profit \(\$5 + (\$45 - \$20)\) \(= \$30\).
- \(P_6 = [4, 6]\) with profit \(\$45 - \$20 = \$25\).
- \(P_7 = [5, 6]\) with profit \(\$45 - \$15 = \$30\).

Note that sales from clients \(3\) to \(4\) and clients \(6\) to \(7\) are not possible, since the buyers' prices must be strictly higher than the sellers'. Since there are fewer than \(K=10\) paths, the answer is just the sum of profits of all paths, equal to \(\$5 + \$10 + \$35 + \$5 + \$30 + \$25 + \$30 = \$140\).

The second case is the same as the first, except we're only interested in the top \(6\) most profitable paths, so we must exclude either \(P_1\) or \(P_4\) for a total profit of \(\$135\).

In the third case, no sales are possible, so we simply report \(\$0\).

In the fourth case, the only possible path is \([2, 1]\), with a profit of \(\$30 - \$20 = \$10\).


Sample input:
4
8 10
1 2 10 20
2 4 25 30
1 4 45 40
4 5 35 20
1 5 10 15
5 6 45 30
6 7 30 40
8 9 80 90
8 6
1 2 10 20
2 4 25 30
1 4 45 40
4 5 35 20
1 5 10 15
5 6 45 30
6 7 30 40
8 9 80 90
2 1
1 2 10 20
3 4 30 40
2 1
2 3 30 40
1 2 10 20


Sample output:
Case #1: 140
Case #2: 135
Case #3: 0
Case #4: 10


Solution: At a glance, the problem seems to be asking us for the \(K\) longest paths, which is NP-hard on general graphs. It can actually be observed that the input must form a DAG, for which there are polynomial time solutions (e.g. by negating the edge weights and solving for the shortest path). Unfortunately, such solutions have running time proportional to the number of edges, of which there can be \(\mathcal{O}(N^2)\) here (for example, if \(N/2\) clients can all sell to the other \(N/2\)).

Instead, we'll try a completely different approach. First consider the problem of finding just the top \(K = 1\) path profit. Let \(P_i\) be the maximum profit that can arise from a path starting at client \(i\). Note that \(P_i = \max(P_j + X_j - Y_i)\) over all other clients \(j\) such that \(B_i = A_j\) and \(X_j > Y_i\). The critical observation is that each \(P_i\) only depends on days \(B_i\) and later, and only depends on buyers with prices greater than \(Y_i\).

We'll iterate over the days in reverse. For each day, we'll iterate over all its buyers/sellers in non-increasing order of price, while maintaining the largest value \(v = P_j + X_j\) across buyers seen so far. For each buyer, we'll update \(v\). For each seller \(i\), we'll set \(P_i = \max(0, v - Y_i)\). Once all the days and buy/sell events per day have been sorted, this processing takes \(\mathcal{O}(N)\) time. Finally, the top \(1\) path profit is the \(\max(P_i)\) across all possible starting clients \(i\).

Now generalizing to the top \(K > 1\) paths, let each \(P_i = [P_{i,1}, P_{i,2}, \ldots, ]\) be a list of the top \(K\) largest profits from distinct paths starting at seller \(i\). Then:

\[ P_i = \text{top}K\left( \,\bigcup_{j \text{ s.t. } B_i=A_j,\,X_j > Y_i} \left[ P_{j,1} + X_j - Y_i, P_{j,2} + X_j - Y_i, \ldots \right] \right) \]

where \(\bigcup\) is the union of lists (multisets) with duplicates allowed. Another way to interpret this: if there are several top paths starting at buyer \(j\), and a sale \(i \to j\) is possible, then we can prepend each path by \(i\) to get a new distinct path starting with that sale.

Again we can process all events sorted by descending days and price. For each day, we start a new running list \(V\) of the top \(K\) values of \(P_{j,k} + X_j\) across all buyers \(j\) and their path lists so far. For each seller \(i\), we merge \(P_i\) with the top \(K\) values of \([v - Y_i \text{ s.t. } v \in V]\). Finally, the answer is the top \(K\) profits across the union of all \(P_i\) lists.

At each buy/sell event, we'll need to merge two lists of length up to \(K\). As long as we make sure that lists are always sorted, merging be done in \(\mathcal{O}(K)\) time and space. As there are \(2N\) events which first need to be sorted, the overall running time is \(\mathcal{O}(N \log(N) + NK)\). Merging can also be handled with data structures like heaps and binary search trees, leading to a higher but still acceptable overall running time of \(\mathcal{O}(N \log(N) + NK \log (K))\).

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=8atOEXlqXFw)


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

const int LIM = 1000005;
const int MOD = 1000000007;
using LL = long long;
using vll = vector<LL>;

struct event {
  int id;
  int day;
  int price;
  char type;

  bool operator<(const event &e) const {
    if (day != e.day) {
      return day > e.day;
    }
    return price > e.price;
  }
};

// Merges two lists already sorted in reverse, trimmed to K elements.
// Optionally add a constant c2 to each element of v2 in the result.
vll merge(const vll &v1, const vll &v2, int K, LL c2 = 0) {
  vll res;
  int i = 0, j = 0, sz1 = v1.size(), sz2 = v2.size();
  while (i < sz1 && j < sz2 && (int)res.size() < K) {
    if (v1[i] >= v2[j] + c2) {
      res.push_back(v1[i++]);
    } else {
      res.push_back(v2[j++] + c2);
    }
  }
  while (i < sz1 && (int)res.size() < K) {
    res.push_back(v1[i++]);
  }
  while (j < sz2 && (int)res.size() < K) {
    res.push_back(v2[j++] + c2);
  }
  return res;
}

int solve() {
  int N, K;
  cin >> N >> K;
  vector<event> E;
  for (int i = 0, a, b, x, y; i < N; i++) {
    cin >> a >> b >> x >> y;
    E.push_back({i, a, x, 'B'});
    E.push_back({i, b, y, 'S'});
  }
  sort(E.begin(), E.end());
  int prevday = -1;
  vector<vll> P(N, {0});
  vll V;
  for (const event &e : E) {
    if (prevday != e.day) {
      V.clear();
    }
    if (e.type == 'B') {
      V = merge(V, P[e.id], K, e.price);
    } else {
      vll V2;
      for (LL v : V) {
        if (v > e.price) {
          V2.push_back(v - e.price);
        }
      }
      P[e.id] = merge(P[e.id], V2, K);
    }
    prevday = e.day;
  }
  V.clear();
  for (int i = 0; i < N; i++) {
    V = merge(V, P[i], K);
  }
  LL res = 0;
  for (LL v : V) {
    res = (res + v) % MOD;
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}