Problem: smart_carts (2020 round3)

Every week you take a socially-distanced trip to Overwaitea, your favourite grocery store, to stock up on food. Out front, there are \(N\) shopping carts, numbered from \(1\) to \(N\). To dissuade theft, the carts are locked together and you need to insert a quarter to unlock one cart from the rest. When you return your cart, you get your quarter back. Now that you think about it, maybe 25 Canadian cents is actually a pretty good deal for your very own shopping cart...

Each cart has a connecting chain leading out of it. There are also \(N+2\) latches, numbered from \(1\) to \(N+2\), which chains may be connected to (with each latch having at most one incoming chain). Each of the first \(N\) latches can be found on carts, with latch \(i\) fixed to cart \(i\). The remaining two latches (latches \(N+1\) and \(N+2\)) are instead mounted to a wall. Each cart \(i\)'s chain is initially connected to latch \(A_i\), but you suspect it would be more aesthetically pleasing if it was instead attached to an ideal target latch \(B_i\).

A *sequence* of \(K\) carts \(S_{1..K}\) is one in which latch \(S_1\) has no incoming chain, cart \(S_1\)'s chain connects to latch \(S_2\), cart \(S_2\)'s chain connects to latch \(S_3\), and so on, with cart \(S_{K-1}\)'s chain connecting to latch \(S_K\), and cart \(S_K\)'s chain not connecting to any cart (but rather to either a wall latch or no latch).

The carts are rigid enough that it's impossible to ever form a "cycle" of carts, such that repeatedly following chain connections forwards from an initial cart will result in returning to that initial cart. This means that each cart is always part of exactly one *sequence*, and is present in that *sequence* exactly once.

The values of \(A_{1..N}\) and \(B_{1..N}\) are given such that the carts initially form a valid configuration (with no "cycles"), and would also form a valid configuration if every cart's chain were to be connected to its ideal target latch.

For example, if \(N = 3\) and \(A = [4, 1, 5]\), the initial configuration looks as follows (having two *sequences* of carts \([2, 1]\) and \([3]\)):

{{PHOTO_ID:1217734278611436}}

You may repeatedly perform either of the following actions before leaving the carts in a desired *final state*, in which every chain must end up once again connected to a latch:

  1. Pay 1 quarter (if you have at least 1) to detach any given cart's chain from whichever latch it's currently connected to (if any)
  2. Gain 1 quarter by attaching any given cart's currently-unattached chain to a latch (as long as no other chain is currently connected to that latch, and a "cycle" of carts would not be formed)

For example, beginning with the above configuration and with at least 1 quarter in hand, you could perform **action 1** to detach cart 1's chain and produce the following configuration (which is *not* a valid *final state* due to cart 1's chain not being connected to any latch):

{{PHOTO_ID:3302289739857297}}

You could then perform **action 2** to attach cart 1's chain to cart 3's latch (forming a valid *final state*):

{{PHOTO_ID:766911834140516}}

Consider a hypothetical scenario in which:

  - You begin with \(Q\) quarters
  - A *sequence* consisting of more than \(C\) carts must never be present (including initially)
  - The *final state* must not have a *sequence* consisting of more than \(X\) carts attached to latch \(N+1\)
  - The *final state* must not have a *sequence* consisting of more than \(Y\) carts attached to latch \(N+2\)

Let \(F(Q, C, X, Y)\) be the maximum number of chains which can end up connected to their ideal target latches in a *final state* given such a scenario, or \(-1\) if it's impossible to achieve a valid *final state* at all.

Let \(G(v)\) be the number of quadruples \((Q, C, X, Y)\) such that \(0 \le Q, C, X, Y \le N\) and \(F(Q, C, X, Y) = v\). You'd like to compute \(G(v)\) for each integer \(v\) such that \(-1 \le v \le N\).

# Constraints

\(1 \le T \le 85\)
\(1 \le N \le 700\)
\(1 \le A_i, B_i \le N+2\)

The sum of \(N\) across all test cases is at most 7000.

# Input

Input begins with an integer \(T\), the number of sets of shopping carts. For each set there are \(N+1\) lines. The first contains the integer \(N\). \(N\) lines follow, the \(i\)th of which contains the space-separated integers \(A_i\) and \(B_i\).




# Output

For each set of shopping carts, print a line containing *"Case #i: "*, followed by \(N+2\) integers, \(G(-1)\), \(G(0)\), \(G(1)\), ..., \(G(N-1)\), \(G(N)\), as defined above.


# Explanation of Sample

In the first case, the initial configuration is as follows:

{{PHOTO_ID:3371452566235882}}

There are \(2^4 = 16\) quadruples \((Q, C, X, Y)\) to consider. For 11 of them, \(F(Q, C, X, Y) = -1\), while the following 5 yield different results:

- \(F(0, 1, 1, 0) = 0\)
- \(F(0, 1, 1, 1) = 0\)
- \(F(1, 1, 1, 0) = 0\)
- \(F(1, 1, 0, 1) = 1\)
- \(F(1, 1, 1, 1) = 1\)

Several evaluations of \(F(Q, C, X, Y)\) are explained below:

- \(F(1, 0, 1, 1) = -1\) because the initial configuration features a *sequence* of 1 cart, which is disallowed due to \(C = 0\).
- \(F(1, 1, 0, 0) = -1\) because every possible *final state* features a *sequence* of 1 cart connected to either latch 2 or latch 3, which is disallowed due to \(X = Y = 0\).
- \(F(0, 1, 1, 1) = 0\) because no action may initially taken without at least 1 quarter.
- \(F(1, 1, 0, 1) = 1\) because you may spend your 1 quarter to disconnect cart 1's chain from latch 2, and then gain your quarter back while connecting it to latch 3 (its ideal target latch).

In the second case, the initial configuration is as follows:

{{PHOTO_ID:1217734278611436}}

Several evaluations of \(F(Q, C, X, Y)\) are explained below:

- \(F(3, 2, 2, 2) = 3\) because you may spend your 3 quarters disconnecting all of the carts' chains, and then gain your quarters back while connecting the carts' chains to their ideal target latches in any order (without a *sequence* of more than 2 carts ever being present). This yields the following *final state*:

{{PHOTO_ID:2978496958918891}}
 
- \(F(3, 3, 3, 1) = 2\) because you may similarly disconnect and then reconnect all of the carts' chains, but cannot arrive at the same *final state* as above (as it features a *sequence* of 2 carts connected to latch 5, which is disallowed due to \(Y = 1\)). This means that only up to 2 chains may end up connected to their ideal target latches instead, for example as in the following *final state*:

{{PHOTO_ID:3274155842706395}}


Sample input:
5
1
2 3
3
4 5
1 4
5 1
4
3 2
4 6
5 5
1 3
6
5 6
3 5
4 7
6 2
7 1
8 3
10
11 2
1 3
2 4
3 5
4 6
12 7
6 8
7 9
8 10
9 11


Sample output:
Case #1: 11 3 2
Case #2: 190 20 0 16 30
Case #3: 560 0 5 0 24 36
Case #4: 1900 67 0 7 19 0 366 42
Case #5: 11165 298 2 52 6 54 0 20 44 0 2890 110


Solution: As a general observation, we can note that the carts in both the initial configuration and any valid *final state* form at most two *sequences*, one attached to latch \(N+1\) and the other to latch \(N+2\). We'll refer to these as the first and second "lines" (either of which may be empty), with the start of each line being the cart attached to the wall latch. We'll then let \(L_i\) be the length of the \(i\)th initial line, and \(K_i\) be the cap on the length of the \(i\)th line in the *final state* (\(K = [X, Y]\)).

Now, we'll begin by discussing how to evaluate \(F(Q, C, X, Y)\), before extending that to efficiently aggregate values across all quadruples \((Q, C, X, Y)\).

Checking for impossibility (\(F(Q, C, X, Y) = -1\)) is relatively simple. It's impossible if \(C\) is smaller than either \(L_1\) or \(L_2\), and impossible if \(\min(C, X) + \min(C, Y) < N\). If \(Q=0\), then it's also impossible if \(K_i < L_i\) for either line \(i\). It's otherwise possible.

Assuming it is possible, there are three distinct cases to consider based on the value of \(Q\):

1. When \(Q=0\), the answer is simply the number of initially-satisfied carts (carts \(i\) such that \(A_i = B_i\)).
2. When \(Q>1\), we can show that it's possible to arrange the carts into any *final state* which satisfies the basic requirements (that is, such that length of each line \(i\) does not exceed \(\min(C, K_i)\)).
One way of demonstrating this is as follows. It's possible to move any cart \(i\) to the end of its current line without involving a longer *sequence* (by disconnecting cart \(i\) from the previous/next latches, connecting it to the former ending cart, and then connecting the line back together). Through repeated applications of this, it's possible to arbitrarily permute the carts in a line. It's furthermore trivially possible to move one line's ending cart to the end of the other line, or to swap the ending carts of both lines, similarly without involving longer *sequences* than necessary. A combination of these operations allows all \(N\) carts to be arbitrarily rearranged.
As a result of this fact, if we consider the lines formed by all chains being connected to their ideal target latches, the answer is simply \(N\) if those lines' lengths satisfy these basic requirements, or \(N-1\) otherwise (as we'll need to split one line at one point, attaching its suffix to the other line instead, in order to make everything fit).
3. When \(Q=1\), things are more involved; we'll discuss this case below.

Let \(F_i = \min(C - L_{3-i}, L_i)\). The last \(F_i\) carts in the \(i\)th line are free to be moved (either amongst themselves or to the other line), while the remaining \(L_i - F_i\) carts are stuck and can never be moved. All rearrangements of the \(F_1 + F_2\) free carts across both lines are achievable (as long as the length of each line \(i\) in the *final state* does not exceed \(\min(C, K_i)\)), which can be demonstrated similarly to in the \(Q>1\) case above. The \((F_i+1)\)th latch from the end of the line, though stuck, is accessible to have a new chain attached to it.

Each cart \(i\) is therefore "potentially satisfiable" if at least one of the following conditions is met:

- It's initially satisfied (\(A_i = B_i\))
- It's free (is amongst the last \(F_x\) carts in its line \(x\)) and latch \(B_i\) is amongst the last \(F_y+1\) latches in its line \(y\) (regardless of whether or not \(x = y\))

However, similarly to the \(Q>1\) case, not all potentially satisfiable carts might actually be simultaneously satisfiable due to restrictions on the *final state*'s line lengths. In order to determine whether this is the case, we'll represent the free, potentially satisfiable carts as a set of "blocks", with each block consisting of 1 or more such carts which should be contiguously connected together in the *final state*. If the ideal target latch of a block's frontmost cart is stuck, then that block is forced to be placed in that latch's particular line. Any other blocks may be rearranged arbitrarily between the two lines, as long as the carts in each block remain together in a single line. Therefore, all potentially satisfiable carts may be satisfied if and only if it's possible to pack these blocks into the two lines without exceeding their maximum allowed lengths, which can be determined if we compute all achievable subset sums of block lengths. If this can't be done, then the answer should be reduced by \(1\) instead, as one block will need to be split up at one point in order to make everything fit.

We're now ready to discuss how to aggregate \(F(Q, C, X, Y)\) values across all quadruples \((Q, C, X, Y)\). We'll shoot for a time complexity of \(O(N^3)\), which is sufficient, though slightly better time complexities (e.g. \(O(N^2 \sqrt{N})\)) are also achievable through some optimizations not discussed in detail here.

Assuming we precompute basic information around the initial and target lines (e.g. \(L_{1..2}\)), it then takes only constant time to evalate \(F(Q, C, X, Y)\) when \(Q \ne 1\). Combined with the fact that \(F(Q, C, X, Y) = F(2, C, X, Y)\) when \(Q > 1\), we can handle all quadruples \((Q, C, X, Y)\) such that \(Q \ne 1\) by simply iterating over all \(O(N^3)\) triples \((C, X, Y)\) (though it's also possible to use the fact that many are evaluated similarly).

For the \(Q = 1\) case, we can observe that the computation of potentially satisfiable carts and achievable block length subset sums depends only on \(C\) (not on \(X\) and \(Y\)). We therefore only need to go through that process \(O(N)\) times, meaning that a naive \(O(N^2)\) subset sum implementation is sufficient (though it's possible in as little as \(O(N \sqrt{N})\) time). Then, given an ordered list of achievable block length subset sums for each value of \(C\), we can iterate over all pairs \((X, Y)\) in another \(O(N^2)\) time and check which ones will have their answer reduced by \(1\) with no additional time (though it's also possible to only iterate over values of \(X\) and deal with the \(Y\) values using binary search).



Code: // Smart Carts
// 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 705

int N;
int nxt[2][LIM], prv[2][LIM];
vector<int> seq[2][2];
int L[2][2];
PR pos[2][LIM];

int F[2], subS[2];
vector<int> CS;
int csInd, sumC, baseAns;

int ProcessQuery0(int* K)
{
  int i, ans = 0;
  // check whether either initial line is too long to be valid
  Fox(i, 2)
    if (L[0][i] > K[i])
      return(-1);
  // count initially-satisfied carts
  Fox(i, N)
    ans += nxt[0][i] == nxt[1][i];
  return(ans);
}

void PrecomputeForQuery1(int C)
{
  int i, j;
  // determine which carts are free
  Fox(i, 2)
    F[i] = min(C - L[0][1 - i], L[0][i]);
  auto IsFree = [&](int i, int e) { // if e=1, include non-free, accessible latches
    PR p = pos[0][i];
    return(p.y > L[0][p.x] - F[p.x] - e);
  };
  // compute number of potentially-satisfiable carts
  baseAns = 0;
  Fox(i, N)
    baseAns += nxt[0][i] == nxt[1][i] || // initially satisfied?
    (IsFree(i, 0) && IsFree(nxt[1][i], 1)); // free, and target accessible?
  // split free, potentially-satisfiable carts into chains
  // and compute achievable subset sums of chain lengths
  sumC = 0;
  Fill(subS, 0);
  bitset<LIM> BC = 1;
  Fox(i, 2)
  {
    auto& s = seq[1][i];
    int c = 0, f = -1;
    Fox(j, Sz(s))
    {
      if (!IsFree(s[j], 0))
        continue;
      c++;
      // chain forced to belong to a certain line?
      if (c == 1 && j && IsFree(s[j - 1], 1))
        f = pos[0][s[j - 1]].x;
      // chain ends with this cart?
      if (j + 1 == Sz(s) || !IsFree(s[j + 1], 0))
      {
        if (f < 0)
          sumC += c, BC |= (BC << c);
        else
          subS[f] += c;
        c = 0, f = -1;
      }
    }
  }
  // store results
  CS.clear();
  Fox(i, sumC + 1)
    if (BC[i])
      CS.pb(i);
  csInd = 0;
}

int ProcessQuery1(int* K)
{
  // compute space for free carts in each line
  int i, S[2];
  Fox(i, 2)
    S[i] = K[i] - (L[0][i] - F[i]) - subS[i];
  // check whether all free cart chains may be packed into the lines
  if (min(S[0], S[1]) < 0)
    return(baseAns - 1);
  while (csInd + 1 < Sz(CS) && CS[csInd + 1] <= S[0])
    csInd++;
  if (sumC - CS[csInd] <= S[1])
    return(baseAns);
  return(baseAns - 1); // 1 cart must remain unsatisfied due to chain breakage
}

int ProcessQuery2(int* K)
{
  int i;
  // check whether either target line is too long to be fully satisfied
  Fox(i, 2)
    if (L[1][i] > K[i])
      return(N - 1);
  return(N);
}

int ProcessQuery(int d, int c, int x, int y)
{
  int i, K[2] = { min(c, x), min(c, y) };
  // check whether either initial line is too long to be valid
  Fox(i, 2)
    if (L[0][i] > c)
      return(-1);
  // check whether there are too many carts to form valid final lines
  if (N > K[0] + K[1])
    return(-1);
  return d == 0
    ? ProcessQuery0(K)
    : d == 1
    ? ProcessQuery1(K)
    : ProcessQuery2(K);
}

void ProcessCase()
{
  int i, j, z;
  // init
  Fill(prv, -1);
  // input
  Read(N);
  Fox(i, N)
  {
    Fox(z, 2)
    {
      Read(nxt[z][i]), nxt[z][i]--;
      prv[z][nxt[z][i]] = i;
    }
  }
  // split into lines (initial/target)
  Fox(z, 2)
  {
    Fox(i, 2)
    {
      seq[z][i].clear();
      j = N + i;
      while (j >= 0)
      {
        pos[z][j] = mp(i, Sz(seq[z][i]));
        seq[z][i].pb(j);
        j = prv[z][j];
      }
      L[z][i] = Sz(seq[z][i]) - 1;
    }
  }
  // process queries
  int d, c, x, y;
  LL G[LIM] = { 0 };
  Fox(d, min(3, N + 1))
  {
    Fox(c, N + 1)
    {
      if (d == 1)
        PrecomputeForQuery1(c);
      Fox(x, N + 1)
      {
        Fox(y, N + 1)
          G[ProcessQuery(d, c, x, y) + 1] += d == 2 ? N - 1 : 1;
      }
    }
  }
  Fox(i, N + 2)
    printf(" %lld", G[i]);
  printf("\n");
}

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