×

# How to solve problem Match2 of September Lunchtime 2018

 0 Can someone suggest the optimal way to solve the problem "Match2" ? problem link: https://www.codechef.com/LTIME64B/problems/MATCH2 Thanks asked 30 Sep '18, 14:21 26●2 accept rate: 33%

 0 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. answered 30 Sep '18, 15:27 4★abhi55 42●6 accept rate: 5% 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 (30 Sep '18, 18:30)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×553

question asked: 30 Sep '18, 14:21

question was seen: 234 times

last updated: 30 Sep '18, 18:31