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 .

Mathematical Proof of why creating new bar will resutl adding suffix in our score . 2 , 1, 3 , 1, || 2, 4, 3, 4, 1, 0 , 1 score=0*(7)+ 1*(14) ; now create new bar 2 , 1, 3 , 1, || 2, 4, || 3, 4, 1, 0 , 1, , 2 new score=0*7 + 6*1 + 8*2 ; diff= newscore — score = 22 — 14 = 8 = suffixscore(8) multipant is just increased by 1 so diff will be multiple of 1 of sum of all on right side .

For my answer : 294660322