Problem: meta_game (2023 round2)

Hacker Cup contest strategy often involves a metagame, where choosing which problems to work on might just be an important decision. On a Quest to become more Pro, you encounter an oracle promising to teach you the contest meta if you play her own Meta-game.

The oracle presents a peg board with \(2N\) moving dots. The initial \(y\)-positions of the dots are given as two arrays \(A_{1..N}\) and \(B_{1..N}\). Each second, simultaneously, \(A_1\) will move to the end of \(B\), while \(B_1\) will move to the end of \(A\) (with all elements shifting left accordingly).

You can connect the dots to form a *Meta-like logo* if all of the following are true:
* For the first half of both arrays, each dot in \(A\) is below the corresponding dot in \(B\).
* For the last half of both arrays, each dot in \(A\) is above the corresponding dot in \(B\).
* \(A\) equals the reverse of \(B\).

Formally:
* \(A_i < B_i\) for every \(i < (N+1)/2\)
* \(A_i > B_i\) for every \(i > (N+1)/2\)
* \(A_i = B_{N-i+1}\) for every \(i = 1..N\)

Note that if \(N\) is odd, the arrays' middle elements are not subject to the first two constraints.

The following is a visualization of a Meta-like logo (corresponding to the first sample case), with dots in \(A\) shown in red and dots in \(B\) shown in blue.

{{PHOTO_ID:359057163229199|WIDTH:500}}

You must answer the oracle: how many seconds must pass before the first time a Meta-like logo appears? If one never appears, output \(-1\).

# Constraints
\(1 \leq T \leq 135\)
\(2 \leq N \leq 2{,}000{,}000\)
\(0 \leq A_i, B_i \leq 1{,}000{,}000{,}000\)

The sum of \(N\) across all test cases is at most \(9{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, there is a line containing integers \(A_1, ..., A_N\). Then, there is a line containing integers \(B_1, ..., B_N\).


# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by a single integer, the number of seconds that must pass before a Meta-like logo appears, or \(-1\) if that will never happen.


# Sample Explanation

The first test case is shown above. \(A\) and \(B\) already form a Meta-like logo, so the answer is 0.

The second case is not initially a Meta-like logo, for several reasons. One reason is that it is not symmetric. Specifically, the \([3, 3, 2, 3, 5 ,6]\) is not the reverse of \([4, 4, 6, 5, 3 ,2]\). After \(1\) second though, this case turns into the case above and is Meta-like.

The third and fourth cases will never turn into a Meta-like logo, no matter how many seconds we wait.

In the fifth case, after 6 seconds we see the first Meta-like logo. In this case \(A = [1, 1, 2, 2]\) and \(B = [2, 2, 1, 1]\).




Sample input:
8
6
3 2 3 5 6 4
4 6 5 3 2 3
6
3 3 2 3 5 6
4 4 6 5 3 2
6
4 3 2 3 5 6
3 4 6 5 3 2
2
1 1
1 1
4
2 2 2 2
1 1 1 1
5
3 3 3 3 3
1 1 1 1 1
5
3 3 3 3 3
1 1 1 1 3
5
1 1 1 1 3
3 3 3 3 3


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


Solution: Note that over time, a pair of dots that are next to each other will always stay next to each other. 

If \(N\) is even and \(A_i = B_i\) for any \(i\), we know that an answer is not possible by definition. If \(N\) is odd, then there can be at most \(1\) place where \(A_i = B_i\) (the midpoint of the metalike-logo), so we can find it and get the answer in \(\mathcal{O}(N)\), or return \(-1\) if there's more than one \(i\) where \(A_i = B_i\).

Otherwise, every \(A_i \ne B_i\), and we can first just think about each \(i\) as the lower vs higher dot. For a meta-like logo, the relationship always look like this:
```
(even N)                    (odd N)      
3 2 3 5 6 4  -> LLLHHH      3 2 3 x 5 6 4 ->  LLLxHHH
4 6 5 3 2 3  -> HHHLLL      4 6 5 x 3 2 3 ->  HHHxLLL
```
Let's first consider even \(N\) by simulating the first pattern in reverse:
```
(t)     (t-1)   (t-2)   (t-N/2)                 (t-N)
LLLHHH  LLLLHH  LLLLLH  LLLLLL  HLLLLL  HHLLLL  HHHLLL
HHHLLL  HHHHLL  HHHHHL  HHHHHH  LHHHHH  LLHHHH  LLLHHH

(t-N-1)                                 (t-2N)
HHHHLL  HHHHHL  HHHHHH  LHHHHH  LHHHHH  LLHHHH  LLLHHH
LLLLHH  LLLLLH  LLLLLL  HLLLLL  HLLLLL  HHLLLL  HHHLLL
```
Thus the pattern repeats after \(2N\) steps. If an answer exists, then at any given time:
* for even \(N\), there's at most \(1\) place when \(A_i < B_i\) inverts to \(A_{i+1} > B_{i+1}\) (or the reverse).
* for odd \(N\), the middle element eithers conform to its left or right side, so this still holds.

Therefore, the midpoint of the metalike logo either be this inversion point, or the first/last element. Either way, there are \(\mathcal{O}(1)\) possible candidates for the midpoints. After we've found these candidates, we can simulate \(2N\) steps on the input arrays using a double-ended queue (updating the positions of the midpoint candidates at each step). If at any time a midpoint candidate actually shifts to the midpoint, we can do a check to see if \(A\) equals the reverse of \(B\). 

There are \(\mathcal{O}(1)\) midpoint candidates, and each can only reach the midpoint twice in our \(2N\) simulated time steps. Thus, the reverse condition is checked at most \(\mathcal{O}(1)\) times. The overall running time is \(\mathcal{O}(N)\).


Code: #include <deque>
#include <iostream>
#include <vector>
using namespace std;

int N;
deque<int> A, B;

bool is_metalike_now() {
  for (int i = 0; i < N; i++) {
    if (i+1 < (N+1)/2 && !(A[i] < B[i])) {
      return false;
    }
    if (i+1 > (N+1)/2 && !(A[i] > B[i])) {
      return false;
    }
    if (A[i] != B[N - i - 1]) {
      return false;
    }
  }
  return true;
}

// Simulate 2*N seconds.
// Given a vector M of O(1) candidate midpoints (index of the middle elem if N
// is odd, or right after the middle if N even), return the first time that:
// - some m in M becomes the midpoint floor(N/2) (both even and odd N), and
// - is_meta_like() holds true.
int check(vector<int> M) {
  for (int t = 0; t <= 2*N; t++) {
    for (int m : M) {
      if (m == N/2 && is_metalike_now()) {
        return t;
      }
    }
    A.push_back(B[0]);
    B.push_back(A[0]);
    A.pop_front();
    B.pop_front();
    for (int i = 0; i < (int)M.size(); i++) {
      if (--M[i] < 0) {
        M[i] += N;
      }
    }
  }
  return -1;
}


int solve() {
  cin >> N;
  A.resize(N);
  B.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  // Handle any equal pairs.
  vector<int> eq;
  for (int i = 0; i < N; i++) {
    if (A[i] == B[i]) {
      if (N % 2 == 0) {
        return -1;
      }
      eq.push_back(i);
    }
  }
  if (eq.size() > 1) {
    return -1;
  }
  if (eq.size() == 1) {
    return check({eq[0]});
  }
  // From here on, guaranteed that A[i] != B[i].
  // Check the number of times that A[i] < B[i] flips.
  vector<int> flipped;
  for (int i = 1; i < N; i++) {
    if ((A[i - 1] < B[i - 1]) != (A[i] < B[i])) {
      flipped.push_back(i);
    }
  }
  if (flipped.size() > 1) {
    return -1;
  }
  // Might as well consider elements 0 and N-1 to be midpoints.
  flipped.push_back(0);
  flipped.push_back(N-1);
  return check(flipped);
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}