AMCS03 - Editorial

pro_test · July 9, 2015, 8:55am

PROBLEM LINK:

Practice

Contest

Author : Surya Kiran

Editorialist: Manas Kumar Verma

DIFFICULTY:

MEDIUM

PREREQUISITES:

Ternary Search or Convex Hull Trick .

PROBLEM:

Given Speed, initial distance of N racers from starting line and ending time of race as K , we need to output minimum value of f(T) \forall T \in [0,K] where f(T) is defined as difference between maximum net distance covered by any racer & minimum net distance covered by any racer at time T .

QUICK EXPLANATION:

Net distance covered by any car can be expressed as linear equation analogous to equation of straight line and problem reduces directly to standard Convex Hull Trick . Also we can observe that f(T) is bitonic function since each of upper and lower convex hull envelopes are bitonic and Upper envelope can’t increase then decrease and lower envelope can’t decrease then increase (formal proof in next paragraph). This means we can use standard Ternary Search here which is faster to code than CHT.

EXPLANATION:

We are given net distance covered by i^{th} racer as P_i(T)=S_i * T + D_i where S_i and D_i denote speed and distance of i_{th} racer which is fixed in beginning while T and P_i are variables. Thus, it is comparable to equation of straight line y = m*x + c . Once you can see the racers as lines , it becomes easier to describe upper and lower convex hull envelope . In given set of lines,informally Upper Convex Hull is a series of line segments which block water first at some x-coordinate if we let water pour from topmost point assuming gravity downwards. Vice versa for lower convex hull envelope . See picture for better clarity.Segment in blue represent upper convex hull envelope while in red represent lower convex hull envelope. Sample Illustration
To prove that f(T) is always bitonic function it is suffice to prove that f(T) is never tritonic . Because to be higher than tritonic function ,by induction that function needs to be tritonic at some range of T . We prove that f(T) is never tritonic by method of contradiction : Suppose on contrary f(T) is tritonic. ie, either function decreases->increases->decrease or increases->decreases->increases. Say f(T) follows former pattern .Decreasing initally means upper envelope a_u and lower envelope say a_l initially are converging (Here a_u , a_l represent locus of points on upper & lower envelope’s initial segment respectively which is decreasing), when function increases after this segment they both (now say b_u , b_l be locus of upper & lower envelope’s segment respectively which is now increasing) diverge but if after this the function decreases (as per tritonic function assumption) the next line segments in chain (say c_u and c_l represent locus of points lying respectively on upper & lower envelope’s segment which by assumption of tritonic function decreasing now) again converge and since c_u , c_l converge it means that their convergance angle is greater than convergence angle between a_u , a_l which implies that function is dependent not on a_u , a_l but instead on c_u , c_l . Thus , f(T) becomes decreasing->increasing ,ie bitonic and not tritonic. Similarily we can prove for increase->decrease->increase case of tritonic function. This completes our claim formally .

ALTERNATIVE SOLUTIONS:

Using convex hull trick was very much direct in this problem and also more inutitive than ternary search solution . Apart from these two O(N log N) solutions one could also come up with O(N^2) solution calculating intersection of every pair of lines and doing a line sweep after sorting them , but clearly this would result in TLE.

IMPLEMENTATIONS IN C++:

Solution using Convex Hull Trick (code by Akul Sareen) here.

Solution using Ternary Search here.