snacache's blog

Help with Live Archive problem — Generations
By snacache, history, 9 years ago, In English

Hi everybody!

I was solving some ACM regional problems from Live Archive and I got stuck realy bad with this task:

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=519&page=show_problem&problem=4002

There is a family of dragons represented as a rooted tree. Every dragon has a hatchyear and a deathyear, and they can have children. So, the task is to find for every dragon the deepest descendant that lives during its lifetime (between its hatchyear and deathyear).

I tried some things without any success, always receiving TLE or WA verdict.

However, I made a naive solution with dfs over all the dragons, looking for the deepest descendant and much to my surprise it was accepted O.o . The maximum amount of dragons can be as large as 50000, so in the worst case I'm pretty sure that N dfs shouldn't work (but it did)

Although I could "solve" this task, I really want to know if there is a solution that actually makes sense with such constraints. I thought about some queries with segment trees or some interval data structure, but nothing really useful came to my mind :(

Thanks!

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I code that problem a few months ago, and Im pretty sure that O(n^2) shouldn't pass as you said. I was looking at my code and it is just a simple SegmentTree+Dfs problem. Total Complexity O(nlogn)

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

    I knew it! hahaha I knew it had something to do with segment trees!

    Can you give me a hint? I was trying using RMQ (maximum) to find the deepest descendant of a dragon, updating the intervals with the depth of the dfs. The answer for a dragon should be the maximum found in its lifetime (using hashing because hatchyear and deathyear can be as large as 10^9) but this won't work because it will find dragons that are not its descendants :-(.

    Thanks!

    → Reply