Problem: consecutive_cuts_ch2 (2022 round1)

**Note: The only difference between this chapter and [chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/A1) is that here, card values are not guaranteed to be distinct and can be up to \(10^9\).**

Let's cut to the chase. You have a deck of \(N\) face-up cards, each displaying **a not necessarily unique integer between \(1\) and \(10^9\).**

*Cutting* the deck once consists of taking a stack of between \(1\) and \(N - 1\) (inclusive) cards from the top and moving it to the bottom in the same order. For example, for the deck \([5, 1, 2, 4, 3]\) ordered from top to bottom, cutting \(2\) cards from the top would yield \([2, 4, 3, 5, 1]\):

{{PHOTO_ID:792109885435616|WIDTH:700}}

Initially, the \(i\)th card from the top is \(A_i\). Is it possible to cut the deck exactly \(K\) times to reorder the deck such that the \(i\)th card from the top is \(B_i\) for all \(i\)?


# Constraints

\(1 \le T \le 205\)
\(2 \le N \le 500{,}000\)
\(0 \le K \le 10^{9}\)
\(1 \le A_i, B_i \le \mathbf{10^9}\)
**\(A\) and \(B\) are permutations of each other.**

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

# Input Format

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


# Output Format

For the \(i\)th test case, print `"Case #i: "` followed by `"YES"` if it's possible to cut the deck \(K\) times to change the deck from \(A_i\) to \(B_i\), or `"NO"` otherwise.


# Sample Explanation

In the first case, it's possible to get to the new order with \(K = 1\) cut (cutting 2 cards from the top).

In the second case, it's impossible to change \([3, 1, 4, 2]\) to \([1, 2, 3, 4]\) with any number of cuts.

In the third case, it's impossible for the deck to be in a different order after \(K = 0\) cuts.


Sample input:
4
5 1
5 1 2 2 3
2 2 3 5 1
4 10
3 1 4 2
1 2 3 4
4 0
3 1 4 2
2 3 1 4
5 3
10 10 9 10 9
10 10 10 9 9


Sample output:
Case #1: YES
Case #2: NO
Case #3: NO
Case #4: NO


Solution: When \(K = 0\), again output `YES` if and only if \(A = B\) as in chapter 1.

When \(K = 1\) and \(A = B\), it is now possible for the answer to be `YES` due to duplicates, for instance, if \(A = B = [1, 2, 1, 2]\). We will further explain how to handle this case below.

For the special case of \(N = 2\), the answer is now `YES` if \(A_1 = A_2 = B_1 = B_2\). Otherwise, the same logic from chapter 1 remains.

In the general case, checking for a rotation becomes more difficult now that duplicates are allowed. We can no longer map values to their indices as in chapter 1, since there may be multiple indices for a given value. We could try rotating \(A\) by each \(1..N\) and comparing to \(B\), but each comparison could take \(\mathcal{O}(N)\), for an overall time complexity of \(\mathcal{O}(N^2)\). A worst-case example for typical lexicographical comparison would be \(A = [1, 1, ..., 1, 2, 3]\), \(B = [1, 1, ..., 1, 3, 2]\).

One possible solution is to concatenate \(A\) with a copy of itself and search for whether \(B\) occurs as a substring using a linear time string-matching technique such as the Knuth-Morris-Pratt, Boyer-Moore, or Z algorithm. One thing to watch out for is the \(K = 1, A = B\) case above, where it's especially important to rule out cutting \(0\) or \(N\) cards. This can be done by deleting the first and last characters of \(A+A\) before searching for \(B\).

Another valid approach involves hashing. We can define some hash function \(h(v_1, v_2, ..., v_N\)\) that is sensitive to the order of its \(N\) inputs, but also supports computing the hash \(h(v_2, ..., v_N, v_1\)\) of the rotated array in \(\mathcal{O}(1)\), assuming \(h(v_1, v_2, ..., v_N\)\) is already given. We can then rotate just the hash of \(A\) one-at-a-time, comparing each to the hash of \(B\), for an overall \(\mathcal{O}(N)\) time complexity.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=B8ZoGe0k1-k)


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

class KMP {
  const vector<int> &needle;
  vector<int> table;

 public:
  KMP(const vector<int> &needle) : needle(needle), table(needle.size()) {
    for (int i = 1, j = 0; i < (int)needle.size(); i++) {
      while (j > 0 && needle[i] != needle[j]) {
        j = table[j - 1];
      }
      if (needle[i] == needle[j]) {
        j++;
      }
      table[i] = j;
    }
  }

  int find_in(const vector<int> &haystack) {
    int m = needle.size();
    if (m == 0) {
      return 0;
    }
    for (int i = 0, j = 0; i < (int)haystack.size(); i++) {
      while (j > 0 && needle[j] != haystack[i]) {
        j = table[j - 1];
      }
      if (needle[j] == haystack[i]) {
        j++;
      }
      if (j == m) {
        return i + 1 - m;
      }
    }
    return -1;
  }
};

int N, K;
vector<int> A, B;

string solve() {
  bool is_equal = A == B;
  // Check special cases.
  if (K == 0) {
    return is_equal ? "YES" : "NO";
  }
  if (N == 2) {
    if (A[0] == A[1]) {
      return "YES"; // Same numbers.
    }
    // Different numbers.
    if (is_equal) {
      return K % 2 == 0 ? "YES" : "NO";
    }
    return K % 2 == 0 ? "NO" : "YES";
  }
  // Check array is rotated by searching for B within (A + A).
  vector<int> AA(A.begin(), A.end());
  AA.insert(AA.end(), A.begin(), A.end());
  if (K == 1 && is_equal) {
    // If K = 1 and A = B, we can't match at index 0 or N-1 of (A + A),
    // since cuts of 0 or N cards are not allowed.
    AA.erase(AA.begin());
    AA.pop_back();
  }
  return KMP(B).find_in(AA) >= 0 ? "YES" : "NO";
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cin >> N >> K;
    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];
    }
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}