Discussion @ 1535. The Hobbit or There and Back Again @ Timus Online Judge

Online Judge	Problems	Authors	Online contests
About Online Judge Frequently asked questions Site news Webboard Links	Problem set Submit solution Judge status Guide	Register Update your info Authors ranklist	Current contest Scheduled contests Past contests Rules

Discussion of Problem 1535. The Hobbit or There and Back Again

1535 Proof?

Posted by svr 4 Mar 2007 20:17

Simple algorithm but hard proof?
How to prove that some construction in this problem
is optimal?

Re: 1535 Proof?

Posted by Victor Barinov (TNU) 4 Mar 2007 22:55

For minimal permutation must be:
(p[i] - p[i+1]) * (p[i-1] - p[i+2]) < 0