COVID19B - Editorial

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. :slight_smile:

16 Likes

took forever to implement

1 Like

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

Can anyone tell me what was wrong in my approach https://www.codechef.com/viewsolution/37902613

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 : - https://www.codechef.com/viewsolution/37868445

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->https://www.codechef.com/viewsolution/37558233
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