Problem: consecutive_cuts_ch1 (2022 round1)

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

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

*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:905763186973896|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 200\)
\(2 \le N \le 500{,}000\)
\(0 \le K \le 10^9\)
\(1 \le A_i, B_i \le N\)
**\(A\) and \(B\) are each permutations of \(1..N\).**

The sum of \(N\) across all test cases is at most \(5{,}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 4 3
2 4 3 5 1
4 10
3 1 4 2
1 2 3 4
4 0
3 1 4 2
2 3 1 4
3 3
3 2 1
1 3 2


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


Solution: When \(K = 0\), we can't perform any cuts, so the answer is `YES` if and only if \(A = B\).

When \(K = 1\), first note that the answer is `NO` if \(A = B\), since we we are forced to disrupt the equality with a cut (which cannot be \(0\) cards). Otherwise if \(A \ne B\), we see that cutting the deck once is the same as rotating an array. Checking if a *sorted* array \(A\) has been rotated to \(B\) can be done by checking that each pair of adjacent values in \(B\) are in order, with exactly one exception. Since \(A\) is not guaranteed to be sorted, we can precompute a mapping of \(A\) values to their indices, and instead check that the mapped indices of all \(B\) values are in order, with exactly one exception.

When \(K \ge 2\), we can observe that any sequence of rotations that doesn't preserve the original order can be replicated with just one rotation. Again, we can just output `YES` if \(B\) is a rotation of \(A\). If \(A = B\), we can also output `YES`, as it only takes one rotation to restore any rotated deck back to the original order.

A special case to watch out for is when \(N = 2\), e.g. \(A = [1, 2]\). When \(B = [1, 2]\), the answer is `YES` if and only if \(K\) is even. When \(B = [2, 1]\), then answer is `YES` if and only if \(K\) is odd. The answers are flipped if \(A = [2, 1]\).

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


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

const int LIM = 500000;

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 (K == 1 && is_equal) {
    return "NO";
  }
  if (N == 2) {
    if (is_equal) {
      return K % 2 == 0 ? "YES" : "NO";
    }
    return K % 2 == 0 ? "NO" : "YES";
  }
  // Check array is rotated.
  int num_out_of_order = 0;
  unordered_map<int, int> pos;
  for (int i = 0; i < N; i++) {
    pos[A[i]] = i;
  }
  for (int i = 0; i < N; i++) {
    if (pos[B[i]] > pos[B[(i + 1) % N]]) {
      num_out_of_order++;
    }
  }
  return num_out_of_order == 1 ? "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;
}