arman024hasan's blog

How to solve this kind of problem?
By arman024hasan, history, 7 years ago, In English

Link: https://toph.co/p/cut-the-rope Which algorithm suits this kind of problems? I tried segment tree.

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

»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

A treap (or any balanced binary search tree) will be enough.

→ Reply
»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

First, find out all lengths of ropes that would appear during process (for example, keep sets of cut points and lengths of ropes). After that, you can use coordinate compression and segment-sum, point-update segment tree that keeps number of ropes of given length. For "cut" queries just do three update queries, for "k-th by length" do tree descend to find smallest length l that there are at least k ropes of length l or less.

→ Reply