Problem: dislodging_logs (2020 round1)

The ingenuity of the great Canadian log drive is the use of natural rivers to transport logs. But as every Canadian knows, not every body of water is so free-flowing, especially in winter. In slow-moving sections of a river, it's common for the surface of the water to freeze overnight, trapping the logs. The log drivers can break up the ice with their long-handled picks, but we'll give them a helping hand anyway. [With dynamite](https://www.youtube.com/watch?v=7AheBqBk0iQ&feature=youtu.be&t=338).

Paul is in charge of coordinating the placement of explosive charges. This is the best dynamite-related job in the log drive, not because it's the safest (which it is), but because you get to light the fuse at the end. We can model the relevant section of the river as a number line with \(N\) log drivers and \(M\) clusters of frozen logs. The \(i\)th log driver is at position \(P_i\) (measured in metres), and the \(i\)th cluster of logs is at position \(Q_i\). All \(N+M\) of these initial positions are distinct.

Every second, each log driver can move one metre to either the left or right, or remain stationary. Multiple log drivers are permitted to occupy the same position. When a log driver occupies the same position as a cluster of frozen logs, they can spend \(S\) seconds to set an explosive charge, and can continue moving after that. **Due to an error, please note that \(S\) is always equal to \(0\).**

As soon as an explosive charge is in place at every cluster, Paul will begin the detonation process by lighting the universal fuse (don't worry, the fuse is long enough to allow the other log drivers to clear out in time). If Paul commands the log drivers optimally, what's the minimum amount of time after which he can light the fuse?

In order to reduce the size of the input, the positions of the logs and log drivers will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(P_{1..K}\) and \(Q_{1..K}\), as well as the two quadruples of constants \((A_P, B_P, C_P, D_P)\) and \((A_Q, B_Q, C_Q, D_Q)\), and must then compute \(P_{(K+1)..N}\) and \(Q_{(K+1)..M}\) as follows:

\(P_i = ((A_P * P_{i-2} + B_P * P_{i-1} + C_P) \text{ modulo } D_P) + 1\) for \(i \gt K\)
\(Q_i = ((A_Q * Q_{i-2} + B_Q * Q_{i-1} + C_Q) \text{ modulo } D_Q) + 1\) for \(i \gt K\)

# Input

Input begins with an integer \(T\), the number of frozen river sections. For each section, there are 5 lines. 

The first line contains the 4 space-separated integers \(N\), \(M\), \(K\), and \(S\).

The second line contains the \(K\) space-separated integers \(P_{1..K}\).

The third line contains the 4 space-separated integers \(A_P\), \(B_P\), \(C_P\), and \(D_P\).

The fourth line contains the \(K\) space-separated integers \(Q_{1..K}\).

The fifth line contains the 4 space-separated integers \(A_Q\), \(B_Q\), \(C_Q\), and \(D_Q\).

# Output

For the \(i\)th river section, print a line containing *"Case #i: "* followed by a single integer, the minimum amount of time (in seconds) before the explosive charges can all be placed and Paul can light the fuse.

# Constraints

\(1 \le T \le 85\) 
\(2 \le N, M \le 1,000,000\)
\(2 \le K \le \text{min}(N, M)\)
\(S = 0\)
\(0 \le A_P, B_P, C_P, A_Q, B_Q, C_Q \le 1,000,000,000\)
\(1 \le D_P, D_Q \le 500,000,000\)
\(1 \le P_i \le D_P\)
\(1 \le Q_i \le D_Q\)

The sum of \(N+M\) across all test cases is at most 10,000,000.

# Explanation of Sample

For the first river section, \(P = [10, 20]\) and \(Q = [13, 16]\). It's optimal for the first log driver to walk to the first log cluster (at position 13) in 3 seconds and set an explosive charge there, while the second log driver walks to the second cluster in 4 seconds and does the same. After 4 seconds, both explosive charges will have been placed, at which point Paul can light the fuse.

For the second river section, it's optimal for the first log driver to take the day off while the second walks to the second log cluster, sets an explosive charge there, and then walks to the first cluster and does the same. This process will take a total of 2 + 1 = 3 seconds.

For the fourth river section:
\(P = [83, 16, 59, 131, 222, 371, 229, 214]\)
\(Q = [8, 62, 92, 202, 70, 150, 250]\)


Sample input:
5
2 2 2 0
10 20
0 0 0 100
13 16
0 0 0 100
2 2 2 0
10 20
0 0 0 100
17 18
0 0 0 100
3 3 3 0
20 60 30
0 0 0 100
25 10 35
0 0 0 100
8 7 3 0
83 16 59
13 5 41 414
8 62 92
62 48 21 404
35 45 8 0
512 931 3092 1477 167 2003 3204 1889
1927 1824 2165 3998
2999 3627 1603 387 1017 905 2215 295
1317 2142 1583 3999


Sample output:
Case #1: 4
Case #2: 3
Case #3: 15
Case #4: 21
Case #5: 229


Solution: Let \(F(t)\) equal \(true\) if it's possible to light the fuse within at most \(t\) seconds, and equal to \(false\) otherwise. If \(F(t_1) = true\), this implies that \(F(t_2) = true\) for every \(t_2 \ge t_1\). This means that it's possible to binary search for the smallest value of \(t\) such that \(F(t) = true\), which will be our answer. This value must be positive and no greater than \(D_P + D_Q\). What remains is efficient evaluation of \(F(t)\).

Let \(E_i\) be the set of log cluster positions which the \(i\)th log driver will set explosive charges at. If \(E_i\) is non-empty, we can observe that the number of seconds the \(i\)th log driver requires is equal to \(\text{min}(|\text{min}(E_i) - P_i|, |\text{max}(E_i) - P_i|)\) \(+\) \((\text{max}(E_i) - \text{min}(E_i))\), where \(\text{min}(E_i)\) and \(\text{max}(E_i)\) are the smallest and largest positions in \(E_i\), respectively.

This observation may be turned into a key insight — if we consider the log drivers and the log clusters each sorted in increasing order of position, then it's optimal for \(E_{1..N}\) to correspond to a partioning of the log clusters into a sequence of contiguous subarrays handled by one log driver each, in the same relative order. Interleaving two log drivers' \(E\) sets (such that either of them no longer consists of a subarray of log clusters) can only increase the time required, as can swapping two \(E\) sets (such that an earlier log driver sets explosive charges at a later subarray of log clusters).

Based on this insight, we can iterate over the log drivers in increasing order of position, while maintaining a non-decreasing pointer into the sorted list of log clusters and greedily allocating as many of the next log clusters as possible to the current log driver (without them requiring more than \(t\) seconds to handle those log clusters). By the time all \(N\) log drivers have been considered, we must have \(F(t) = true\) if and only if all \(M\) log clusters have been allocated to them.

Evaluating \(F(t)\) takes just \(O(N+M)\) time, assuming that the \(P\) and \(Q\) values have already been sorted. As such, the overall time complexity of this solution comes out to \(O(N log(N) + M log(M) + (N+M) log(D_P + D_Q))\).

Though we initially believed that the above solution extends to the case in which \(S > 0\), it does not, as it is then no longer necessarily the case that the partitions of logs clusters should be assigned to log drivers in the same relative order. For example, consider the counterexample (pointed out by competitor Scott Wu) in which there are 2 log drivers at positions \(20\) and \(25\), 3 log clusters at positions \(5\), \(10\), and \(11\), and \(S = 10\). In this case, the first log cluster should be handled by the second log driver to achieve the optimal answer of 30.

Because this error unfortunately only came to light during the round, we altered the constraints at that point such that \(S\) is always equal to \(0\) rather than being positive. Since everybody who received an Accepted verdict before that point had written a solution trivially applicable to \(S = 0\) and consistent with our intended solution, we kept those Accepted verdicts, while rejudging all submissions which had previously received Wrong Answer verdicts.


Code: // Dislodging Logs
// 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_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 1000001

int N[2], K, S;
int P[2][LIM];

void ReadSeq(int* V, int N, int K)
{
  int i, A, B, C, D;
  Fox(i, K)
    Read(V[i]);
  Read(A), Read(B), Read(C), Read(D);
  FoxI(i, K, N - 1)
    V[i] = ((LL)A * V[i - 2] + (LL)B * V[i - 1] + C) % D + 1;
}

bool IsValid(LL m)
{
  int i, j = 0;
  // iterate over log drivers from left to right
  Fox(i, N[0])
  {
    // greedily allocate as many clusters as possible to this log driver
    int k = j;
    while (k < N[1])
    {
      LL d = min(Abs(P[0][i] - P[1][j]), Abs(P[0][i] - P[1][k])) + (P[1][k] - P[1][j]);
      if (d > m)
        break;
      k++;
    }
    // all clusters covered?
    if (k == N[1])
      return(1);
    j = k;
  }
  return(0);
}

LL ProcessCase()
{
  int i;
  // input, and sort by position
  Fox(i, 2)
    Read(N[i]);
  Read(K), Read(S);
  Fox(i, 2)
  {
    ReadSeq(P[i], N[i], K);
    sort(P[i], P[i] + N[i]);
  }
  // binary search for min. valid # of seconds
  LL r1 = 1, r2 = INF;
  while (r2 > r1)
  {
    LL m = (r1 + r2) >> 1;
    if (IsValid(m))
      r2 = m;
    else
      r1 = m + 1;
  }
  return(r1);
}

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