CrapCoder's blog

any hint to solve lightoj 1187

By CrapCoder, history, 8 years ago, In English

i'm stuck on this problem

http://lightoj.com:81/volume/problem/1187

forum says there is an O(n) greedy and an nlog(n) solution with BIT/segtree .can you give any hint or idea so i can get closer to solve this.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

consider the sample test:

3

0 1 0

fill the leaf nodes of your segment tree by 1 such the the leaves are 1(st=ed=1) 1(st=ed=2) 1(st=ed=3).

scan right to left from your input array.

1st iteration: you have 3 people and 0 people is taller than him so kill (3-0)=3rd person from the tree.

now the tree looks like 1(st=ed=1) 1(st=ed=2) 0(st=ed=3).

2nd iteration: you have 2 people and 1 people is taller than him so kill (2-1)=1st person from the tree.

now the tree looks like 0(st=ed=1) 1(st=ed=2) 0(st=ed=3).

finally find the index(st or ed of the node as they are same) which contain 1.

try by your self.

then you can take help from my code.

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

    How does your method work for the 2nd sample case?

    3 0 1 2

    → Reply