javacoder1's blog

WHY MY CONVEX HULL WORKS!!!
By javacoder1, history, 8 years ago, In English

I was trying to solve this question of dynamic programming using the convex hull trick .

http://mirror.codeforces.com/contest/319/problem/C .

Here is a link to my implementation which got accepted.

http://mirror.codeforces.com/contest/319/submission/23071655.

But this submission is raising more concerns .In the query part of the struct i made for cht , i know i am supplying lines whose slope are continuously decreasing with x.So the query part is a kind of pointer algorithm which evaluates the intersection between the last two lines in the hull and moves forward if it finds it adequate because the points in which i am eveluating the lines are strictly incresing.But the problem is that i am popping lines in the insert part so suppose we have 4 lines in the hull and the cur pointer is at the last line.The next inserted line comes and pops everything but the last one so what cur was previously pointing does not exist , so this code should have given RTE , but why not ? I hope some experienced person might look through this code explaining why this didn't happen as well as whether my code is fully correct because i tried to make this one for the case too where the slopes are equal which is not demanded in this question.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Though this comment is irrelevant to this blog but recently i am seeing people who don't want to help others but are having the courtesy to give negative upvotes. Man , i know that you are liberal but why are you doing so , if you don't want to help press the back button on your browser and leave . By doing so you are also making this post uninteresting for those who want to help . Please cooperate!!

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

Please help me!!

→ Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +9 Vote: I do not like it

I too don't understand codeforces users behaviour. There are lots of upvotes on jokes, but almost no upvotes on interesting stuff. I think some posts asking for help should be downvoted however, thinking about those which question has been answereda thousand times on the internet. See this, for example: http://mirror.codeforces.com/blog/entry/49132 . It's just useless.

Ok, done with my complaints lol. I made some tests:

http://mirror.codeforces.com/contest/319/submission/23074890

The situation you described never happens on the testcases (cur never points to an empty line). I'll try to think why.

EDIT: More strictly, you never remove the line that was chosen as cur:

http://mirror.codeforces.com/contest/319/submission/23075005

I'm pretty sure this is related to the problem. I think the fact you'll never remove the line that was chosen is true and can be proved, but I can't get to it.

EDIT 2: Ok, my last statement is true. Here's why (drawing will help):

So you choose line r for a given a_i. Now, the next line we will add to the convex hull is going to cross the y axis at the same y-coordinate that line r has when x = a_i (this is because of the DP recurrence). b_i is always greater than zero, so our new line will cross line r at an x-coordinate greater than a_i. This way, our new line crosses line r at a x-coordinate greater than the one where line r crosses the line before it. This way, line r won't be "useless" and won't be removed.

This is an explanation about why your code works. Note that, the way I see it, your solution works because of the way the DP recurrence works. Maybe its a more general property, I don't know. You can try playing around for yourself.

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

    Thanks man , there are definitely good people like you !! Yeah that cur points to an empty line thing never happens in this question and when i browsed through the codes of few participants , i found some of them implementing this trick or getting away out of this using binary search. This trick is similar to the two pointer algorithm but i am unable to think of a case which contradicts this nor the web has anything relevant to this. That is the reason i was asking this question because the ambiguity is in the query part only. It might happen that the cases are weak or i am missing something.So i posted this blog with the intention that some experienced person would clarify this. Let's hope for the best !! BTW thanks again!!

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

    PLEASE IGNORE!!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +4 Vote: I do not like it

      Check my new update.It should make things clear now.

      I also modified your code a bit:

      http://mirror.codeforces.com/contest/319/submission/23075126

      I like to write put an eps value (1e-12) just to be sure with doubles.

      Also, the way I learned, my function "useless" is different from yours. I'm not sure if it makes any difference. (I'm testing if left crosses right before left crosses middle, instead of testing if middle crosses right before left crosses middle).

      I think it doesn't make any difference at this case, and I used your version to prove my point above.

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

        Finally i got it, the line which cur points to will never get removed as let's say we evaluated the point at some coordinate x[i] . The [y] we get is m1*x[i]+c1.

        Note that for the next line this becomes the y intercept that is c2 = [y] so for the new line the value at x[i] becomes m2 * x[i] + [y] > [y] since m2 is non zero. and since m2 has less slope tham m1 this will intersect to the right of x[i] and hence will never be removed.

        → Reply