ritik_patel05's blog

By ritik_patel05, history, 4 years ago, In English

Problem : HELPR2D2 — Help R2-D2!

Solution : Link

Approach : I stored in each leaf node K(Volume left to use) and in the parent node, I summed up the volume of children's node. For querying, I try to go as much left as I can and update the volume used. I cross-checked with several cases. But cannot find where it's going wrong on submission.

If someone has solved this question, I really appreciate your help. Thank you!

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

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

Why are you storing sum of child values in nodes of segment tree? When deciding whether to move left or right from a node, you need to know if the left part contains any node with value greater than or equal to the value you are searching. Instead you are checking that the sum of values on that part is greater than the required value or not which is wrong. Changing your segment tree to store max of child nodes gives AC.(if max value on left part is greater than the value you are looking for then at least one node in that part has an equal or larger value)

Spoiler
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yeah now I get it if once I go to left as I am storing sum of child nodes. It might say to me that yes there's a node down there with free volume available. But it isn't always true.

    Max should do the trick to check. Thanks a lot ankurdua15!