DMOPC '18 Contest 1 P2 - Sorting

View as PDF

Submit solution



Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:

Problem type

You are given a natural number K and a permutation P of the numbers 1, 2, \ldots, N. Since P is a permutation, it has length N and each number from 1 to N appears exactly once. You are allowed to swap two elements if their positions are exactly K apart. In other words, you may swap P_i and P_j only if |i-j|=K. Determine if P can be sorted from least to greatest.

Constraints

1\le K < N\le 100

Subtask 1 [40%]

1\le K\le 2

Subtask 2 [60%]

1\le K<100

Input Specification

The first line will contain two space-separated integers, N and K.
The next line will contain N space-separated integers, P_1, P_2, \ldots, P_N.

Output Specification

Output YES if it may be sorted and NO otherwise.

Sample Input 1

5 1
1 4 3 2 5

Sample Output 1

YES

Explanation for Sample 1

Swap P_3 and P_4. The sequence is now 1 4 2 3 5.
Swap P_2 and P_3. The sequence is now 1 2 4 3 5.
Swap P_3 and P_4. The sequence is now 1 2 3 4 5, which is sorted.

Sample Input 2

5 2
5 4 3 2 1

Sample Output 2

YES

Explanation for Sample 2

Swap P_2 and P_4. The sequence is now 5 2 3 4 1.
Swap P_1 and P_3. The sequence is now 3 2 5 4 1.
Swap P_3 and P_5. The sequence is now 3 2 1 4 5.
Swap P_1 and P_3. The sequence is now 1 2 3 4 5, which is sorted.

Sample Input 3

5 3
5 4 3 2 1

Sample Output 3

NO

Comments

There are no comments at the moment.