Problem: capastaty (2020 round2)

During the COVID-19 pandemic, Pascal, like many others, has become [an expert at cooking pasta](https://xkcd.com/2287/). He's become so talented that he's decided to open his own restaurant! The challenge is that restaurants today must follow strict capacity guidelines to reduce the virus's spread. He's got the cooking covered, but will need help optimizing the seating logistics in order to achieve a good trade-off between a booming business and responsible social distancing.

On a certain day, Pascal's restaurant is divided into \(N\) open seating sections (numbered from \(1\) to \(N\)), with \(S_i\) customers initially sitting in each section \(i\). To keep business strong, but seating capacity manageable, Pascal insists that each section \(i\) must seat between \(X_i\) and \(X_i + Y_i\) customers, inclusive.

In an attempt to achieve this, he may repeatedly choose a customer to politely (yet forcibly) relocate from their current seating section to a different section of Pascal's choice.

Customers would be annoyed by too much shuffling about, so Pascal has asked for your help in determining the minimum number of such relocations necessary. If the criteria cannot all be met after any number of relocations, you should report a value of \(-1\) instead.

In order to reduce the size of the input, the above values will not all be provided explicitly. Instead, you'll be given the first \(K\) values \(S_{1..K}\), \(X_{1..K}\), and \(Y_{1..K}\), as well as the three quadruples of constants \((A_S, B_S, C_S, D_S)\), \((A_X, B_X, C_X, D_X)\), and \((A_Y, B_Y, C_Y, D_Y)\), and must then compute \(S_{(K+1)..N}\), \(X_{(K+1)..N}\), and \(Y_{(K+1)..N}\) as follows:

\(S_i = (A_S * S_{i-2} + B_S * S_{i-1} + C_S)\text{ modulo }D_S\)  for \(i > K\)
\(X_i = (A_X * X_{i-2} + B_X * X_{i-1} + C_X)\text{ modulo }D_X\) for \(i > K\)
\(Y_i = (A_Y * Y_{i-2} + B_Y * Y_{i-1} + C_Y)\text{ modulo }D_Y\) for \(i > K\)

The sum of \(N\) across all \(T\) days is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of days. For each day, there are 7 lines:

The first line contains the 2 space-separated integers \(N\) and \(K\).

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

The third line contains the 4 space-separated integers \(A_S\), \(B_S\), \(C_S\), and \(D_S\).

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

The fifth line contains the 4 space-separated integers \(A_X\), \(B_X\), \(C_X\), and \(D_X\).

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

The seventh line contains the 4 space-separated integers \(A_Y\), \(B_Y\), \(C_Y\), and \(D_Y\).

# Output

For the \(i\)th day, print a line containing *"Case #i: "* followed by a single integer, either the minimum number of customer relocations required, or \(-1\) if it's impossible.

# Constraints

\(1 \le T \le 100\)
\(2 \le N \le 1,000,000\)
\(2 \le K \le N\)
\(0 \le A_S, B_S, C_S, A_X, B_X, C_X, A_Y, B_Y, C_Y \le 1,000,000,000\)
\(1 \le D_S, D_X, D_Y \le 1,000,000,000\)
\(0 \le S_i < D_S\)
\(0 \le X_i < D_X\)
\(0 \le Y_i < D_Y\)

# Explanation of Sample

On the first day, Pascal divides his restaurant into 2 seating sections, with \(S = [10, 20]\), \(X = [9, 21]\), and \(Y = [0, 0]\). In other words, the first section initially has 10 customers but needs to have exactly 9, while the second initially has 20 but needs to have exactly 21. Relocating a single customer from the first section to the second would satisfy both requirements.

On the second day, each section needs to end up with anywhere between 14 and 18 customers, inclusive. Relocating 4 customers from the second section to the first would accomplish this.

On the third day, it's impossible to satisfy all of the requirements. For example, if 2 customers were relocated from the first section to the second, the first section would be left with fewer than its required minimum of 2 customers.

On the fifth day, \(S = [15, 12, 2, 19, 3]\), \(X = [1, 9, 3, 1, 3]\), and \(Y = [0, 6, 9, 9, 8]\).


Sample input:
7
2 2
10 20
0 0 0 100
9 21
0 0 0 100
0 0
0 0 0 100
2 2
10 20
0 0 0 100
14 14
0 0 0 100
4 4
0 0 0 100
2 2
3 5
0 0 0 100
2 7
0 0 0 100
2 0
0 0 0 100
4 4
8 2 5 7
0 0 0 100
2 0 7 2
0 0 0 100
3 5 4 1
0 0 0 100
5 2
15 12
1 2 3 20
1 9
2 3 4 10
0 6
3 4 5 10
100 2
267483417 24355960
870455564 423903642 12577889 341064999
227341573 171278940
619862831 424929478 165711514 317464772
110095480 184821992
618014398 840039189 11907142 234063725
1000 2
0 1
0 1 1 2
0 1
0 1 1 2
0 1
0 1 1 2


Sample output:
Case #1: 1
Case #2: 4
Case #3: -1
Case #4: 7
Case #5: -1
Case #6: 5172260357
Case #7: 0


Solution: For each seating section \(i\), we can compute 4 quantities:

1. **At least** \(\text{max}(0, X_i - S_i)\) customers must be added to it
2. **At most** \(\text{max}(0, (X_i + Y_i) - S_i)\) customers may be added to it
3. **At least** \(\text{max}(0, S_i - (X_i + Y_i))\) customers must be removed from it
4. **At most** \(\text{max}(0, S_i - X_i)\) customers may be removed from it

Note that no section will require customers to both be added and removed from it (quantities 1 and 3 cannot both be positive).

Let \(Q_i\) be the sum of the \(i\)th quantity described above across all \(N\) seating sections. We can compute \(Q_{1..4}\) in \(O(N)\) time. If \(Q_1\) (the minimum total number of customers who must be added to sections) is greater than \(Q_4\) (the maximum total number of customers who may be removed from sections), then the output must be \(-1\). The same applies if \(Q_3 > Q_2\).

Otherwise, we can observe that it's always possible to relocate customers such that all of the sections' requirements are satisfied, and in particular to do so using only \(\text{max}(Q_1, Q_3)\) relocations (it cannot possibly take fewer). In particular, we can begin by relocating \(\text{min}(Q_1, Q_3)\) customers from sections which must have customers removed into ones which must have customers added. After that, there may either be remaining sections requiring more customers or ones requiring fewer customers, which can be addressed with another \(\text{max}(Q_1, Q_3) - \text{min}(Q_1, Q_3)\) relocations.



Code: // Ca-pasta-ty
// 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 S[LIM], X[LIM], Y[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;
}

LL ProcessCase()
{
  int N, K, i;
  // input
  Read(N), Read(K);
  ReadSeq(S, N, K);
  ReadSeq(X, N, K);
  ReadSeq(Y, N, K);
  // aggregate requirements
  pair<LL, LL> P[2];
  Fox(i, N)
  {
    int x = X[i] - S[i], y = X[i] + Y[i] - S[i];
    P[0].x += max(0, -y);
    P[0].y += max(0, -x);
    P[1].x += max(0, x);
    P[1].y += max(0, y);
  }
  // check if satisfiable
  Fox(i, 2)
    if (P[i].x > P[1 - i].y)
      return(-1);
  return(max(P[0].x, P[1].x));
}

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