### 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.