pritishn's blog

By pritishn, 4 years ago, In English

Hi,
I had made this problem( https://www.codechef.com/FTCF2020/problems/TRADE2 ) and the approach that I used to solve was make a segment tree over a multiset table of size 10^5. In that approach , table[i] would denote prices of phones with speed i. Segment tree would work on the .begin() values of the multiset tables.

I wanted to know if there's any alternate approach to this problem. Thanks in advance!

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

We can solve it offline by taking a list of all phones (even ones that are held by customers) and sorting it by speed. Additionally, each phone has an "active" boolean indicating whether it is currently able to be bought. Now, we need to perform queries of the following form:

  • toggle a single element from active to inactive, or vice versa.
  • ask for the minimum price on a suffix, only taking into consideration elements which are active.

We can do this with a segment tree, where each node stores the index corresponding to an active phone with minimum price on an interval. The details are not that difficult.

To process a customer, we use binary search to find the leftmost element in the array satisfying our speed conditions, and then query the segment tree to get the best phone on the corresponding suffix. Then toggle the activity of both the phone we came into the shop with, as well as the phone we just found.

Total running time is $$$O(n+q\log(n+q))$$$.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you allow submissions for the problems?