icpc_expert's blog

Manhattan Centre CS academy
By icpc_expert, history, 6 years ago, In English

I am trying to solve manhattan centre from cs academy. I am thinking to apply binary search on answer for x between 1 and 100000000. According to me the graph of the function will be a parabola.So what I am doing is I am calculating three values one at mid,mid+1 and mid-1 and checking if I am on the left side of the parabola low=mid+1 else if I am on the right side of the parabola high=mid-1. Else if I find the min point then it is the answer.But the solution is not working in the way that I wanted it to be can anyone tell me where I am going wrong.Also I saw some of the submissions where people applied ternary search and got the correct answer. As far as I know all the problems solved with ternary search can also be solved with binary search also.Here is the link to my solution. SOLUTION. Sorry for my poor english.

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

Comments Comments (2)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We can not solve this problem with ternary search or binary search. There are people who answered correctly with ternary search because they were lucky. You can solve with ternary search or binary search only when the function is convex function. However, as you can see by experimenting with test number 7, the function of x in this problem is not a convex function. In other words, the test case was weak. (It happens occasionally in csacademy) If you want to solve the problem solved by ternary search using binary search, you can do binary search with "difference". I post my code below, but I was lucky (!) I got the right answer for this problem, except for one case. https://ideone.com/VzVfBl

→ Reply