COVID19B - Editorial

Author & Editorialist: Alei Reyes
Tester: Suchan Park

Simple

PREREQUISITES:

Simulation, Brute Forces

PROBLEM:

There are N athletes moving with uniform speed on a line. Initially one of them is infected with a virus, but we don’t know who. The virus spreads from one athlete to another when they are at the same position. Find the minimum and maximum number of infected athletes in the best and worst possible scenarios.

Quick Explanation

Brute force the initial infected athlete and simulate the process as it happens in time.

Explanation

Athlete i will catch j if i \lt j and v_i \gt v_j, they will meet at time t_{i,j} = (j-i)/(v_i-v_j) and at position i + v_i \cdot t_{i,j}.

The idea is to brute force the initial infected athlete and simulate the process increasing order of time. Let’s build a map M[t][x] containing the set of athletes that will meet at time t in position x, it can be obtained by Iterating over each pair of athletes, and calculating their intersection time.

Let’s iterate over M in increasing order of time. If at some moment there is an infected athlete at time t and position x, then the virus will spread over all athletes in M[t][x].

Common Error

My first incorrect solution was as follows: If athlete i is the initially infected, then all faster athletes at their left, and all slower athletes at their right will be infected.

Bonus Problem: Is possible to solve it for constraints e.g N\leq 10^5 ?

Setter's Solution (C++)
int mini=n;
int maxi=0;
map<pair<int,int>,vector<int> >mp;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)if(v[i]>v[j]){
int t=((j-i)*120)/(v[i]-v[j]);
int x=i*120+v[i]*t;
assert(120*i+v[i]*t==120*j+v[j]*t);
mp[make_pair(t,x)].push_back(i);
mp[make_pair(t,x)].push_back(j);
}
}
for(int i=0;i<n;i++){
vector<bool>infected(n);
infected[i]=true;
for(auto p:mp){
for(int x:p.second){
infected[x]=true;
}
}
}
int cnt=0;
for(int x:infected)cnt+=x;
mini=min(mini,cnt);
maxi=max(maxi,cnt);
}
printf("%d %d\n",mini,maxi);

Tester's Solution (Kotlin)
class COVID19B_SOLVER (val br: java.io.BufferedReader, val bw: java.io.BufferedWriter) {
fun check() {
}

fun run() {
require(N in 3..5)

val events = (0 until N).map{ i -> (0 until i).map{ j -> Pair(i, j) }}.flatten()
.filter{ (i, j) -> V[i] != V[j] }
.map{ (i, j) -> Triple(1.0 * (i - j) / (V[j] - V[i]), i, j) }
.filter{ it.first > 0 }
.sortedBy { it.first }

val answers = (0 until N).map { start ->
val infected = BooleanArray(N) { it == start }
for((_, i, j) in events) {
val to = infected[i] || infected[j]
infected[i] = to
infected[j] = to
}

infected.count { it }
}

println("${answers.min()!!}${answers.max()!!}")
}
}


Video Editorial

12 Likes

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=4z8NfQ2CLbs&list=PLz-fHCc6WaNJa2QJq7qULBBV0YOJunq75&index=2

3 Likes

Full detailed explanation in hindi - Link

5 Likes

Thanks for this. Such simple constraints and yet such complexity

7 Likes
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

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() {
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?