your time complexity is O(n^2)
Getting WA in 2 test case
What am i missing here …??
https://www.codechef.com/viewsolution/28014565
#include<bits/stdc++.h>
#include
#define ll long long int
using namespace std;
int main(){
ll t; cin>>t;
while(t–){
ll n,k; cin>>n>>k;
string s; cin>>s;
int ans = INT_MIN, tmp = 0, kk = 0;
if(n <= k){
ans = n;
cout<<ans<<endl;
}
else{
// ans = k;
for(int i=0;i<n-k;i++){
int j = i+k;
int l = i-1;
tmp = k;
for(;j<n;j++){
if(s[j] == '1'){
tmp++;
}
else{
break;
}
}
for(;l>=0;l--){
if(s[l] == '1'){
tmp++;
}
else{
break;
}
}
ans = max(ans,tmp);
}
cout<<ans<<endl;
}
}
return 0;
}
please inform me what’s wrong in this code:
link: CodeChef: Practical coding for everyone
from itertools import groupby
t = int(input())
while t>0:
n, k = input().split()
n = int(n)
k = int(k)
st = input()
ans = [0]
for x, y in groupby(st):
if x == '1':
ans.append(len(list(y)))
#print(x , )
a = min(n, max(ans)+k)
print(a)
t = t-1
What’s wrong with this approach.here i am trying to find max consecutive ones and then adding k to it taking care of boundary conditions.
https://www.codechef.com/viewsolution/28013706
can you please reveal a testcase for which my approach doesn’t work?
Can anyone please tell why tle in my code? According to me its time complexity is n*t which should be acceptable.
#include<bits/stdc++.h>
#define ll long long
#define vi vector
#define vll vector
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i–)
#define si set
#define sll set
#define ins insert
#define vpp vector<pair<int,int>>
#define mp make_pair
#define ft first
#define sc second
using namespace std;
struct interval{
int f,s;
};
int main(){
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
string s;
cin>>s;
int i=0;
interval v[n];
int mx=INT_MIN;
while(i<n){
int j=i;
if(s[i]==‘0’){
i++;
if(mx<0)
mx=0;
continue;
}
while(j<n && s[j]==‘1’){
j++;
}
if(j-i >mx)
mx=j-i;
i=j;
}
i=0;
int p=0;
int ans=0;
while(i<n){
int j=i;
if(s[i]==‘0’){
i++;
if(mx==0){
ans=min(n,k);
break;
}
continue;
}
while(j<n && s[j]==‘1’){
j++;
}
if(j-i ==mx){
v[p].f=i;
v[p].s=j-1;
p++;
}
i=j;
}
i=0;
if(ans==0){
while(i<p){
int l=v[i].s-v[i].f+1;
if((v[i].s+k < n)||(v[i].f-k>=0)){
ans=l+k;
break;
}else{
int op1,op2;
if(v[i].s+k >= n){
op1=n-v[i].f;
}if(v[i].f-k<0){
op2=v[i].s+1;
}
if(ans<max(op1,op2)){
ans=max(op1,op2);
}
}
}
}
cout<<ans<<"\n";
}
return 0;
}
No,I think it is O(n) only
Why only one test case passes in this CodeChef: Practical coding for everyone
I used different approach.
No. It’s Linear.
can anyone please explain what is the problem in my code -
my code is understandable easily.
my code is -
#include <bits/stdc++.h> using namespace std ; int main() { int t ; cin>>t ; while(t--) { int n,k ; cin>>n>>k ; string str ; cin>>str ; if(n==k) { cout<<n<<"\n" ; continue ; } vector<pair<int,int> > val ; int kmax=0 ; for(int i=0;i<n;i++) { if(str[i] == '1') { int j=i; for(j=i;j<n;j++) { if(str[j] =='1') kmax++ ; else { break ;} } val.push_back(make_pair(kmax,i) ) ; i=j-1 ; kmax=0 ; } } if(val.size()==0) { cout<<k<<"\n" ; continue ; } sort(val.begin(),val.end()) ; //cout<<"val is \n" ; int ans=0,temp ; //vector<int> ans ; for(int i=val.size()-1;i>=0;i--) { if( val[i].second+1 > k ) { temp = k + val[i].first ; if(temp>ans) {ans=temp;} //break ; } else { if( val[i].first + val[i].second + k - 1 < n ) { temp = val[i].first + k ; if(temp>ans) ans = temp ; } else { if(val[i].second + k < n) { temp = n - val[i].second ; if(temp>ans) ans=temp ; } } } } cout<<ans<<"\n" ; } return 0 ; }
so I changed the code a little bit , having the data of the consecutive occurrences of 1’s in forward and backward direction, and then using it .
and here is my code but still I am getting W.A any guess why? please …
#include <bits/stdc++.h> using namespace std ; int main() { int t ; cin>>t ; while(t--) { int n,k ; cin>>n>>k ; string str ; cin>>str ; if(n<=k) { cout<<n<<"\n" ; continue ; } vector<pair<int,int> > val ; int forward[n] = {0},back[n]={0} ; int kmax=0 ; for(int i=0;i<n;i++) { if(str[i] == '1') { int j=i; for(j=i;j<n;j++) { if(str[j] =='1') {kmax++ ;forward[j]=kmax ;} else { break ;} } val.push_back(make_pair(kmax,i) ) ; i=j-1 ; kmax=0 ; } } kmax = 0 ; for(int i=n-1;i>=0;i--) { if(str[i]=='1') { int j=i ; for(j=i;j>=0;j--) { if(str[j]=='1') { kmax++ ; back[j] = kmax ; } else break ; } i=j+1 ; kmax = 0 ; } } if(val.size()==0) { cout<<k<<"\n" ; continue ; } sort(val.begin(),val.end()) ; //cout<<"val is \n" ; int ans=0,temp ; //vector<int> ans ; for(int i=val.size()-1;i>=0;i--) { if( val[i].second+1 > k ) { temp = k + val[i].first + forward[ val[i].second - k - 1 ] ; if(temp>ans) {ans=temp;} //break ; } else { if( val[i].first + val[i].second + k - 1 < n ) { temp = val[i].first + k + back[ val[i].second + k + 1 ] ; if(temp>ans) ans = temp ; } else { if(val[i].second + k < n) { temp = n - val[i].second ; if(temp>ans) ans=temp ; } if( val[i].second + val[i].first >= k ) { temp = val[i].second + val[i].first + back[ val[i].second + val[i].first + 1 ] ; if(temp>ans) ans = temp ; } } } } cout<<ans<<"\n" ; } return 0 ; }
Your code gives a different answer for
1
10 4
1111111111
every time I run it
thanks a lot , i figured out that trying to do it using only the consecutive occurrences of 1’s isn’t correct, as their can be cases of selecting the substring that may contain the consecutive 1’s in between , so have to traverse the entire array and check for the answer.
So , basically the answer to this question lies in the maximum length we can have between (i to i+k) + the forward 1’s till (i-1) + the backward 1’s till (i+k)
but still I am getting W.A why??
my code -
#include <bits/stdc++.h> using namespace std ; int main() { int t ; cin>>t ; while(t--) { int n,k ; cin>>n>>k ; string str ; cin>>str ; vector<pair<int,int> > val ; int forward[n] = {0},back[n+2]={0} ; int kmax=0 ; if(n<=k) { cout<<n<<"\n" ; break ; } for(int i=0;i<n;i++) { if(str[i] == '1') { int j=i; for(j=i;j<n;j++) { if(str[j] =='1') {kmax++ ;forward[j]=kmax ;} else { break ;} } //val.push_back(make_pair(kmax,i) ) ; i=j-1 ; kmax=0 ; } } kmax = 0 ; for(int i=n-1;i>=0;i--) { if(str[i]=='1') { int j=i ; for(j=i;j>=0;j--) { if(str[j]=='1') { kmax++ ; back[j] = kmax ; } else break ; } i=j+1 ; kmax = 0 ; } } /*cout<<"______the forward array is________\n" ; for(auto f: forward) cout<<f<<" " ; cout<<"\n_____the backward array is_______\n" ; for(auto f: back) cout<<f<<" " ; cout<<"\n" ;*/ int ans=0,temp ; //vector<int> ans ; ans = max(ans,k+back[k]) ; for(int i=1;i+k<n;i++) { ans = max(ans, forward[i-1] + k + back[i+k] ) ; } //ans = max(ans,forward[n-1-k]+k) ;= cout<<ans<<"\n" ; } return 0 ; }
This solution fails for the following testcase:
1
5 4
10000
The answer should be 5
:
Longest consecutive run of 1's = 5 obtained by changing the following marked range (of size 4) to all 1's:
10000
^ ^
Giving:
11111
just figured out how I used my last four hours but didn’t find out a bug that was in front of my eyes, all the time:rofl:
if(n<=k) { cout<<n<<"\n" ; break ; }
that break statement instead of continue .
Can any one please see why my code is not working
#include<bits/stdc++.h>
using namespace std;
int main(){
int t ;
cin >> t ;
for(int testcase = 0 ; testcase < t ; testcase++){
int n , k ;
cin >> n >> k ;
if(n<=k){
cout << n << endl ;
continue ;
}
string PizzaBroccoli = "0" ;
string temp ;
cin >> temp ;
PizzaBroccoli = PizzaBroccoli + temp ;
PizzaBroccoli = PizzaBroccoli + "0" ;
//cout << PizzaBroccoli.size() << endl ;
int LeftToRight[n+2] = {0};
int RightToLeft[n+2] = {0};
for(int i = 1 ; i <= n ; i++){
if(PizzaBroccoli[i] == '1' ){
LeftToRight[i] = LeftToRight[i-1] + 1 ;
}
}
for(int i = n ; i >=1 ; i--){
if(PizzaBroccoli[i] == '1' ){
RightToLeft[i] = RightToLeft[i+1] + 1 ;
}
}
/*
for(int i = 1 ; i <= n ; i++)
cout << LeftToRight[i] << " " ;
cout << endl ;
for(int i = 1 ; i <= n ; i++)
cout << RightToLeft[i] <<" " ;
cout << endl ;
*/
int maxPizza = INT_MIN ;
for(int i = 1 ; i+k <= n ; i++){
int total = RightToLeft[i+k] + LeftToRight[i-1] + k;
maxPizza = max(maxPizza , total) ;
}
cout << maxPizza << endl ;
}
}
Here is your AC code, with a single change .you should iterate from i =0 upto i=n-k.
https://www.codechef.com/viewsolution/48832337
Try this
1
5 1
11011