EXMLF1 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: am_aadvik
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N cars, the i-th of which drove a distance of d_i in t_i seconds.
The cars all move with a constant speed.
Find the number of the fastest car - if there are multiple, report the one with smallest index.

EXPLANATION:

Since each car travels at a constant speed, the speed of the i-th car equals the distance it traveled divided by the time it traveled.

That is, the speed of the i-th car, which we’ll denote s_i, equals \frac{d_i}{t_i}.

The task is now to find the largest among these speeds (and if there are multiple cars with the largest, the one with smallest index).
That can be done using a simple loop, as follows:

  • Initialize \text{ans} = 1 to be the answer.
  • Then, for each i = 2, 3, 4, \ldots, N in order:
    • If s_i \gt s_{\text{ans}} then the new highest speed is s_i.
      So, set \text{ans} = i here.
    • If s_i \le s_{\text{ans}} then highest speed remains s_{\text{ans}}.
      In this case we don’t change \text{ans}; since even if s_i = s_{\text{ans}}, we want to report the lower-indexed car (and \text{ans} \lt i since we’re iterating left to right).

In the end, just print \text{ans}.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    speeds = []
    for i in range(n):
        d, t = map(int, input().split())
        speeds.append(d // t)
    
    ans = 0
    for i in range(1, n):
        if speeds[i] > speeds[ans]:
            ans = i
    print(ans + 1)