You are not logged in. Please login at www.codechef.com to post your questions!

×

CYCLRACE - Editorial

1
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

This question is marked "community wiki".

asked 11 Jan '16, 09:49

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 11 Jan '16, 15:14

admin's gravatar image

0★admin ♦♦
19.7k350498541


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)

link

answered 11 Jan '16, 15:14

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

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

(11 Jan '16, 18:32) rushilpaul4★

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 ?

link

answered 17 Jan '16, 13:46

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

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

link

answered 11 Jan '16, 15:43

animan123's gravatar image

3★animan123
1112
accept rate: 0%

@dpraveen The solution links are broken. Please fix!

link

answered 11 Jan '16, 21:31

bholagabbar's gravatar image

4★bholagabbar
6115
accept rate: 0%

Update the solutions links please, they are broken !

link

answered 16 Jan '16, 18:37

rishab951's gravatar image

4★rishab951
2
accept rate: 0%

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

link

answered 19 Jan '16, 17:58

cacyth's gravatar image

4★cacyth
1
accept rate: 0%

Why does it say 'Access denied' when trying to access author's/tester's/editorialist's solutions?

link

answered 13 Feb '16, 14:56

epiq's gravatar image

4★epiq
11
accept rate: 0%

I don't understand why I'am getting WA here

link

answered 03 Jul '18, 22:02

colonel_bishop's gravatar image

3★colonel_bishop
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,477
×151
×106
×4
×4

question asked: 11 Jan '16, 09:49

question was seen: 4,700 times

last updated: 03 Jul '18, 22:02