URAL 1130 - Nikifor's Walk

好像是很經典的題, 題解十分巧妙
做法在這裏

回溯答案我用了tree去記錄, 如果merge i+j, 則由i到j連一條weight 0的edge; 如果merge i-j, 則連weight 1的邊, 最後從source做一次dfs
其實那些properties對我來說並不明顯, 所以還是在這裏做個記錄吧


Claim 1. For any two vectors u,v where |u|,|v| <= L, either |u+v| <= sqrt(2)*L or |u-v| <= sqrt(2)*L

Proof.
|u+v|² = |u|²+|v|²-2|u||v|cos(θ)
|u-v|² = |u|²+|v|²+2|u||v|cos(θ)
In either case, the square of magnitude will not greater than |u|²+|v|² = 2*L²


Claim 2. For any three vectors length not greater than L, it is always possible to choose 2 of them such that the length resultant vector performing addition OR subtraction is not greater than L.


Proof.
I seen a proof on other's blog using the formula above, using the fact that there must exists a θ >= 120 degree.

Let three vectors be v,w,u.



Let the brown vector = v.
If v+w or v+u falls in yellow, then the length of v+w or v+u <= L
Else if v+w or v+u falls in red, then the length of v-w or v-u <= L
Else, v+w and v+u falls in blue or green, then the length of w+u or w-u <= L