COVID19 - Editorial

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;
}

CAn anyone figure out what is wrong in my solution?
https://www.codechef.com/viewsolution/32634093

You are only searching right , not in left direction :slight_smile:

4 Likes

You made lot of mistakes in your logic … check your code for this .

1
6
0 1 2 5 6 9

I followed the most naive approach by converting the number to string and taking # whenever there is a distance of 3 or more… for N=8 there will be maximum 4 groups possible.

#include<bits/stdc++.h>
#include
#define pb(x) push_back(x)
#define vi vector
#define ll long long
#define mp make_pair
#define vvi vector<vector>
#define st stack
#define ln “\n”
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
#define bg(x) x.begin()
#define ed(x) x.end()
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i–)
#define atob(i,a,b) for(int i=a;i<=b;i++)
#define btoa (i,a,b) for(int i=b;i>=a;i–)

using namespace std;

int main()
{
ios_base::sync_with_stdio(!cin.tie(0));

        int t;
        cin>>t;
         while(t--)
      {
          string s="#";
         int n;cin>>n;int ar[n]; rep(i,n)cin>>ar[i];
         
          int maxc=1,count=1;    
          rep(i,n-1)
          {
              if(ar[i+1]-ar[i]<3)
              {
                  count++;
                  maxc= max(count,maxc);
              }
                if(ar[i+1]-ar[i]>2)
                count=1;
           } 
         
              rep(i,n-1)  if(ar[i+1]-ar[i]<3)s+=to_string(ar[i])+"*"; else s+=to_string(ar[i])+"#";
              if(ar[n-1]==10)s+="A#"; else s+=to_string(ar[n-1])+'#';
        

               int min1,min2,min3,min4;
               int c=0;
               size_t l1 = s.find('#'); size_t l2=s.find('#',l1+1);
               atob(i,l1,l2)
               {
                   if(s.at(i)<='9'&&s.at(i)>='0'||s.at(i)=='A') c++;
               }
                size_t l3=s.find('#',l2+1); 
                int c1=0,c2=0,c3=0;
           
               if(l3==string::npos ) {cout<<c<<" "<<maxc<<ln;continue;} //cout<<s<<" "<<"min="<<c<<" "<<" max= "<<maxc<<ln;continue;}
               atob(i,l2,l3)
               {
                   if(s.at(i)<='9'&&s.at(i)>='0'||s.at(i)=='A') c1++;
               
               }
                size_t l4=s.find('#',l3+1); if(l4==string::npos)  {cout<<min(c,c1)<<" "<<maxc<<ln;continue;}//cout<<s<<" "<<"min="<<min(c,c1)<<" "<<" max= "<<maxc<<ln;continue;}
                if(l4!=string::npos ) 
                atob(i,l3,l4)
               {
                   if(s.at(i)<='9'&&s.at(i)>='0'||s.at(i)=='A') c2++;
               
                  }
                size_t l5=s.find('#',l4+1); if(l5==string::npos) {cout<<min(c,min(c1,c2))<<" "<<maxc<<ln;continue;}//cout<<s<<" "<<"min="<<min(c,min(c1,c2))<<" "<<" max= "<<maxc<<ln;continue;}
               if(l5!=string::npos )
               atob(i,l4,l5)
               {
                   if(s.at(i)<='9'||s.at(i)>='0'||s.at(i)=='A') c3++;
               }
                         
             cout<<min(min(c,c1),min(c2,c3))<<" "<<maxc<<ln;
      }
 return 0;

}

Here is the simplest solution, thinking of finding shortest subarray and longest subarray where in both consecutive element <=2

def longestSubArray(p):
    i = 0
    j = 1
    curr_lg = max_lg = 1
    while j<len(p):
        if p[j] - p[j-1] <=2:
            curr_lg += 1
        else:
            curr_lg = 1
        j += 1
        max_lg = curr_lg if curr_lg > max_lg else max_lg
    return max_lg

def shortestSubArray(p):
    i = 0
    j = 1
    curr_sm = min_sm = len(p)
    while j<len(p):
        if p[j] - p[j-1] >2:
            if j == len(p)-1:
                curr_sm = 1
            else:
                curr_sm = (j - 1) - i + 1
            i = j
        elif j == len(p)-1:
            curr_sm = j - i + 1
        j+=1
        min_sm = curr_sm if curr_sm < min_sm else min_sm
    return min_sm

for t in range(int(input())):
    n = int(input())
    p = [int(i) for i in input().split()]
    sm = shortestSubArray(p) # subarray with consecutive element <=2
    lg = longestSubArray(p) # subarray with consecutive element <=2
    print(sm, lg)

1 Like

I am getting tle. Can anyone figure out what is wrong in my solution .
https://www.codechef.com/viewsolution/32836386

Simplicity :slightly_smiling_face:

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define tc int t;cin>>t;while(t--)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ff(i,a,b) for(int i=a;i<b;i++)
#define fb(i,b,a) for(int i=b;i>a;i--)
#define ffi(i,a,b,c) for(int i=a;i<b;i+=c)
#define fbi(i,b,a,c) for(int i=b;i>a;i-=c)
#define clin(s) getline(cin,s)
#define MOD 100000000
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define ub upper_bound
#define lb lower_bound

int main() {
	fio;
	tc{
	    int n,i;
	    cin>>n;
	    int arr[n];
	    ff(i,0,n){
	        cin>>arr[i];
	    }
	    int minc=INT_MAX,maxc=1,chain;
	    bool allsep=true;
	    ff(i,0,n-1){
	        chain=1;
	        while(i<n-1&&arr[i+1]-arr[i]<=2){
	            i++;
	            chain++;
	            allsep=false;
	        }
	        
	        if(chain>maxc){
	            maxc=chain;
	        }
	        if(chain<minc){
	            minc=chain;
	        }
	    }
	    if(arr[n-1]-arr[n-2]>2&&allsep==false){minc=1;}
	    cout<<minc<<" "<<maxc<<"\n";
	}
	return 0;
}

@logic_gupta why you used nested for loop…

just find difference between the positions and find consecutive count for distance <=2 and return min(Best case) and max (worst case)of count value

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{

int t;
cin>>t;
while (t--)
{
	int n;
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	int diff[n];
	diff[0]=0;
	for(int i=1;i<n;i++)
	{
		diff[i]=arr[i]-arr[i-1];
	}
	int cnt=1;
	int mn=INT_MAX;
	int mx=INT_MIN;
	for(int i=1;i<n;i++)
	{
		if(diff[i]<=2)
		   cnt++;
		   else
		   {
			  mn=min(cnt,mn);
			  mx=max(cnt,mx); 
			  cnt=1;
		   }
		   
	}
	mn=min(cnt,mn);
	mx=max(cnt,mx);
	cout<<mn<<" "<<mx<<endl;
}

}

6 Likes

I am not able to debug what the issue is with this code. Any help?

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    int testcases = Integer.parseInt(bufferedReader.readLine());
    while(testcases > 0){
      int N = Integer.parseInt(bufferedReader.readLine());
      int[] Xs = Arrays.stream(bufferedReader.readLine().split(" "))
                       .mapToInt(Integer::parseInt)
                       .toArray();
      int prevX = Xs[0];
      int clusterSize = 0;
      int min = 1000;
      int max = -1;
      for(int x : Xs){
        if(x - prevX <= 2){
          clusterSize += 1;
        }
        else {
          if(clusterSize < min){
            min = clusterSize;
          }
          else if(clusterSize > max){
            max = clusterSize;
          }
          clusterSize = 1;
        }
        prevX = x;
      }
      if(min == 1000){
        min = clusterSize;
      }
      if(max == -1){
        max = clusterSize;
      }
      System.out.println(min + " " + max);
      testcases--;
    }
  }

I have been working on this for 4 hours , i have no idea why it is not working…it seems correct to me.
please guys any help i will be very great-full.
https://www.codechef.com/viewsolution/33106375

one thing I can spot is

       if(best=1)

besides this there is also a logical error .
Just check for some testcases.

5
5
0 3 6 9 10 Output : 1 2
7
0 1 4 5 8 9 10 Output: 2 3
6
0 1 4 5 8 9 Output : 2 2
5
0 1 4 7 10 Output : 1 1
8
0 1 2 3 4 5 6 7 Output : 8 8

Grateful …
You are not checking for middle cases where minimum group can be between Some max groups . Besides these min can never be 10 as there are only 8 people .
Just check for these .

4
5
0 3 6 9 10 Output : 1 2
7
0 1 4 5 8 9 10 Output: 2 3
6
0 1 4 5 8 9 Output : 2 2
8
0 1 2 3 4 5 6 7 Output : 8 8

2 Likes

I missed this case, thanks.

1 Like

PLease have alook at my solution in java
https://www.codechef.com/viewsolution/33152156
I think this question is the most easy to understand.

:slightly_smiling_face:

feeling happy to help someone in a way

1 Like

Good Logic

can you find out where i am wrong

how this is possible bro .
5
0 1 4 7 10
output min=1,max=1 max value should be 2 here like in case if 0 is infected or 1 is infected

1 Like

Thanks for correcting me bro.