Problem: mail_security (2020 round3)

Facebook Prime is a top-secret subscription service being developed to disrupt the online shopping space. (Or maybe there's no such service — we're not telling.) A central focus of the service is preventing package theft, something which has become all too common in today's delivery-driven world. As a member of its engineering team, you wish to model some worst-case scenarios to stress test the vulnerability of poorly-run mailrooms.

In the *very* worst cases, mailroom managers will actually leave mailbox keys inside mailboxes themselves. This means that if one mailbox were to be broken into, a series of other mailboxes could be compromised as well. Suppose a particular mailroom has \(N\) mailboxes (numbered from \(1\) to \(N\)), each with a corresponding key, and \(M\) packages (numbered from \(1\) to \(M\)). The \(i\)th mailbox has a capacity of \(S_i\), meaning that it can store a set of objects (packages or keys) as long as the sum of their sizes doesn't exceed \(S_i\). The size of the \(i\)th package is \(P_i\), and the size of each key is \(X\).

For the purposes of our model, a valid mailroom arrangement must satisfy all of the following conditions:

  1. Each package is either inside a mailbox, or is entirely absent.
  2. Each key is either inside a mailbox (possibly its own corresponding mailbox), or is entirely absent.
  3. Each mailbox contains at most 1 package.
  4. No mailbox's capacity is exceeded.

Suppose a thief enters a validly arranged mailroom and forcibly breaks into just one mailbox (without needing a key). If the mailbox contains a package, then they'll obtain it; if the mailbox contains any keys, the thief can then proceed to open each of those keys' corresponding mailboxes and repeat the process (gaining access to any packages and keys they contain, and so on).

Given the specifications of a mailroom, you wish to determine, among all possible valid arrangements, the largest number of packages that may be obtained after a thief forcibly breaks into a single mailbox.

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}\) and \(P_{1..K}\), as well as the two quadruples of constants \((A_S, B_S, C_S, D_S)\) and \((A_P, B_P, C_P, D_P)\), and must then compute \(S_{(K+1)..N}\) and \(P_{(K+1)..M}\) as follows:

\(S_i = ((A_S * S_{i-2} + B_S * S_{i-1} + C_S)\text{ modulo }D_S) + 1\) for \(i > K\)
\(P_i = ((A_P * P_{i-2} + B_P * P_{i-1} + C_P)\text{ modulo }D_P) + 1\) for \(i > K\)

# Constraints

\(1 \le T \le 90\)
\(2 \le N \le 1,000,000\)
\(2 \le M \le 1,000,000\)
\(2 \le K \le min(N, M)\)
\(1 \le X \le 1,000,000,000\)
\(0 \le A_S, B_S, C_S, A_P, B_P, C_P \le 1,000,000,000\)
\(1 \le D_S, D_P \le 1,000,000,000\)
\(1 \le S_i \le D_S\)
\(1 \le P_i \le D_P\)

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

# Input

Input begins with an integer \(T\), the number of mailrooms to be modeled. For each mailroom, there are 5 lines:

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

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 \(P_{1..K}\).

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


# Output

For each mailroom, print a line containing *"Case #i: "*, followed by a single integer, the maximum possible number of packages which could be stolen by forcibly breaking into a single mailbox in any valid mailroom arrangement.




# Explanation of Sample

For the first mailroom, \(S = [10, 10, 10]\) and \(P = [9, 9, 9]\). If each mailbox contains a package, the 1st mailbox contains the 2nd mailbox's key, and the 2nd mailbox contains the 3rd mailbox's key, then a thief breaking into the 1st mailbox would gain access to the 2nd mailbox followed by the 3rd, obtaining all three packages in the process.

For the second mailroom, \(S = [10, 10, 10]\) and \(P = [10, 10, 10]\). If the 1st and 3rd mailboxes each contain a package, while the 2nd mailbox contains all three mailboxes' keys, then a thief breaking into the 2nd mailbox would gain access to the other two mailboxes and their packages.

For the third mailroom, \(S = [10, 10, 10]\) and \(P = [11, 11, 11]\). No package can fit within any mailbox.

For the fourth mailroom, \(S = [2, 11, 9, 7]\) and \(P = [10, 9, 10, 11]\). It's possible to arrange the mailroom such that two packages are obtainable by a thief, but three or more can never be obtained.

For the fifth mailroom, \(S = [15, 3, 5, 11, 7, 17, 5]\) and \(P = [7, 8, 11, 10, 3]\).


Sample input:
6
3 3 3 1
10 10 10
0 0 0 100
9 9 9
0 0 0 100
3 3 3 1
10 10 10
0 0 0 100
10 10 10
0 0 0 100
3 3 3 1
10 10 10
0 0 0 100
11 11 11
0 0 0 100
4 4 2 3
2 11
1 0 6 11
10 9
0 1 0 13
7 5 5 4
15 3 5 11 7
13 6 11 20
7 8 11 10 3
0 0 0 100
20 25 2 8
21 4
1 2 3 30
17 18
4 5 6 30


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


Solution: As a general observation, we can note that keys are essentially interchangeable. If we're "using" \(x\) mailboxes (that is, there are \(x\) non-empty mailboxes that we intend for the thief to gain access to), the only requirement is that a total of at least \(x-1\) keys are present somewhere amongst them. It's then always possible to assign the keys' identities and select an initial break-in mailbox such that the thief will eventually access all \(x\) mailboxes.

Now, we'll begin by sorting the mailboxes in order of capacity, and the packages in order of size. We'll then binary search on \([0, \min(N, M)]\) for the maximum number \(v\) of packages which can be obtained, which will be our answer.

For a given value of \(v\), we'll begin by reducing the set of \(N+M\) mailboxes/packages to only the relevant ones which we'll intend to use. We should attempt to use the smallest \(v\) packages, ignoring the rest. We'll need to use at least \(v\) mailboxes, which might as well be the largest \(v\) of them. If there are additional mailboxes capable of fitting at least one key (having capacities no less than \(X\)), then we should intend on using all of them as well (even if some may prove unnecessary), and we should **ignore any remaining mailboxes**. It can't be better to use fewer mailboxes, as using a mailbox capable of fitting a key can never be detrimental (as it can at least fit a key allowing use of another mailbox in its place). It also can't be better to use more mailboxes, as using an *additional* mailbox with capacity less than \(X\) (with the intent of placing a package with size less than \(X\) in it) cannot be more beneficial than instead replacing an existing key in some larger mailbox not yet containing any package with this small package — at least one such mailbox must exist in that scenario.

We'll then combine the relevant mailboxes/packages into a single list sorted in non-increasing order of capacity/size, and iterate over them in that order. Along the way, we'll maintain an ordered multiset of mailbox capacities which have been seen but not yet used, ordered by their capacities modulo \(X\) (initially empty), as well as the total number \(k\) of keys which can fit within the already-seen mailboxes (initially \(0\)).

- When a mailbox with capacity \(c\) is encountered, we'll insert \(c\) into our multiset and increase \(k\) by \(\lfloor c/X \rfloor\).
- When a package with size \(p\) is encountered, it must be placed into some mailbox in our multiset. If the multiset is empty, then the given value of \(v\) must be invalid. Otherwise, we should choose a mailbox capacity \(c\) for which \(c \text{ \% } X \ge p \text{ \% } X\) and \(c \text{ \% } X\) is minimized — or, if there's no such capacity, then instead just a capacity \(c\) for which \(c \text{ \% } X\) is minimized (where \(\text{\%}\) is the modulo operator). This greedy strategy is based on the fact that the package will reduce the number of keys which can fit in the mailbox by \(\lfloor p/X \rfloor\) if \(c \text{ \% } X \ge p \text{ \% } X\), and by \(\lfloor p/X \rfloor + 1\) otherwise. Either way, once the optimal \(c\) has been selected, we'll remove it from our multiset and decrease \(k\) accordingly.
   
By the end of this process, the given value of \(v\) must be valid if and only if \(k+1\) is greater than or equal to the number of mailboxes used.

The total time complexity of this solution is \(O((N + M) (log(N) + log(M))^2)\).


Code: // Mail Security
// 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 1000000

int N, M, K, X;
int S[LIM], P[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 Valid(int np)
{
  int i;
  // assemble list of relevant objects
  vector<PR> O;
  FoxR(i, N) // largest np mailboxes, plus any large enough for a key
    if (O.size() < np || S[i] >= X)
      O.pb(mp(S[i], 1));
  int nb = Sz(O);
  Fox(i, np) // smallest np packages
    O.pb(mp(P[i], 0));
  sort(All(O), std::greater<>());
  // iterate over objects by non-increasing capacity/size
  multiset<PR> AC; // available pairs of (capacity % X, capacity)
  LL nk = 0;
  for (auto o : O)
  {
    // mailbox?
    if (o.y)
    {
      nk += o.x / X;
      AC.insert(mp(o.x % X, o.x));
      continue;
    }
    // package
    if (AC.empty())
      return(0);
    auto I = AC.lower_bound(mp(o.x % X, 0));
    if (I == AC.end())
      I = AC.begin();
    int c = I->y;
    AC.erase(I);
    nk += (c - o.x) / X - c / X;
  }
  return(nk >= nb - 1);
}

int ProcessCase()
{
  // input
  Read(N), Read(M), Read(K), Read(X);
  ReadSeq(S, N, K);
  ReadSeq(P, M, K);
  // sort objects by capacity/size
  sort(S, S + N);
  sort(P, P + M);
  // binary search
  int r1 = 0, r2 = min(N, M);
  while (r1 < r2)
  {
    int m = (r1 + r2 + 1) / 2;
    if (Valid(m))
      r1 = m;
    else
      r2 = m - 1;
  }
  return(r1);
}

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