Harder version of the BINSUBS problem in Jan Lunchtime

general
,
1

In the original version of the problem(BINSUBS) in January Lunchtime, we are given a simple Binary String and we have to find the minimum number of characters needed to be removed to make it a non decreasing string.

Try to solve the same problem with some minor modifications. Instead of 0’s and 1’s, the string can be made up of any of the 256 ASCII characters. The input string can have a maximum size n of 10^7. Find the minimum number of characters needed to be removed to make it a non decreasing string.

Challenge : An O(nlogn) might not pass.

2 Likes
2

Can you tell the expected complexity ?

3

You can come up with any kind of complexity. Just make sure that the total number of operations are under 1e9.

I was actually able to come up with an algorithm that takes approximately 0.5e9 operations, whose time complexity was O(n*log2(256)). The bound might be a bit too tight. Ignore that if you want to. Just explore the various ways to do it; the learning around this problem was good for me.

1 Like
4

I’ll give it a try for sure. Please help If I fail to find an approach other than Longest increasing subsequence

5

Yes, LIS is the way. Learn of the various methods to do that.

1 Like
6

Okay, but I don’t think that O(NlogN) is the desired solution, isn’t it ?

7

Can you provide detailed solution for this?

8

It might run or might not. Will be very close to 10^9.

1 Like
9

https://cp-algorithms.com/sequences/longest_increasing_subsequence.html#toc-tgt-9

Read a little about the fenwick tree(No background is required other than “prefix sum”).

1 Like
10

Why though? according to contraints, N=10^7 so NlogN \approx7*10^7 which I think is appreciably less than 10^9

11

Are you sure the log here is to the base 10?

1 Like
12

You’re correct it’s base 2 because we use binary search in the algorithm. In that case it’d be NlogN \approx 2.5 \times10^8 operations.

13

These are generally the number of higher level steps. Under each step, there can be multiple operations.

Example :
int sum=0;
for(int i=0;i<n;i++)
{sum+=i;sum+=i+1;}

We call this a O(n). But overall there will atleast 3n or 4n operations.

We generally ignore these constants when the time bounds are not too tight but they are important when the bounds are very tight.

So, O(nlogn) might not actually be 2.5*10^8 operations.

1 Like
14

Yes I agree, These constants factor optimizations can’t be ignored when time limit is so tight.

15

Ignore them for now.
Just read about the various methods of solving LIS problem.

1 Like
16

Sure Sir, thanks. I’ll read it from the resource you provided above.