1 Like
This was one of those problems where even though you understand the problem crystal clear, was very challenging to implement atleast for me. 
16 Likes
I have solved using DFS & i think that may be best solution if n<=10^5 would be given .
I thought that virus can only spread if 2 players are at same integer location at the same time.
It was easy but I couldn’t solve it because of such small misunderstanding. It taught me something useful. Nice question.
2 Likes
There is the simplest solution, which requires no simulation, even it doesn’t require to check that after how much time one athlete will cross another one.
You have to simply reverse the given array and sort it in decreasing order. you have to use bubble sort
Let’s take an example the speed array is 3 1 4 2.
reverse -->2 4 1 3
now let’s say 2 is infected and denote it with “.” i.e.
2. 4 1 3
now we sort step by step like this
4. 2. 1 3 // first swap will infect the athlete having speed 4
4. 2. 3 1 // second swap will infect none
4. 3. 2. 1 // third swap will infect athlete having speed 3
so we have 3 athletes get infected and the array is sorted.
reverse -->2 4 1 3
so now let’s say 1 is infected
2 4 1. 3
4 2 1. 3 // no one gets infected
4 2 3. 1. // athlete having speed 3 gets infected
4 3. 2. 1. // athlete having speed 2 gets infected
so in this way, we have to check for all n athletes one by one and take the minimum infected and maximum infected case.
11 Likes
4
4
3 1 4 2
4
4 3 1 2
4
3 4 1 2
4
4 3 1 2
check for these cases manually too
use this simplest solution that requires only one bubble sort algorithm
can you explain the DFS approach? I tried but had to increase code to implement so decided to go for brute force.
I am getting this output
4
4
3 1 4 2
2 3
4
4 3 1 2
3 4
4
3 4 1 2
3 3
4
4 3 1 2
3 4
It’s similar to the approach in editorial. Instead of creating a map, create an adjacency list of athletes who will meet in their run. Also calculate their meet times. Then run a simple DFS considering how many will get affected. This can be done in O(N) or O(N ^ 2) depending on the implementation.
1 Like
CAN anyone help me find why my code did’t clear the subtask 2 ??
here is link to my submission : - CodeChef: Practical coding for everyone
my code -
#include <iostream>
using namespace std;
int main() {
// your code goes here
int T;
cin>>T;
for (int k =0; k<T; k++){
int max = 0;
int min = 6;
int N;
cin>>N;
int arr[N] ;
for (int a=0; a<N; a++){
cin>>arr[a];
}
for (int j =0; j<N; j++){
int count = 1;
for (int i =0; i<N; i++){
int nom = (j - i) ;
int dom = (arr[i] - arr[j] ) ;
if ( (nom>0 && dom>0 ) || (nom<0 && dom<0 ) ){
count++ ;
}
} // inner loop
if (count >max){
max = count;
}
if ( count < min ){
min = count ;
}
} // outer loop
cout<<min<<" "<<max<<endl;
} // testcases
return 0;
}
1 Like
nice method
I don’t think we need to reverse the array .we can keep the array as-is and use bubble sort to sort it in ascending order. well, it is just what you said but I just felt this is more intuitive because after every pass of the array it gives you the order in which athletes are after one second of time. example if the speed array is 3 1 4 2 then after one second the order is 1 3 2 4 which you can get by doing one pass of bubble sort(in the actual algorithm we do it n times right)so in a way your method is like playing the simulation but it is giving a new insight to it
in your method, you are saying that ith person got infected and he is spreading it to jth person but it is possible that this new person can also infect others right example if the speed array is 2 3 1 and 3 is infected then after some time all three people will get infected but according to your code it is just 1
why this doesn’t work?
true bro
Exactly buddy
here is the sol. link->CodeChef: Practical coding for everyone
bascially here 1 to node n are 1 to n numbered athletes & in the adjacency matrix i have stored the time when i’th & j’th player will meet…
Then calling DFS using i’th palyer as root node(1<=i<=n) & i’th palyer can only infect j th player if their time meeting is +ve & greater than equal to the time when i’th palyer was infected & only that j’th player is responsible for speading infection to others also…
2 Likes
i did dfs too.So first task is to form a graph where weighted edges represent time at which the nodes contact,so we start from each and infect all that are in direct contact with initial node and for all other nodes check if time of contact for the next edge is more if its more we explore that node else we continue to other nodes.
I think a visual explanation would be easier to uderstand
1 Like