coderbond007's blog

How to solve this online query problem?
By coderbond007, history, 7 years ago, In English

Problem says that we have to get rank of the favourite team after updating rank of team t at each query. Can anybody suggest me how to solve this online query problem?

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

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

Your rank is number of teams with more problems than you + number of teams with same problems as you but less penalty.

We can calculate the number of teams with more problems by using binary indexed tree built over problems where they contain the number of teams that solved them, then the number of teams with larger problems is query(maximum_problems) — query(team #1 problems). After each query make sure you update your BIT.

For the second part use K balanced binary trees which contains the penalties of each team that currently have solved exactly p problems. Then you need something to answer kth order statistics queries which you can implement quickly using this link, and again after each event update your balanced binary trees. ( Memory usage will be O(N) because we store teams that solved exactly P problems).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. It's the second time I am coming across Policy-based Data structures. Java does not have such inbuilt library for Ordered Set :( I have a doubt regarding Ordered Set. Is ordered set a type of treap? If it's a variance of Treap, what extra factors are added in Treap to make it work like Ordered Set. As I want to implement it in Java, without knowing the functioning I can't code it.

    → Reply