HCAGMAM1 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Vasu
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

The schedule of Chef’s job is given by a string S with length 30. S_i = 1 means that chef has worked on that day and S_i=0 means that chef hasn’t worked on that day. Also, Y Rs bonus will be given in everday on the longest consecutive streak of days that chef has worked (if multiple longest streaks are posssible only one such streak is selected for bonus). We need to find the total salary of chef on that month.

EXPLANATION:

  • Let tot be the total number of ones (working days) in S.

  • Let us also find max where max is the maximum length of consecutive ones in S.

  • This can be simply done by looping over the string S, and we keep track of the number of consecutive ones ending at index i, for all 1 \leq i \leq N. The maximum over all these values is equal to max.

  • The total salary will then equal to tot \cdot X + max \cdot Y.

TIME COMPLEXITY:

O(length(S)) for each testcase.

SOLUTION:

Editorialist's solution
Setter's solution 
#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int main()
{
    ll t;
    cin>>t;
    
    while(t--)
    {
        ll x,y;
        cin>>x>>y;
        
        string s;
        cin>>s;
        
        ll countd=0;
        ll maxx=0;
        
        ll count=0;
        
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='1')
            {
                countd++;
                count++;
            }
            else
            {
                count=0;
            }
            
            maxx=max(maxx,count);
        }
        
        cout<<(countd*x)+(maxx*y)<<endl;
    }
}
Tester's solution 
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int x, y;
    cin>>x>>y;
    string s;
    cin>>s;
    int n = s.size();
    int mx = 0;
    int temp = 0;
    int ans = 0;
    for(int i = 0; i < n; i++){
      if(s[i] == '1'){
        temp++;
        ans += x;
      }else{
        temp = 0;
      }
      mx = max(mx, temp);
    }
    ans += mx * y;
    cout<<ans<<"\n";
  }
  return 0;
}

Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

1 Like