Mockvita 1 2020 Problem C - Collision Course

1

Mockvita Problem 3
Mockvita Problem 31065×1306 60 KB

I’m posting this as Mockvita 1 is over. I tried to solve this problem:

import math

def nCr(n, r):

    if r > n-r:

        r = n-r

    ans = 1

    for i in range(1, r+1):

        ans *= n-r+i

        ans //= i

    return ans

c = int(input())

all_car_times = {}

for _ in range(c):

    x, y, velocity = [int(x) for x in input().split()]

    dist = math.sqrt(x*x + y*y)

    time = dist / velocity

    if time in all_car_times:

        all_car_times[time] += 1

    else:

        all_car_times[time] = 1

total_collisions = 0

for val in all_car_times.values():

    if val >= 2:

        total_collisions += nCr(val, 2)

print(total_collisions)

But it’s passed public test cases only and failed in private test cases. Can anyone please figure out my fault?

1 Like
2

Floating points are not accurate, using them as key is not a good idea. I pretty much did the same, but i had used the “fractions” module. Or you could try keeping fraction as a tuple of numerator and denominator ( reduce fraction such that these two are mutually co-prime).

2 Likes
3

YEah , this might be a problem because i did same with double for only ending with wrong answer so i think your idea is great.

4

Thanks bro. I got your point.