GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Saturday 10 September 2022

[Solution] Consecutive Cuts - Chapter 2 Meta Hacker Cup Solution



Note: The only difference between this chapter and chapter 1 is that here, card values are not guaranteed to be distinct.
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]:
Initially, the ith card from the top is A_i. Is it possible to cut the deck exactly K times to reorder the deck such that the ith 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 ith 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.

No comments:

Post a Comment