xuanquang1999's blog

By xuanquang1999, 4 years ago, In English,
  • Statement:

Given a very large number X that has n digits, delete k (1 <= k < n <= 5*10^5) digits from it so that the remain part is as large as possible.

  • Input:

First line: Two numbers n & k.

Second line: Number X (without leading zero)

  • Output:

The largest number can be obtained after deleting k digits from it.

  • Sample test:

Input

4 2

1924

Output

94

I has met this problem more than five times in my life, but I can't find a solution for this. It would be appreciated if someone help me with this.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Just do it greedily. If you can delete numbers so that you get a 9 at the front then do it, if not try with an 8, etc. Then you move on to selecting the second most significant digit, etc. You just have to figure out how to do it efficiently ie better than O(nk) complexity, which can be done in various ways. ;)

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

this problem can be solved using dynammic programming with a complexity of O(N*10) in worst case let us maintain a DP[10][N] (N denotes the length of the number) table where DP[i][j] represents the index of the first occurence of digit i in the range from j to N. Now starting from the first index (MSB) you can check what maximum digit you can get at this position with the available range of K. this way you can move forward filling each position. Can you provide link to the above problem :).

»
4 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

The problem is solvable in O(N).
Instead of directly delete K digits, we can try to find the biggest number with N-K digits. This can be done with simple greedy. Let the string be s[1..n], for the first digit, pick the biggest one in s[1..n-k+1], suppose you find it first at index i1, then the range we should consider for the second digit is s[i1+1..n-k+2], then you got i2, .etc...
Observing that these ranges are monotonic, a deque is enough, or you can build a RMQ sparse table, or a Segment tree.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

We can take a array of length 10 (0-9). Each of its index will represent digit and value within that array index will represent how many times this digit was repeated in original number. For digits K, we travel through this array and keep only those values in this array that add up to K from index 0 to 9, rest values we can equate to 0. We again scan original number left to right, For every digit we check if we it has non-zero value present in our aux array if so, we will skip this digit while forming our answer number and decrement the count of array value for that digit by 1. Complexity, O(n).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyway, another question: Does this problem available on Codeforces?