MCO16401 - Editorial

cakewalk
greedy
mco16401

#1

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:


#2

Hi!
I attempted this problem. I compare the elements of the two arrays and if they are unequal, I increase the split count and if they are equal, I just increase the count by 1 till I come to the point they are unequal now. Here is my solution. It is incorrect but I cannot debug it. Kindly help me with it.
https://www.codechef.com/viewsolution/23440892