JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
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] appears
then 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.
RSS