PalForce's blog

By PalForce, history, 2 years ago, In English

Avoiding Airports

I have been trying to solve this question on kattis(Avoiding Airports) since 7 months. I know the dp solution. Which is sort all flights by start time and then calculate total frustration of taking each flight.

{flight[i].s is start time of flight i and flight[i].e is end time of flight i}.

frustration of i'th flight f[i] = min(f[j]+(flight[i].s-flight[j].e)^2) for j < i . Many people then told me that you can make this faster by using convex hull trick. Where slope here is -2*flight[j].e and constant = dp[j]+flight[j].e^2 So for a particular flight with start time flight[i].s I have to find the best (slope,constant). But I don't know how to make the query because the slope/-2 < flight[i].s has to be satisfied. How can I still make queries. Most problems I took to learn CHT didn't have any conditions on the slope. If someone can give another example to some problem that would also help.

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

»
21 month(s) ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I was wrong.

»
15 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

Have you already solved this problem?

If not, I think it might help.

If yes, this comment is for others who is also seeking help.

My approach is to solve it with a persistent Li-Chao tree. Lichao tree kind of works the same as convex hull.

Basically the trick is to make a different tree for the different airports. And when you reach a certain airport $$$a_i$$$, update the $$$a_ith$$$ persistent tree.

It will take at most $$$mlog(max(e_i))$$$ node, which is $$$4*10^6$$$, and will pass the memory limit. Thus, you won't need to maintain condition on a slope.