STRSUB binary search

bro can anyone just explain me the logic to solve this problem. i just want to know the approach using binary search not segment tree @karangreat @ssjgz @ssrivastava990

@anon55659401 can you help ?

Problem link ? (20 characters)

https://www.codechef.com/problems/STRSUB

What a great problem! Completely blown my mind! I’ll take some time to explain the solution :slight_smile:

1 Like

The problem is really good.

1 Like

Yup, I took full 15 minutes of isolation to reach the solution , that too I guess I had luck : p

bro so how did you solved it… you are really great man… @anon55659401

1 Like

He is a pro. :joy::boom:

2 Likes

I am writing the solution !

yo bro… lets when we will reach there.

ok bro (20 characters)

Short solution:- for each ‘i’, you do binary search and find what will be the longest subarray starting from ‘i’ which will satisfy the condition.

For any (l,r), quickly, do a binary search and find a guy which just touches ‘r’.
All guys which did not touch will be added normally, all other in simple other way.
Long Solution:-Morning ko!

@anon55659401 bro subah hogyi… ab solution bata de bhai :grin:

explanation @anon55659401 @ssjgz @l_returns

:joy: :joy: isko help karo koi?

bhai fati padi h ab to ye question padh k irritation horha :joy:
@nuttela

Use two pointers in precomputation.
For each l, find max r which can be taken so that it follows this condition and just store all such r in an array ( a[l]=r )
Now also keep prefix sum of this array.
Values of r will always be increasing.
So now given l,r , binary search on r ( find value smaller than or equal to r ( do not do this on prefix sum array) ).
Now let this index be k.
So answer = pre[k] - pre[l-1] - ( k-l+1) ( roughly)
And also answer += r*(r-k) -(r-k) ( roughly again)
So idea is to find max r for each l ( let max r for each l1 be r1 and so on).
Then
Subarrrays (l1,l1) , (l1,l1+1) , (l1,l1+2),…( l1,r1) will be valid. So we fix l and find all possible r for it.
So this is my approach.

@l_returns bro i have understood some part can you explain with an example on-0001100
(l,r)=(2,7) and k=2
and how did you wrote that formula