- 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.
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. ;)
Thanks for helping me!
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 :).
The problem statement is written in Vietnamese. Not sure if you can read it...
Problem statement
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.
Can you explain what you mean by "a deque is enough", please? Can we find the minimum/maximum in an interval using a deque?
Using Deque for the RMQ problem is applicable when our range queries are monotonic, that is, L[i] <= L[i+1] and R[i] <= R[i+1] with L[], R[] are left and right bounds of ranges. The algorithm is some kind of sliding window algorithm which you can find the pseudo code here:
http://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on
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).
Anyway, another question: Does this problem available on Codeforces?