DOSA - Lalith Dosa
Lalith is going to have dinner and he has N dosas in front of him with their prices represented by sequence of integers a1, a2, a3 ... an.
And he has decided to eat in a different manner. You are free to replace the price of any dosa with any positive integer.
How many prices (integers) must be replaced to make the resulting sequence strictly increasing?
The first line of the test case contains an integer N - the number of dosas.
The next line contains N space separated integers where the ith integer is ai, representing the price of the i-th dosa.
Output the minimal number of prices(integers) that should be replaced to make the sequence strictly increasing.
0 < N <= 10^6
0 < ai <= 10^9
Sample Input #1
1 7 10 2 20 22
Sample Output #1
Sample Input #2
1 2 2 3 4
Sample Output #2
In the first sample input, we can replace 2 with any integer between 11 and 19 to make the price sequence strictly increasing, hence the output is 1.
In the second sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the price sequence.
Read about longest non-decreasing sequence
Very Good Problem, Learnt something New :)
Hint : LIS + binary search
id 17120850 can i know which test case my submission fails
O(N LOG(N)) will pass
finally got it:)
Be careful with case like:
Getting WA , explain why my code fails ?
[spoiler removed]Last edit: 2014-01-17 18:10:30