Given a string S of zeroes and ones. Given range (L,R), you have to find the 1st and last occuring 1 in the range and tell the number of zeros between the first and last ones including L and R index.
1<=L,R<=10^5.
Eg:
0010011001
L,R=1,8
Output: 2
Pls help in this question. O(n^2) not working
I solved it using prefix sums.
Store the position of 1’s and take lower bound of each.
Contest finished or running ??
finished.
Is there a way to solve these problems now ?
NOPE.
I did it by maintaining a array of total 0s till a particular index(lets say temp array) .
and also a vector for all 1s to shift my L,R to required index(1s ) in (log n) time. Then I first shifted my L,R accordingly and then just saw difference of value in temp array of L and R.
Hence Creating temp and 1s vector ->O(n)
each query ->O(log n)
I maintained 3 array one prefix-sum array for 0s, next_pos_of_1 array, prev_pos_of_1 array and answered queries in O(1).
.
Can any one help with the Game question where you have to divide the bunch in equal parts
Hint -> Try dividing such that for that very bundle no further division is possible for him
using stack found position of next 1 and prev 1 for every index , simple prefix sums from here
like dividing it to a prime . . . I tried it but can’t think more. any hint?
Do you know how to solve the 3rd and the 5th problem?
How to solve that permutation problem?
Can anyone explain me what 3rd problem(permutation wala) was asking for I was unable to understand the question?
Just a observation , If B has no factor between [C,B) ==>ans=0(can’t divide equally by 1st player).
if it has a factor ->. if (A is odd){return 1;} else {return 0;}
as can be proved easily try otherwise I will tell
@anonym_chef So, u find the sum between next_pos_of_1(from L) and prev_pos_of_1(from R) and than u do (R-L-prefix_sum) ? U did prefix sum using fenwick tree? then how u can answer queries in O(1), it will take logn
@knightknight
For eg, a,b,c=5,92,10 then ever if u finding prime factor, u can’t divide becaz after dividing quotent is less to C. factors of 92 = 46,23,4,2 but how can u divide ? @knightknight
No, not fenwik tree but I used prefix count array for 0s
please explain the proof
@anonym_chef i understand u used prefixsums for fidning next 1 and prev 1 but how did u ans. queryies of L,R. Did u count the sum or how? pls explan