PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author & Editorialist: Alei Reyes
Tester: Danya Smelskiy
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Basic programming
PROBLEM:
There are N people standing on a line, exactly one of them (we don’t know who) is infected with a virus. The virus spreads from one person to another if their distance is at most 2. If the infected person is chosen optimally, find the minimum (best possible scenario) and maximum (worst possible scenario) number of infecteds.
QUICK EXPLANATION:
Let’s say an integer i is a breakpoint if the distance between person i and i+1 is greater than 2. The breakpoints divide the line in many segments, we have to find the longest and shortest segment.
EXPLANATION:
We don’t know who is the initially infected person, so we can simulate for each person how the virus will spread and calculate the number of infecteds.
The key observation is that the virus stops spreading in one direction when two adjacent people are at a distance greater than 2.
Let’s suppose person i is the initially infected. The virus will spread to the right of person i and stops if two adjacent people are at a distance greater than 2. Formally, the virus will spread until the minimum r (r \geq i), such that x_{r+1}-x_r > 2. For simplicity we can consider that x_{N+1}=\infty .
The following pseudocode describes how to find such r:
findRight(i):
r = i
while r<n and x[r+1]-x[r]<=2:
r = r + 1
Similarly, the virus will spread to the left of person i and stops if two adjacent people are at a distance greater than 2. Formally, the virus will spread until the maximum l (l \leq i), such that x_l-x_{l-1}>2. For simplicity we can consider that x_0=-\infty
The following pseudocode describes how to find such l:
findLeft(i):
l = i
while l>1 and x[l]-x[l-1]<=2:
l = l - 1
Therefore the virus will infect r-l+1 people (everyone with indices l through r).
For each i the maximum number of infecteds is at most N. The initially infected person i can be any of the N people, therefore the brute force will make at most N^2 operations. With such algorithm we can solve the problem in less than a second for a N near 10^4.
However we don’t have to try for all N. Let’s suppose that the initially infected person is i, then the virus will spread from L = findLeft(i) to R = findRight(i). Note that if the initial infected person is any j between L and R (L \leq j \leq R), then the virus will also spread from L to R. This leads to the following linear time algorithm.
l = 1
bestCase = N
worstCase = 1
while l <= N:
r = findRight(l)
len = r - l + 1
bestCase = min(bestCase, len)
worstCase = max(worstCase, len)
l = r + 1
Since the constraints are very low, even very unoptimized solutions should get accepted, for example the following pseudocode simulates the spread of the virus:
for T = 1 . .. N: #Why only N iterations?
for i = 1 . . . N-1:
if x[i+1] - x[i] <= 2:
if infected[i]: infected[i+1] = True
if infected[i+1]: infected[i] = True
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
int main(){
int t=rint('\n');
assert(1<=t&&t<=2000);
while(t--){
int n=rint('\n');
vector<int>x(n);
for(int i=0;i<n;i++){
x[i]=rint(i==n-1?'\n':' ');
assert(0<=x[i] && x[i]<=10);
if(i-1>=0)assert(x[i]>x[i-1]);
}
int mini=1e9;
int maxi=-1e9;
for(int i=0;i<n;){
i++;
int cnt=1;
while(i<n && x[i]-x[i-1]<=2)cnt++,i++;
mini=min(mini,cnt);
maxi=max(maxi,cnt);
}
printf("%d %d\n",mini,maxi);
}
assert(getchar()==EOF);
return 0;
}
Tester's Solution
#include <iostream>
#include <vector>
using namespace std;
void solve(int test_id) {
int n;
vector<int> v;
cin >> n;
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
v.push_back(x);
}
int mn = n;
int mx = 0;
int l = 0;
for (int i = 0; i < (int)v.size(); ++i) {
if (i && v[i] - v[i - 1] > 2) l = i;
if (i + 1 == v.size() || v[i + 1] - v[i] > 2) {
int cur = i - l + 1;
if (cur < mn)
mn = cur;
if (cur > mx)
mx = cur;
}
}
cout << mn << " " << mx << '\n';
return;
}
int main(int argc, const char * argv[]) {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tests;
cin >> tests;
for (int i = 1; i <= tests; ++i) {
solve(i);
}
return 0;
}
