SEGM01 - Editorial

general
, , ,
1

Practice

Contest

Author: Kamil Debowski

Tester: Lewin Gan

Editorialist: Misha Chorniy

Difficulty:

Cakewalk

Pre-Requisites:

None

Problem Statement

Given a string S. Each character of S is a digit ‘0’ or ‘1’. You need to check if all the ‘1’ digits form a single non-empty segment(consecutive subsequence) in the string.

Subtask 1

Length of S in this subtask will be not more than 50. If segment of '1’s exists, it should be consecutive. Let’s iterate over left bound of segment and right bound of segment, and check if only '1’s lies inside this segment, and only '0’s are out of the segment. Complexity of such algorithm is: O(S^3)

Subtask 2

Define L - leftmost position of digit ‘1’ in S, R - rightmost position of digit ‘1’ in S. Corner case is: when all characters in S are '0’s, then answer is “NO” as the segment from '1’s is empty. If exists at least one digit ‘1’ in S then all characters between L and R must be equal ‘1’, otherwise subsegment from '1’s is not consecutive. How to check it? Using one simple “if”, if(R-L+1 = C), where C is frequency of '1’s in S. Total complexity of this algorithm is O(S).

Solution:

Setter’s solution can be found here

Tester’s solution can be found here

Please feel free to post comments if anything is not clear to you.

1 Like
2

I cant find error in my code…it gives correct answer for half of the test cases …
https://www.codechef.com/viewsolution/14151559

Here is my solution…

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

int main()
{
int n;scanf(“%d”,&n);
while(n–)
{
char s[1000005];
scanf(“%s”,s);
bool trig=false,done=false; int i;
for(i=0;i<strlen(s);i++)
{
if(trig){if(s[i]==‘0’){trig=false;}}
else{if(s[i]==‘1’&&done){puts(“NO”);break;}else if(s[i]==‘1’){trig=true;done=true;}}
}
if(i==strlen(s)&&done){puts(“YES”);}
}
return 0;
}

3

@harshitsaini

your code is not printing anything if string doesn’t contain any 1’s.

try this input

1

00000

1 Like
4

@hruday968

Thanx for the bug…got it corrected.

1 Like
5

#include<stdio.h>
int main(){
int t;
long int s,q,r;
scanf("%d", &t);
while(t–){
scanf("%ld",&s);
if(s==0)
printf(“NO \n”);
else{
q=s;
while(q%10==0)
q/=10;
r=1;
while(r==1){
r=q%10;
q=q/10;
}
if(q!=0)
printf(“NO \n”);
else
printf(“YES \n”);
}
}
return 0;
}

what is wrong with this solution? Even codechef compiler is giving the expected output (as of the test cases mentioned) but on submitting, I receive WA error.

6

Anytime bro!

7

Why is it showing TLE in subtask 2
/*
// Sample code to perform I/O:

cin >> name; // Reading input from STDIN
cout << "Hi, " << name << “.\n”; // Writing output to STDOUT

// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
*/

// Write your code here
#include <bits/stdc++.h>
#define ll signed long long
using namespace std;

int hcf(int n,int m)
{
if(m==0)
return n;
else
return hcf(m,n%m);
}
//int a[100004];

void solve()
{

//cout<<s<<" “<<s1<<”\n";
//cout<<lcm<<" “<<d<<” “<<d1<<” “<<”\n";
// cout<<lcm/d<<" “<<lcm/d1<<” “<<”\n";
string s;
cin>>s;
ll c=count(s.begin(),s.end(),‘1’);
if(c>0){vector v(c,‘1’);
auto it=search(s.begin(),s.end(),v.begin(),v.end());
if(it!=s.end())
cout<<“YES”;
else
cout<<“NO”;
}
else
cout<<“NO”;

//cout<<s.size();

cout<<"\n";

//cout<<n<<"\n";
}

int main()
{
//cout<<“Hello World”;

int t;
cin>>t;
//ll cnt=0;
while(t–)
{solve();}
//cout<<hcf(72,36);

return 0;

}

9

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

void solve()
{
string s;
cin>>s;
int pos1=-1;
int pos2=-1;
for(int i=0;i<s.length();++i)
{
if(s[i]==‘1’){
pos1=i;
break;
}
}
for(int i=s.length();i>=0;–i)
{
if(s[i]==‘1’){
pos2=i;
break;
}
}
int flag=1;
if(pos1==-1 && pos2==-1){
flag=0;
}

else{
for(int i=pos1;i<=pos2;++i){
if(s[i]!=‘1’){
flag=0;
break;
}
}
}

if(flag==0){cout<<“No”<<"\n";}
else cout<<“Yes”<<"\n";

}

int main()
{

int t;
cin>>t;
while(t--)
{
	solve();
}

return 0;

}

Can anyone tell me why I am getting the wrong answer?

10

import java.util.Scanner;

public class Sts {

public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);

    int t,j,n,k;

    int ans;

    String a,b;

    t=sc.nextInt();

    for(int i=0;i<t;i++){

        a=sc.next();

        n=0;

       

        for(j=0;j<a.length();j++){

            if(a.charAt(j)=='1')

            n++;

        }

        char c[]=new char[n];

        for(j=0;j<n;j++){

            c[j]='1';

        }

        b=String.valueOf(c);

        ans=a.indexOf(b);

        
                       

        if(ans!=-1&&n>0)

        System.out.println("yes");

        else

        System.out.println("no");

      
       

    

    }

    sc.close();

}

    

}

solution is wrong
if i try the example inputs the answer in coming right
i need to know what the problem is with the code

11

don’t worry silly mistake
answers should have been in CAPS

12

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define IOP freopen(“input.txt”, “r”, stdin); freopen(“output.txt”, “w”, stdout);

#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);

#define twhile ll t; cin >> t; while(t–)

int solve() {

string s;

cin >> s;

bool started =false; // to keep track of the starting of 1 s

int count =0; // to count subsequence

for(int i=0;i<s.length();i++){

if(s[i]=='1'){

     started=true;

}

if(started == true){

    if(s[i]=='0'){

        started= false;

        count ++;

    }

     else if(s[i]=='1' && i==s.length()-1){

        count++;

     }

}

}

if(count==1){

cout << "YES" << endl;

}

else{

cout << "NO" << endl;

}

}

int main(){

    FIO

    IOP

    twhile{

       

      solve() ;

    }

     

    return 0;

}
13

WORKING SOLUTION IN C++ ALL TEST CASE PASSED

#include

using namespace std;

int main()
{int t;
cin>>t;
while(t–)
{ int count=0;
int index=-1;
string s;
cin>>s;
for(int i=0;i<s.size();i++)
{if(s[i]==‘1’)
{if(index==-1)
index=i;
count++;
}
}
bool val=true;
if(index!=-1)
{for(int k=index;k<index+count;k++)

{
   if(s[k]=='0')
   {val=false;
   break;
   }
}

}
else
val=false;

if(val)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;

}

return 0;

}

:pensive: BUT I PERSONALLY NOT FOUND THIS QUESTION A CAKEWALK QUESTION AS MENTIONED BY SETTER​:eyes:

14

Please help me in finding the mistake.
It is only passing first subtask(even though the time complexity is O(n) ).
@hruday968 @suhas_manju @king_786 @mgch @errichto
Thanks for your time.

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

int main() {
	int t=0;
	cin>>t;
	for(int e=0;e<t;e++){
	   string s;
	   cin>>s;
	   int n=s.size(),flag=0,one=0 ;
	   for(int i=0;i<n-1;i++){
	       if(s[i]=='1')one=1;
	       if(one){
	       if(s[i]=='0'&&s[i+1]=='1')flag++;
	       }
	   }
	   if(flag||one==0) cout<<"NO\n";
	   else cout<<"YES\n";
	}
}