CCC '20 S1 - Surmising a Sprinter's Speed - DMOJ: Modern Online Judge

CCC '20 S1 - Surmising a Sprinter's Speed

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

Canadian Computing Competition: 2020 Stage 1, Senior #1

Trick E. Dingo is trying, as usual, to catch his nemesis the Street Sprinter. His past attempts using magnets, traps and explosives have failed miserably, so he's catching his breath to gather observational data and learn more about how fast Street Sprinter is.

Trick E. Dingo and Street Sprinter both inhabit a single straight west-east road with a particularly famous rock on it known affectionately as The Origin. Positions on this straight road are measured numerically according to the distance from The Origin, using negative numbers for positions west of The Origin and positive numbers for positions east of The Origin.

The observations by Trick E. Dingo each contain two numbers: a time, and the value of Street Sprinter's position on the road at that time. Given this information, what speed must Street Sprinter be capable of?

Input Specification

The first line contains a number $2 \le N \le 100\,000$ ~2 \le N \le 100\,000~, the number of observations that follow. The next $N$ ~N~ lines each contain an integer $0 \le T \le 1\,000\,000\,000$ ~0 \le T \le 1\,000\,000\,000~ indicating the time, in seconds, of when a measurement was made, and an integer $-1\,000\,000\,000 \le X \le 1\,000\,000\,000$ indicating the position, in metres, of the Street Sprinter at that time. No two lines will have the same value of $T$ ~T~.

For $7$ ~7~ of the $15$ ~15~ available marks, $N \le 1\,000$ ~N \le 1\,000~.

Output Specification

Output a single number $X$ ~X~, such that we can conclude that Street Sprinter's speed was at least $X$ ~X~ metres/second at some point in time, and such that $X$ ~X~ is as large as possible. If the correct answer is $C$ ~C~, the grader will view $X$ ~X~ as correct if $\frac{|X-C|}{\max(1, C)} \le 10^{-5}$ ~\frac{|X-C|}{\max(1, C)} \le 10^{-5}~.

Sample Input 1

Output for Sample Input 1

7.0

Explanation of Output for Sample Input 1

Since the Street Sprinter ran from position $100$ ~100~ to position $120$ ~120~ between time $0$ ~0~ and time $10$ ~10~, we know its speed must have been at least $2$ ~2~ at some point in time: if it was always less than $2$ ~2~, then the distance of $20$ ~20~ could not be covered in $10$ ~10~ seconds. Likewise, the speed must have been at least $7$ ~7~ in order to travel between position $120$ ~120~ and $50$ ~50~ in $10$ ~10~ seconds.

Sample Input 2

Output for Sample Input 2

6.8

Comments

5

maxcruickshanks commented on July 17, 2021, 12:28 a.m.

The checker has been updated to heed the constraints described in the problem.

4
qiao_yun20060930 commented on May 2, 2021, 6:01 p.m. ← edited →
cout << fixed << setprecision() << NAME

-22
wleung_bvg commented on April 20, 2020, 8:04 p.m. ← edit 2 →
Edit: The checker has now been updated to check for bother absolute and relative.

Note that DMOJ is checking for an absolute error of $10^{-5}$ ~10^{-5}~ rather than relative error. This is probably for the better as cases such as the following would require you to print around $14$ ~14~ digits after the decimal just to get within a relative error of less than $10^{-5}$ ~10^{-5}~.

Input

2 0 0 900000000 3

Correct Output

0.00000000333333

Incorrect Output

0.000000003
This comment is hidden due to too much negative feedback. Show it anyway.

0

orangewave commented on April 3, 2020, 2:46 p.m. ← edited →

I can't get batch #3 to pass. I'm using python3. Here is my code: https://pastebin.com/iEztHv4J

Any suggestions?

6

sushi commented on April 3, 2020, 8:39 p.m.

I suggest you reread the problem, is it possible to be at time 20 before time 10?

0

mathgeek008 commented on April 3, 2020, 5:07 p.m.

Using a temporary list and iterating through it (nested for loop) effectively squares the number of operations the program does before printing. Try implementing an algorithm that avoids doing this.

1

RyanLi commented on April 3, 2020, 5:06 p.m. ← edited →

Your solution is O(N^2). The intended solution is O(N log N). Try thinking of a faster way to calculate the speeds.

Edit: Forgot sorting existed

12

magicalsoup commented on April 21, 2020, 12:22 a.m.

The intended solution is not necessarily $O(n)$ ~O(n)~. I think $O(n \log n)$ ~O(n \log n)~ would be more correct.

3

Evanhyd commented on April 1, 2020, 11:39 p.m.

There are no restrictions on the number of decimal points; More precise is better

8

TimothyW553 commented on April 2, 2020, 3:13 a.m. ← edited →

I only printed to 1 decimal place during CCC 🐒

6

Plasmatic commented on April 3, 2020, 4:22 a.m.

orz timothy cco chad passing s1 with only 1 decimal place

-8

RyanLi commented on March 26, 2020, 12:03 a.m.

Just a heads up printf should be used instead of cout, as cout rounds the output and can also print in scientific notation

This comment is hidden due to too much negative feedback. Show it anyway.

14
Tzak commented on March 26, 2020, 12:18 a.m. ← edited →
If you want to print a floating-point value x in decimal format with n digits after the decimal point with std::cout, use the following:

std::cout << std::fixed << std::setprecision(n) << x;

5

ross_cleary commented on March 25, 2020, 9:53 p.m.

Use doubles not floats.