Scalar Question (2)

help
5

finished.

1 Like
6

Is there a way to solve these problems now ?

7

NOPE.

8

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)

1 Like
9

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

1 Like
10

Hint -> Try dividing such that for that very bundle no further division is possible for him

1 Like
11

using stack found position of next 1 and prev 1 for every index , simple prefix sums from here

1 Like
12

like dividing it to a prime . . . I tried it but can’t think more. any hint?

13

Do you know how to solve the 3rd and the 5th problem?

14

How to solve that permutation problem?

15

Can anyone explain me what 3rd problem(permutation wala) was asking for I was unable to understand the question?

16

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

17

@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

18

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

19

No, not fenwik tree but I used prefix count array for 0s

20

please explain the proof

21

@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

22

how you are shifting L and R according to the vector ???

23
  1. Binary search with lower_bound for L(will return index greater then L having 1)
  2. Binary search with lower_bound for R and if prev R is not equal to new R(iterator- - )
1 Like
24

it can be easily solved in O(n) for preprocessing and O(1)
for queries
basically there are 3 steps;
coutarray -count no of zeroes till i index
leftarray-store index of latest 1 on left side
right array-store index of latest 1 on right side
now for queries L R
we need to check right[L]<=R&&LEFT[R]>=L
THEB RETURN COUNTARRAY[left[r]]-COUNTARRY[right[l]]
OTHERWISE -1