**This is just for my self , If it is helpful for you , I am glad (but most porbably not)**↵
C. Competitive Fishing↵
==================↵
In this question , we have to divide the array into m non empty group (group do not need to be of same size ) , such that if we assighned score to first group as 0 , second group to 1 and third group to 3 and so on , the score of Bob should be greater than or equal to k , and we have to find minimum m . ↵
Example : ↵
6 3↵
001110↵
and in the question , it is stated that 0 is Alice win and 1 is Bob's win↵
So we can divide this into many segment one such is ↵
00 || 111 || 0 here 0*( BobScore(0)- alice score(2) )+ 1*( Bob Score( 3) -0) +2*(0-1*1) = 1 So we have to get this value greater than or equal to k . ↵
One key observation is ↵
if there is already k bar (k+1 segment) , than if we create one more segment at ith index (.. i-1 || i.....) then total sum will of score will be just suffix of resultant score . ↵
Resultant score is if we got 1 at n-1 index than score=1 else score =-1 , ↵
and by suffix sum in iterating from n-1 to 0 , if we find 1 we will increase 1 else decrease 1 , ↵
if we creaete bar at i1 , i2 , i3 , i5 then our final sum will be suffix[i1] + suffix[i2] + suffix[i3] + suffix[i5] , ↵
Here key observation is that we can't create bar at i0 or at index 0 , becuase here we assumed that bar is created on the left side so , creating bar at left side means doing nothing , ↵
So we will not take this case . ↵
↵
Finally we have to maximisse this ↵
suffix[i1] + suffix[i2] + suffix[i3] + suffix[i5] , ↵
so we will sort our suffix array , and iterate from left to right and see if our sum>=k than ans will be i+1+1 (indexing is 0 ) and if we do not get any answer so ans will be -1 . ↵
↵
↵
For my answer : ↵
[submission:294660322]↵
C. Competitive Fishing↵
==================↵
In this question , we have to divide the array into m non empty group (group do not need to be of same size ) , such that if we assighned score to first group as 0 , second group to 1 and third group to 3 and so on , the score of Bob should be greater than or equal to k , and we have to find minimum m . ↵
Example : ↵
6 3↵
001110↵
and in the question , it is stated that 0 is Alice win and 1 is Bob's win↵
So we can divide this into many segment one such is ↵
00 || 111 || 0 here 0*( BobScore(0)- alice score(2) )+ 1*( Bob Score( 3) -0) +2*(0-1*1) = 1 So we have to get this value greater than or equal to k . ↵
One key observation is ↵
if there is already k bar (k+1 segment) , than if we create one more segment at ith index (.. i-1 || i.....) then total sum will of score will be just suffix of resultant score . ↵
Resultant score is if we got 1 at n-1 index than score=1 else score =-1 , ↵
and by suffix sum in iterating from n-1 to 0 , if we find 1 we will increase 1 else decrease 1 , ↵
if we creaete bar at i1 , i2 , i3 , i5 then our final sum will be suffix[i1] + suffix[i2] + suffix[i3] + suffix[i5] , ↵
Here key observation is that we can't create bar at i0 or at index 0 , becuase here we assumed that bar is created on the left side so , creating bar at left side means doing nothing , ↵
So we will not take this case . ↵
↵
Finally we have to maximisse this ↵
suffix[i1] + suffix[i2] + suffix[i3] + suffix[i5] , ↵
so we will sort our suffix array , and iterate from left to right and see if our sum>=k than ans will be i+1+1 (indexing is 0 ) and if we do not get any answer so ans will be -1 . ↵
↵
↵
For my answer : ↵
[submission:294660322]↵
