JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Indexed Trees Explaination of the solution to prob 2 in the article
 Explaination of the solution to prob 2 in the article | Reply It would be very helpful if someone could explain the solution to prob 2 in the article.Specifically, i don't understand the part of turning the cards between [i,j] in O(log n) complexity.Thanks!
 Re: Explaination of the solution to prob 2 in the article (response to post by chetan1507) | Reply suppose interval [i,j] appearsthen update(add 1) all intervals containing i in your BIT (it will take log(n) time )update(add -1) all intervals containing (j+1) in your BIT (log(n) time).now you can find your answer using cumulative frequency mod 2;finding cumulative frequency also takes log(n) time."i think i'm not wrong."
 Re: Explaination of the solution to prob 2 in the article (response to post by chetan1507) | Reply Let me describe a bit more detailed what renesh was trying to explain.Assume you have bunch of interval in which cards are turned. Denote them by {(a1, b1), ..., (an, bn)}. If we mark by 0 face down, and by 1 face up, then every turn will change 1 to 0, and vice versa.If you want to count how many times card at position idx is turned, you have to count number of intervals (a, b) such that a <= idx and idx <= b. Or, you have to count number of intervals (a, b) such that a <= idx and *subtract* number of intervals such that b < idx (note that b < idx implies a < idx as well). Is it clear why you are supposed to do this? Now, that means you have to deal only with ai and bi values.Rest of the idea relies on the definition of BIT.Best regards,EDIT: You might want to try to solve this problem.
 Forums Tutorial Discussions Binary Indexed Trees Explaination of the solution to prob 2 in the article Previous Thread  |  Next Thread