SPEEDTEST - EditorialED

PROBLEM LINK:

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

Author: S. Manuj Nanthan
Preparer: Mradul Bhatnagar
Testers: Satyam, Jatin Garg
Editorialist: Nishank Suresh

DIFFICULTY:

718

PREREQUISITES:

None

PROBLEM:

Alice’s office is A kilometers and she takes X hours to reach it.
Bob’s office is B kilometers and he takes Y hours to reach it.

Who is driving faster?

EXPLANATION:

Alice’s speed is \frac{A}{X} and Bob’s speed is \frac{B}{Y}. Comparing these two numbers with an if condition is enough to solve the problem.

I did this, why am I still getting WA?

Note that all four values given in the input are integers, but the speeds need not be. So, directly comparing the values as

if (a/x < b/y) {...}

will not work in languages such as C++ and Java, where / denotes integer division when it operates on integers.

You can test your code on

1
3 3 3 2

and see if your output matches what you expect to see.

To resolve this, there are a couple of options:

  • Convert all four values to doubles and do the comparison there, which is still unsafe but will work in this problem since the values of A, B, X, Y are small.
  • The better option is to not use division at all. Note that \frac{A}{X} \lt \frac{B}{Y} if and only if A\cdot Y \lt B\cdot X, so you can instead compare the values of A\cdot Y and B\cdot X instead, which works purely with integers and is completely safe.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (C++)
#include <iostream>
using namespace std;

int main() {
    int t; cin >> t;
    while (t--) {
        int a, x, b, y; cin >> a >> x >> b >> y;
        if (a*y == b*x) cout << "Equal\n";
        else if (a*y < b*x) cout << "Bob\n";
        else cout << "Alice\n";
    }
}
Editorialist's code (Python)
for _ in range(int(input())):
    a, b, x, y = map(int, input().split())
    print('alice' if a*y > b*x else ('bob' if a*y < b*x else 'equal'))