eddycael's blog

Help with problem UVa 12945 — Farmer Jane
By eddycael, history, 9 years ago, In English

Hi... I am trying to solve this problem

I learned about Ternary Search and my code works for the test cases in the sample. Can anyone tell me some hint? this is my code Thanks in advance and sorry for my poor english

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

»
9 years ago, # |
← Rev. 4   Vote: I like it +2 Vote: I do not like it

You can use the partial derivate to find the minimum(relative)/maximum(relative) of a function , In this case the function is:

If you draw a graphic for this problem, you can see that in this case the function only has a minimum and this point is an absolute minimum. Something like this:

Then: For find X such that f(X, Y) is minimum(absolute minimum in this problem)

  1. Derivate f(X, Y) respect of X (consider Y as a constant)
  2. Make the result equal to zero
  3. Find X in the new equation and replace all x[i], w[i]. (You should have the value of X)

The same steps for Y, finally evaluate (X, Y) in f(X, Y) and obtain the final answer.

The final complexity is O(n). Good luck.

PD.: Sorry for my poor english.

→ Reply