aravind.nujella's blog

By aravind.nujella, history, 3 months ago, In English

Assume a codeforces like platform where there are $$$n$$$ users and their ratings vary over time $$$[0, T]$$$. Now given an interval $$$[l,r]$$$, we would like to find top k profiles which had highest delta in that interval.

Is it possible to answer this query without iterating over $$$n$$$ interval sums? For example we can get $$$O(n\log(n)\log(T))$$$ by maintaing fenwick tree per user and sorting the list of interval sums.

Edit: Added requirement to avoid looping over $$$n$$$ users..

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it