PROBLEM LINK:Author: Maksym Bevza DIFFICULTY:Medium PREREQUISITES:dynamic convex hull of lines PROBLEM:There are $n$ persons taking part in a race. They all start at position x = 0 with initial velocity zero. You are $Q$ queries to support, each of which could be one of the following: 1. Change the speed of $i$th person to $v_i$ at some $T$. 2. Ask the position of the leader at some time $t$.
EXPLANATION:If position of a person is $x$ and speed is $v$, then at time $t$, his position will be $x + v * t$. Now, assume that we change its speed at time $T$ from $v$ to $v'$. Now position of the person at time $t > T$, will be $x + v * T + v' * (t  T) = (x + (v  v') * T) + v' * t$ i.e. $x' + v' t$ where $x' = (x + (v  v') * T)$. So, the information that we need to store for a cyclist is values $(x, v)$ for it, such that $x + v * t$ will give its position at a time $t$. Using the above equations, we also know how to update this information for the update query (i.e. query of type 2) : Change $x$ to $x'$ and v to $v'$. Now, we know the information $(x_i, v_i)$ for each person, we want to know the position of leader at time $t$. The trivial $O(n)$ solution will be to iterate over all the racers and find the maximum of $(x_i + v_i * t)$. This solution is enough to solve the first subtask. We want to find something better. Online solution Let us plot all these lines for each person in 2D plane. We can note that the curve corresponding to position of leader at various times will be lower convex hull of all these lines. We can maintain this lower hull by maintaining the order of lines appearing in the hull w.r.t. increasing $t$ coordinate. Dealing with query #1 Dealing with query #2 We are given in the problem statement that speed of a racer will never decrease. So, we don't need to delete the older line for an update, because it is not going to provide us position of winner of race anyways. Hence we only need to support addition of line operation in a convex hull. We can add a line in a lower convex hull using binary search too. This operation is very well explained in the following article. OPTIMAL COMPLEXITY:$O((n + Q) log n)$ SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 11 Jan '16, 09:49

Here's how I solved it. I used segment tree + binary search. For each cyclist , you need to store 3 value (time , distance , speed) denoting the cyclist has travelled distance 'distance' at time 'time' and is moving at speed 'speed'. Process all queries first. Build a segment tree for all queries where a node stores the leader at time [q[l] , q[r]] , q[i] being query time of ith node. If an update query comes , using binary search find the time at which it overtakes the leader at that point. Then using segment tree , update the leader for all further time. To set a range [l , r] to value v , you can use the idea from this. For the second query [indexed i] , using segment tree find the value of the node denoting range[i , i] and determine its position. Complexity : O(N * logN * logN) answered 11 Jan '16, 15:14

Used Convex Hull Trick Link to my Solution : https://www.codechef.com/viewsolution/9159452 Wondering if it could be solved without using CHT or segment trees, but by some logic. Since "The speed of cyclist never decreases". Maintaining three leaders at each point didnt worked for me :/ Here's the solution link : https://www.codechef.com/viewsolution/9092793 Wondering if anybody has done that way ? answered 17 Jan '16, 13:46

My favorite problem from the contest! Here is my approach After this for updating a cyclist speed, I used the concept of events. Whenever a cyclist C1 speed is updated, you go up the tree to the node where C1 is losing(if you reach root, it means he is already the winner, so you only have to update his values). Suppose he loses at node p to cyclist C5. Now we calculate if with his new speed C1 can overtake C5 and if yes then at what time. Suppose we find out that C1 can overtake C5 at time t1, we schedule at event at time t1 where C1 challenges C5. These events are stored in a priority queue ordered by time. When this event occurs at time t1, C1 may replace C5. In this case, we check if he can challenge his new parent now and so on(atmost logn challenges) Whenever we have to do a query at time ti, we first flush the event queue till time ti (perform all events that occur till time ti). If it is a query of type 1, schedule a new event. If it is a query of type 2, just return the distance of cyclist at root. Complexity : O(q*logn) because for any query we just have to climb up tournament tree(n levels) answered 11 Jan '16, 15:43

Update the solutions links please, they are broken ! answered 16 Jan '16, 18:37

I found some AC codes cannot pass this example: 3 10 1 0 1 2 2 100 1 1 2 2 2 100 1 50 3 2 2 100 1 50 3 8 2 100 1 52 2 6 2 100 (The answer is 400,but some codes' output is 390 @ironmandhruv)@Maksym Bevza answered 19 Jan '16, 17:58

Why does it say 'Access denied' when trying to access author's/tester's/editorialist's solutions? answered 13 Feb '16, 14:56
