SNAPCHAT - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: iceknight1093, rivalq
Editorialist: iceknight1093

DIFFICULTY:

965

PREREQUISITES:

None

PROBLEM:

On the i-th day, Chef sent A_i snaps to Chefina, and Chefina sent B_i snaps to Chef.
What is their longest streak?

EXPLANATION:

Let’s call the i-th day good if A_i \gt 0 and B_i \gt 0.

The longest streak is then nothing but the longest consecutive set of good days.

One way of computing this is as follows:

  • Let cur denote the length of the current segment of good days. Initially, cur = 0.
  • Let ans denote the final answer. Initially, ans = 0.
  • Then, for each i from 1 to N:
    • If the i-th day is good, increase cur by 1. Otherwise, reset cur to 0.
    • Then, set ans = \max(ans, cur)

In the end, ans is the answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans, cur = 0, 0
    for i in range(n):
        if a[i] > 0 and b[i] > 0: cur += 1
        else: cur = 0
        ans = max(ans, cur)
    print(ans)
2 Likes

My C++ Solution :

#include<bits/stdc++.h>
using namespace std;

#define endl “\n”
#define ll long long

int solve(int a[] ,int b[] , int n ){
int count=0, maxcount=0;
for(int i = 0 ; i<n;i++){
if(a[i]>0 && b[i]>0){
count++;
maxcount= max(maxcount , count) ;
}
else count=0; //streak break
}
return maxcount;
}

int main(){
//MAKES INPUT OUTPUT FAST
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t–){
int n ;
cin>> n;
int a[n] , b[n] ;
for(int i = 0 ; i< n ;i++){
cin >> a[i] ;
}
for(int i = 0 ; i< n ;i++){
cin >> b[i] ;
}

    cout << solve(a , b , n) << endl ;
    
}

return 0;
}