Need help with "Coronavirus Spread 2" (Prblem Code:COVID19B)

Problem link: https://www.codechef.com/SEPT20B/problems/COVID19B/

I am not able to figure it out where my code is giving WA.
if anyone can point out mistake in my code or atleast give some test cases where my code fails…it would be a great help.

Approach: I have stored all my velocities in a vector v and then for each velocity i am calling function “findcount” which gives me count of infected people. it counts the people with velocity greater than the infected person to its left and persons with velocity less than infected people to its right while taking care of time of infection.

my code: https://www.codechef.com/viewsolution/37621867

Try
1
4
4 1 3 2
Your code gives 3 3 whereas the correct ans is 3 4.

Well I can’t really get what you have done but I can suggest what was my approach

Suppose there is a runner A at pos i having speed v1 and there is a another runner B at pos j having speed V2 .

Now it is only possible to infect runner B by runner A if

i + v1* t = j + V2 *t
So on rearranging this you can see that sign for i-j and V2-v1 should be same and V2!=v1 .

Now once we find any one infected we can take this infected one and again see from the starting and see how many he can infect but here we should consider the time it takes
Which can be done by T= (i-j)/v2-v1 .
So suppose person A infected B in X seconds and now we consider person B as infected and we go through all the non effected person and we first see if he can infect them or not and if he can do that then we check what time it takes …if it is > then the time it took for himself to be infected then he can infect that runner
You can manage a Boolean array for those who are infected and keep a count of how many will get infected by the person and finally return minimum and maximum value

You can refer this for the same
https://www.codechef.com/viewsolution/37873629

1 Like

you forgot 2 cases.
the fastest person to your left can infect anyone slower than him.
the slowest person to your right can infect anyone faster than him.
take these into account and you are done.

2 Likes