CYCLRACE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Maksym Bevza
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Praveen Dhinwa

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.
  • Time values are distinct and are sorted in increasing order w.r.t queries.
  • Speed of a cyclist can not decrease.

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 position of a person vs time (t). We know that position of a person at time will be given by equation x + v * t, which is a straight line passing throught (0, x) and has positive slope of v.

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

  • Find position of winner at time t.
    i.e. find out value of lower convex hull at time t.
    We can use binary search to find the line which is the part of lower convex hull for a particular time.
    After knowing the line, we can find the position of winner at that time t easily.

Dealing with query #2

  • Change the speed of i-th racer from v to vā€™ at time T.
    As discussed above, the old line corresponding to racer (x_i, v_i) has to be replaced with new line (x_i', v_i').

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:

Author
Tester
Editorialist

1 Like
2

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.

Solution

Complexity : O(N * logN * logN)

6 Likes
3

My favorite problem from the contest! Here is my approach

I used a tree(something like a segment tree) to keep track of the winner at a static time t0. All cyclist are present at leaf nodes. Consider two adjacent cyclists C1 and C2. If C1 is ahead at time t0, then the parent will contain C1, otherwise C2.

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)

https://www.codechef.com/viewsolution/9103916

1 Like
4

Brilliant observation! By the way, complexity would include Q too

5

@dpraveen The solution links are broken. Please fix!

6

Update the solutions links please, they are broken !

7

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 :confused:

Hereā€™s the solution link : https://www.codechef.com/viewsolution/9092793

Wondering if anybody has done that way ?

3 Likes
8

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

9

Why does it say ā€˜Access deniedā€™ when trying to access authorā€™s/testerā€™s/editorialistā€™s solutions?

10

I donā€™t understand why Iā€™am getting WA
here