ERROR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Mahbub
Editorialist: Jingbo Shang

DIFFICULTY:

Cakewalk

PREREQUISITES:

Programming Language.

PROBLEM:

Determine whether the given binary string contains the substring (consecutive) “010” or “101”.

EXPLANATION:

You can use a loop and condition clauses to check directly. Also, you can use some built-in functions to solve this problem too.

For example, C++, we can use

int position = strstr(s, "010") - s;

to get the first occurrence of “010” and check whether this position is in range. Or, if string is used in C++, then

int position = s.find("010");

will work for string.

Similarly, Java, Python, etc… a lot of languages have such functions. Post your accepted solution and let’s find which one is the shortest! I think it will be interesting :stuck_out_tongue:

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

Using Python’s elegance
http://www.codechef.com/viewsolution/3250941

for _ in xrange(input()):
    s = raw_input()
    if "010" in s or "101" in s: print "Good"
    else:                        print "Bad"

P.S.: Waiting for a one liner in Perl or GolfScript :stuck_out_tongue:

UPDATE: If that’s the case @shangjingbo, then how about a Perl regex check

$s =~ m/"101"/
1 Like
3

Well, when I’m good with Monads I can return and fully solve this one in Haskell, but, the built-in functions sure are a charm:

isInfixOf "010" "10010"

:smiley:

1 Like
4

I think it may be the shortest one :slight_smile:

5

sound great, but you have benn beaten by @kuruma, have another try :smiley:

1 Like
6

@shangjingbo >> I was not trying to enter any competition for shortest code. I was just demonstrating Python’s elegance. :smiley:

7

The problem with this check is that it doesn’t receive input and produce output, instead, it can be used in an interactive fashion, but, I’m loving Haskell so far :smiley:

8

Wow, great!

9

I foolishly tried to implement “Z- algo”… :P. Someone kick me on my ass…

4 Likes
10

@all:

May i know what is wrong with this approach. http://www.codechef.com/viewsolution/3177973

I was checking characters at i, i-1, i-2 in a loop.

Thanks :slight_smile:

11

You missed corner case when length < 3, for example for

1
1

your code returns ‘Good’…

1 Like
12

feeling bad to have missed this case :frowning: thanks

13

don’t be sad, I can write a book about stupid bugs I did in contests :smiley:

My advice here is, do not use some side effects (like if I scanned whole string), use additional boolean flag that is set to false at the beginning and when you really find what you are looking for, set it to true.

Also you do not need to use such difficult input reading, see my code (http://www.codechef.com/viewsolution/3153331 ) for this problem if you want or this one (http://www.codechef.com/viewsolution/3250870 ), to see how to use StringTokenizer.

14

what is wrong wid this…
#include <stdio.h>
#include <conio.h>
#include <string.h>
int main(void)
{
int t;
char a , b , c ,d ,count ;
scanf("%d" , &t);
while(t–)
{
count = 0;
a = getchar();
b = getchar();
c = getchar();
while( (d = getchar()) != ‘\n’)
( (a==‘0’ && b==‘1’ && c==‘0’) || (a == ‘1’ && b==‘0’ && c==‘1’)) ? ( (count++) , (a = b) , ( b = c) , (c = d )): ((a = b) , ( b = c), (c = d ));
(count > 0)?(printf(“Good\n”)):(printf(“Bad\n”));
}
getch();
return 0;
}

15

what is wrong with this…
#include <stdio.h>
#include <string.h>
int main(void)
{
int t;
char a , b , c ,d ,count ;
scanf("%d" , &t);
while(t–)
{
count = 0;
a = getchar();
b = getchar();
c = getchar();
while( (d = getchar()) != ‘\n’)
( (a==‘0’ && b==‘1’ && c==‘0’) || (a == ‘1’ && b==‘0’ && c==‘1’)) ? ( (count++) , (a = b) , ( b = c) , (c = d )): ((a = b) , ( b = c), (c = d ));
(count > 0)?(printf(“Good\n”)):(printf(“Bad\n”));
}
return 0;
}

16

@ rd13123013
When 010 or 101 comes at the last of the string …then d==’\n’ .Therefore ,it doesn’t enters into While loop…so the count doesn’t increasing …and there lies the bug.

 So , you can overcome this by using "do() ...while()..loop" :)
1 Like
17

int main()
{
int t;
cin>>t;
while(t–) {
std::string str("");
cin>>str;
if((str.find(“010”)==!std::string::npos) || (str.find(“101”)==!std::string::npos))
{
cout<<endl<<“Good”<<endl;
}
else
{
cout<<endl<<“Bad”<<endl;
}
}
system(“pause”);
return 0;
}

18

Try pasting ur code after pressing CTRL+K

19

What is wrong with this code? Similar code accepted in java but this is not working.

class Sample7

@t=0
@str

def initialize
t=gets.to_i

for i in 0...t
  str=gets
  if str.include?"101"||"010"
    puts "Good"
  else puts "Bad"
  end
end

end
end

obj=Sample7.new

20

WHAT IS WRONG IN MY CODE?
#include
#include<string.h>
using namespace std;
int main()
{
int t;
long int l,i,c,d,j,e;
cin>>t;
while(t–)
{
char s[100005];
cin>>s;
l=strlen(s);
for(i=0;i<l-2;i++)
{
e=2;
c=0;
j=i;
while(e–)
{
if(s[j]!=s[j+1])
c++;
else
break;
j++;
}
if(c==2)
{
cout<<“good”<<endl;
break;
}
}
if(c!=2)
cout<<“bad”<<endl;
}
return 0;
}