PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Video Editorial
Author & Editorialist: Alei Reyes
Tester: Suchan Park
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()!!}")
}
}
