You are not logged in. Please login at www.codechef.com to post your questions!

×

How to solve problem Match2 of September Lunchtime 2018

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

vishrut_10's gravatar image

3★vishrut_10
262
accept rate: 33%

edited 30 Sep '18, 15:00


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.

link

answered 30 Sep '18, 15:27

abhi55's gravatar image

4★abhi55
426
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) vishrut_103★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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