How to solve problem Match2 of September Lunchtime 2018

general
1

Can someone suggest the optimal way to solve the problem “Match2” ?
problem link: https://www.codechef.com/LTIME64B/problems/MATCH2

Thanks

2

the approach i think but not sure it will work is to use fenwick tree to update in range and get cumulative sum of range 1 to N.at each index initially if A[i]==B[i] value of frequency at that index is 1 otherwise 0.so, value of initial pr will be Sum(1,n).and when updating in range if new value c==B[i],for each l<=i<=r we update frequency to 1 otherwise update frequency to zero.

i learned recently about binary indexed tree so, not confident about approach.if there is any mistake or in scenarios where to use binary indexed tree correct me with explanation.

3

Hi @abhi55,
I am unable to understand, “when updating in range if new value c==B[i],for each l<=i<=r we update frequency to 1 otherwise update frequency to zero.” this line of your explanation. Are you trying to say that we need to run another loop from l<=i<=r to compute this, if yes then this solution is almost like brute force ?? Please correct me if i am wrong.

Thanks