Thanks a lot!
1 Like
if 120 is not used, i.e. int t=((j-i) )/(v[i]-v[j]); what if v[i]-v[j] > j-i? since we are using int to store the result, result will be 0 for many cases. That is why 120 since it’s divisible by(1,2,3,4,5). I think we could use 60 as well.
My implementation is here. This problem was just implementation, but people seemed to have struggled.
but how ?? at t= 1 player at 2nd index will infect player at 3rd index ; but how will person at 1st index get infected ??
int t=((j-i)120)/(v[i]-v[j]);
int x=i120+v[i]*t;
why there is multiplication by 120?
2 Likes
Since the speed of any athlete can vary from 0 to 5 . So to get integer value of meeting time we can take lcm of speeds of two players & the speed of two can be any within that range. As a result we can use lcm of 1,2,3,4,5 all velocities , their lcm is 60 , so 120 can also be used because 120 is multiple of 60.
exactly @auto_genos, i was saved by comment on problem page, someone (@ptype035) mentioned the time is continuous.
Some people(including me) might think why 120(5!) is multiplied here. Its just done to prevent t and x have float value. One can use float t,x and remove 120 as well.
Can u give the any test case and its correct ans? it will help
1 Like
I dont know why this code is getting accepted for n=3.
As here i have just count all the faster atheletes at their left and all the slower athelets at their right.
https://www.codechef.com/viewsolution/37520086
4 2 5 3 1 .
In this example for runner no. 3 with velocity 5 He will infect 3,1. But 3 will in turn infect 4(as 4 will cross 3 after a certain time and get infected ). And 1 will in turn infect 2. So total infected for 5 will be 5(3,1,4,2,5).
Really now I Understood what was the mistake I was doing the whole time.
Can anybody help me why on
INPUT:
1
5
4 3 5 1 2
it gives
OUTPUT:
4 5
Athlete 3(with velocity 5) will never meet any other athlete so it should show 4 4.
Brother. cay you please explain this with your approach.
I have used dictionary with sets in Python. 30 lines of code.
`t = int(input())
for _ in range(t):
n = int(input())
vels = [int(i) for i in input().split()]
timeCount = {}
for i in range(n):
for j in range(i+1, n):
if vels[i]>vels[j]:
equalTime = (j-i)/(vels[i]-vels[j])
equalDist = i + vels[i]*equalTime
try:
timeCount[(equalTime, equalDist)].update([i, j])
except:
timeCount[(equalTime, equalDist)] = set([i, j])
minVal = None
maxVal = None
timeKeys = sorted(timeCount.keys())
for i in range(n):
infected = set([i])
for j in timeKeys:
if len(infected.intersection(timeCount[j]))!=0:
infected.update(timeCount[j])
if minVal==None or len(infected)< minVal:
minVal = len(infected)
if maxVal==None or len(infected)> maxVal:
maxVal = len(infected)
print(minVal, maxVal)`i don’t think 2 will reach 3 here
u sure about it?
@alei why did we multiply (j - i) and i by 120 ?
I couldnt find the reasoning behind that please explain .
Thank You
Well this question tested mostly the reading skills … if you have read that line " same time same distance " correctly then this question had nothing special to be done… although I would surely agree with what you said it can get the best one down for a while !
could you share the code for that bubble sort approach?