MAX_NUM - finding maximum possible number

no tags 

Given a number n, Find out what max possible number you can make by deleting exactly k digits.

T : no of test cases <= 10^3

1 <= no of digits in n <= 10^5. (n might contain leading zeros)

0 <= k <= n

if value of n is equal to k. then just print a new line.


T: no of test cases

T line follow

every line has

n , k


max possible number


1223 2
8756 2

Note that left to right order should be maintained. As in the example given answer is 23 not 32.

hide comments
Thotsaphon Thanatipanonda: 2013-05-02 06:48:14

My Java program can run within 0.20 sec without any special optimization.

Akb: 2013-05-02 06:48:14

what to print if k=(no of digits in the number)??
why did you keep your problem incomplete?

:D: 2013-05-02 06:48:14

The only real problem was that i/o was incorrect. You may change the time limit, so that JAVA could pass easier.

praveen123: 2013-05-02 06:48:14

I have updated the problem statement to make it more cleaner, I have also modified the test cases. Three solutions have been accepted.
Please give your opinion on the quality of problem and also on the issue of time limit.

praveen123: 2013-05-02 06:48:14

hi all,
First of thank you Alex Anderson for giving me test cases for checking input - output.
I had a small bug in the code. when some two digits coincided. So I am changing input and output file now and rejudging all the submission.
@:D , if you feel that judge data seems to be correct or may be want to suggest some improvements for the problem, I will really appreciate that.
Please make problem visible when all the conflicts are over.

Last edit: 2013-02-10 03:13:36
:D: 2013-05-02 06:48:14

Re praveen123: Pretty much what Robert said. For test cases here my solutions coincide. Could you print some small case where any of us fails?

Robert Gerbicz: 2013-05-02 06:48:14

My code prints the same answers for that two input. But you can see our code as (here) you are the problem setter.

Say n has got L digits; after deleting k digits in every case you have got the same length=L-k. It means that if you want the maximal number you have to start with 9 (if in the number there is a 9 and you can complete the number to have L-k digits), in the 2nd place you will see again 9 in general etc. so for me it is not surprising that you see a lot of consecutive 9's.

praveen123: 2013-05-02 06:48:14

:D , you are printing out a huge streak of 9's as in the case of Robert.
Could tell me your understanding of the problem so that I could see that something is incorrect at logic side or implementation side

Added by:praveen123
Time limit:0.407s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64