Problem: timber (2020 quals)

Every year, millions of logs are sent floating downstream in [the great Canadian log drive](https://www.youtube.com/watch?v=7AheBqBk0iQ). But as every Canadian knows, you can't have a successful log drive without logs. The first step in the logging season is to fell a great number of trees, taking care not to pile the trees up in a way that will make them hard to move.

Eva has been assigned a section of forest with \(N\) trees standing in a row. Looking at them from the side and modeling the ground as a number line, the \(i\)th tree is at position \(P_i\) (measured in metres) and has a height of \(H_i\) metres. All of the trees are at distinct positions.

Each tree may be cut down such that it falls either to the left or to the right, or it may be left standing (it's important to farm trees sustainably). If the \(i\)th tree is cut down to the left, it will form a **timber interval** of \([P_i - H_i, P_i]\) on the ground, while if it is cut down to the right, it will form a timber interval \([P_i, P_i + H_i]\).

The trees that are cut down will be moved into a nearby river to begin their long journey to the mill. It's hard to move a tree that has another tree on top of it, so Eva will not cut down trees in a way that would cause the intersection of any pair of timber intervals to have positive length. It's fine however, and indeed desirable, for two timber intervals to share an endpoint in common. For example, one tree may be cut down to create a timber interval of \([a, b]\) and another may be cut down to create a timber interval of \([b, c]\). It's also fine for timber intervals to overlap with trees which have not been cut down. Uncut trees are essentially ignored.

A **combined timber interval** is an interval where each point within it is within at least one timber interval. For example, if you have timber intervals \([a, b]\) and \([b, c]\) (for any \(a < b < c\)), then \([a, c]\) is a combined timber interval. 

Eva would like to form the largest combined timber interval possible, as that represents a series of trees that can all be pushed into the river at once. Determine the maximum possible length that a combined timber interval could have if Eva cuts down trees optimally.

# Input

Input begins with an integer \(T\), the number of forest sections that Eva will work in. For each section, there is first a line containing the single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(P_i\) and \(H_i\).

# Output

For the \(i\)th section, print a line containing *"Case #i: "* followed by a single integer, the length of the largest possible combined timber interval that Eva can create in that section of forest.

# Constraints
\(1 \le T \le 90\)
\(1 \le N \le 800,000\)
\(-500,000,000 \le P_i \le 500,000,000\)
\(1 \le H_i \le 500,000,000\)

The sum of \(N\) across all forest sections is at most 4,000,000.

# Explanation of Sample

In the first case, if both trees are cut down such that they fall to the right, a combined timber interval of length 9 (between positions 0 and 9) will be formed.

In the second case, if the first tree falls to the right and the second falls to the left, they will similarly form a combined timber interval of length 9.

In the third case, no matter how the trees are cut down, their endpoints cannot coincide. Therefore, the longest possible combined timber interval consists of just the third tree being chopped down.


Sample input:
8
2
0 5
5 4
2
0 5
9 4
3
0 5
9 3
2 6
5
3 2
2 8
-4 5
8 5
1 4
6
-15 15
-9 9
-3 3
5 5
9 9
18 18
8
10 20
20 20
30 20
40 20
50 20
60 20
70 20
80 20
12
13 8
-14 5
2 19
33 10
-31 9
15 21
5 3
-22 16
-6 11
25 12
-40 24
21 18
2
-500000000 500000000
500000000 500000000


Sample output:
Case #1: 9
Case #2: 9
Case #3: 6
Case #4: 12
Case #5: 33
Case #6: 80
Case #7: 56
Case #8: 1000000000


Solution: We can observe that any combined timber interval must consist of 0 or more trees falling to the right followed by 0 or more trees falling to the left (with these two sequences of trees meeting at a common point in between).

Let \(R_p\) be the maximum length of a combined timber interval whose right endpoint is \(p\) and which consists only of trees cut down to the right. Let \(L_p\) similarly be the maximum length of a combined timber interval whose left endpoint is \(p\) and which consists only of trees cut down to the left. The answer (the maximum length of any combined timber interval) is then the maximum of \(( R_p + L_p )\) over all possible choices of \(p\).

What remains is computing these \(R\) and \(L\) values. We'll consider only the \(R\) values for now, with the \(L\) values computed in a very similar fashion (imagine that the trees are reversed on the number line, such that the \(i\)th tree is at position \(-P_i\) rather than \(P_i\)).

We'll use a dynamic programming approach, initially assuming that \(R_p = 0\) for each \(p\) and then increasing the \(R\) values as much as possible until we've considered all possible ways of increasing them. We'll first sort the trees in increasing order of position, and then iterate over them in that order. For the \(i\)th tree, a sequence of right-falling trees ending at position \(P_i\) may have that tree added onto it, meaning that we must have \(R_{P_i+H_i} \geq R_{P_i} + H_i\), and should therefore set \(R_{P_i+H_i} := max ( R_{P_i+H_i}, R_{P_i} + H_i )\).

Note that, though \(R_p\) is defined and possibly relevant for any integer \(p\) in [\(-10^9, 10^9\)], at most \(N\) entries are non-zero (at most one for each tree). Therefore, in order to keep memory usage manageable, we should store a sparse mapping of \(p \rightarrow R_p\), for example using a hash table (such as a C++ `unordered_map` or Python `dict`). This can also help with efficient computation of \(max_p ( R_p + L_p )\), as we should only consider positions \(p\) for which either \(R_p\) or \(L_p\) is non-zero.

The time complexity of this algorithm is \(O(N \log(N))\), resulting from sorting the trees.


Code: // Timber
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x) {
  char c, r = 0, n = 0;
  x = 0;
  for (;;) {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else if ((c >= '0') && (c <= '9'))
      x = x * 10 + c - '0', r = 1;
    else if (r)
      break;
  }
  if (n)
    x = -x;
  return(1);
}

#define LIM 800005

int N;
PR P[LIM];
unordered_map<int, int> M[2]; // [left-to-right, right-to-left]

int ProcessCase()
{
  int i, d, ans = 0;
  Read(N);
  Fox(i, N)
    Read(P[i].x), Read(P[i].y);
  sort(P, P + N);
  Fox(d, 2)
    M[d].clear();
  Fox(d, 2)
  {
    if (d == 1)
      reverse(P, P + N);
    Fox(i, N)
      Max(M[d][P[i].x + P[i].y * (d ? -1 : 1)], M[d][P[i].x] + P[i].y);
    for (auto I : M[d])
      Max(ans, I.y + M[1 - d][I.x]);
  }
  return(ans);
}

int main() {
  int T, t;
  Read(T);
  Fox1(t, T)
    printf("Case #%d: %d\n", t, ProcessCase());
  return(0);
}