PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
GREEDY
PROBLEM:
Find the minimum number of parts to split a permutation so that we can rearrange the parts to form another permutation q.
EXPLANATION:
To solve this problem, a greedy approach will work. Note that each part must contain a contiguous sequence of numbers (e.g. 5, 6, 7 or 2, 3, 4, 5). Thus, we can just iterate from left to right and split whenever the difference between two adjacent numbers is not 1 (and the one to the right should be larger). This can be done in O(n) time.
Subtask 2 is almost the same thing. One way to solve subtask 2 is to convert the second permutation into 1, 2, ..., n while changing the first permutation accordingly and then solve the problem as in Subtask 1. The complexity is O(n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.