All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

47's Code
No tags

Agent 47 is on an important mission to infiltrate a world renowned terrorist organisation. To pass the last security checkpoint he has to enter a N digit passcode into the machine. Thanks to Diana the digits of this passcode are known. 47 inputs these digits but gets an error message. The digits are correct but their order is not correct. 47 knows that the correct passcode is lexicographically largest combination of these digits (interrogation of some terrorist) . As the machine is old fashioned it only allows atmost K adjacent swaps of digits.

As the time is running out he calls in his IT guys at the agency and asks for their help. As a newly joined employee the task is forwarded to you. Help 47 bypass this code as fast as possible. The world's fate rests on your shoulders.


  • First line of input contains an integer T denoting number of test cases.
  • Each test case contains two lines, first line contains two integers N and K. Where N is the number of digits and K denotes swaps allowed.
  • Second line contains N space separated digits ai.


Print lexicographically largest combination of digits for each test case separated in a new line.


  • 1<=T<=100
  • 1<=N<=105
  • 0<=ai<=9
  • 1<=k<=n

Note: Use fast i/o to handle large test cases.

5 3
3 5 1 2 1
5 3
3 1 2 1 2

In the first test case:
First swap is between 3 and 5. Second swap between 1 and 2.
In second test case:
First swap between 1 and 2 and the passcode will look like: 3 2 1 1 2
Second swap between 1 and 2 and the passcode will be: 3 2 1 2 1
Third swap is between 1 and 2 and the passcode will be: 3 2 2 1 1.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications