Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Maximize Mismatch

By upobir · Limits 1s, 512 MB · Custom Checker

You are given a permutation PP of number 1,,n1, \cdots , n (I.E. each number occurs exactly once). Now you want to introduce some chaos to this permutation. To introduce chaos, you can perform at most kk swaps between adjacent positions. The chaosness of the final permutation is calculated as the count of the mismatches I.E. the number of indices ii such that P[i]iP[i] \neq i (the indices are 1-indexed). Output the maximum number of mismatch you can make and also output such a sequence of swaps.


There will be TT testcases.

Each testcase begins with a line containing space separated numbers nn, kk. Next line contains nn space separated numbers representing the initial permutation.

1T1051 \leq T \leq 10^5
3n1053 \leq n \leq 10^5
0kn0 \leq k \leq n
sum of nn over all testcases 105 \leq 10^5


For each testcase first output one number ss in a line, ss is the number of swaps you will perform. In the next ss lines, output the swaps to be performed. To swap positions xx and yy output the numbers xx and yy. Note that the swaps you perform should be between adjacent positions.

In case of multiple answer, you can output any.


4 2
1 4 2 3
10 2
1 2 3 4 5 6 7 8 9 10
1 2
1 2
9 10



    100% Solution Ratio

    MursaleenEarliest, 4d ago

    Tahmid690Fastest, 0.0s

    MursaleenLightest, 1.6 MB

    MursaleenShortest, 921B


    Login to submit