# PROBLEM LINK:

Practice

Div-2 Contest

Div-1 Contest

Video Editorial

* Author & Editorialist:* Alei Reyes

*Suchan Park*

**Tester:**# DIFFICULTY:

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){
bool spread=false;
for(int x:p.second)spread|=infected[x];
if(spread){
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() {
val N = br.readLine()!!.toInt()
require(N in 3..5)
val V = br.readLine()!!.split(' ').map(String::toInt)
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()!!}")
}
}
```