Mintoo's blog

Gradient And Hessian In Codechef CPOINT
By Mintoo, 9 years ago, In English

Can somebody explain this solution http://www.codechef.com/viewsolution/2949645 for this problem http://www.codechef.com/problems/CPOINT/.

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

»
9 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

Newton's method in optimization http://en.wikipedia.org/wiki/Newton's_method_in_optimization http://en.wikipedia.org/wiki/Newton's_method_in_optimization

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

The same problem was in ch24 qualifying round some years ago. There is another nice way to solve it using hill climbing optimization. You can start from the point (Xs = avg{Xi}, Ys = avg{Yi}) and then try to move in each of the 8 directions by some distance d = 1010 and see which point has the best result out of eight and then you repeat the move but with a smaller distnace d = d / 10. Once d reaches some convergence threshold, 1e - 9 for example, you can output the solution.

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

I will give it a shot using 2D ternary search, though it is often hard to prove correctness in similar solutions... It is nice to see gradient and hessian applied in some algos :).

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

    Yes, many have solved it using 2D ternary search. But ternary search took a lot of time compared to the gradient and hessian.

    → Reply