Hi, can u please explain more how to do this with Binary index tree + bit masking. Stuck for quite a while now! Also what do u mean by " *Try to count number of pairs using truth table of these operators. "*

Active In

Competitive Programming

Featured Contributions

reply in this discussion

Hi, can u please explain more how to do this with Binary index tree + bit masking. Stuck for quite a while now! Also what do u mean by " *Try to count number of pairs using truth table of these operators. "*

Read more… (43 words)

reply in this discussion

Hi Kunal,

First understand how we can use a priority queue (heap) for our advantage here and what makes taking heaps as the choice of data structure in this example. Our requirement is to get the max (and the min) with every swap.

The priority queue (heap) helps us here since we don't have to take the pain of getting the max or the min from the shelves by sorting or anything else.

Whenever we need to get the max or the min from the heap, just the top element gives that in O(1) time. And for k swaps, inserting into the heap will take theta(k*log(n)) time. For building the heap, it will be n*log(n) time making the total of theta(k*logn + n*logn) time complexity which is good enough for us in this example.

As far as implementation goes , u can simply maintain min and max heap for each shelf and u r done. I think it's pretty easy if u understand the concept of heaps. Learn heaps (priority queue) ...

Read more… (194 words)

reply in this discussion

For longest path, first do the topological sorting and then take the vertices one by one. Read more at Longest Path in a Directed Acyclic Graph

Read more… (26 words)

reply in this discussion

Use *scanf* instead of *cin* in case u are getting TLEs. Happy coding :)

Read more… (14 words)

reply in this discussion

Thats what, I dont think we have to take absolute value, it will always be (parent_value-child_value) as far as i can think from this line in question -> " He has already decided that he will present evidence that wealth falls rapidly as one goes down the organizational tree. "

Read more… (50 words)

reply in this discussion