 # SPELLBOB - Editorial

Practice

Contest

Author: Praveen Dhinwa

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

CAKEWALK

# Prerequisites

Looping Techniques

# Problem

You are given 3 cards with letters written on both sides. You can permutate the cards or flip them. After you do all operations, the cards should spell “Bob” on the top face.

# Explanation

First, fix the letter o for the middle card. Now, try the remaining cards and check if both of them contain a “b” on either side of them. A pseudo-code for the above approach is:

``````
s = input()
t = input()
for i in [0, 2]:
if s[i] == 'o' or t[i] == 'o':
cnt = 0
for j in [0, 2]:
if j != i:
if s[j] == 'b' or t[j] == 'b':
cnt += 1
if cnt == 2:
ok = True

``````

Feel free to share your approach, if it was somewhat different.

# Time Complexity

O(|S| * |S|) per test case.

O(|S|)

# SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

Editorialist’s solution can be found here.

1 Like

Each card is one of the following cases:
(a) it has a b on one side and an o on the other
(b) it has a b but no o
© it has an o but no b
(d) it has neither o nor b

if we encounter a (d) card, we cannot succeed.

Otherwise, if (and only if) we have at least 2 of (a)s and (b)s and at least 1 of (a)s and ©s, we can make bob. So just count the different types as read and test at the end.

1 Like

We can also do like:
Count the b’s and o’s occuring at every position. (Since, the length of the string is 3 only, we can store the count of b’s and o’s in two arrays, say b and o).

Then, there are only three possible combinations for making “bob”.

1. “bbo” b=1, b=1 and o=1
2. “bob” b=1, o=1 and b=1
3. “obb” o=1, b=1 and b=1

#### Below is an implementation in C:##

``````
#include<stdio.h>
int main()
{
int t,i;
scanf("%d",&t);
while(t--)
{
char st1,st2;
scanf("%s",st1);
scanf("%s",st2);
int b[]={0,0,0};
int o[]={0,0,0};
for(i=0;i<3;i++)
{
//for string 1
if(st1[i]=='b')
b[i]++;
else	if(st1[i]=='o')
o[i]++;
//for string 2
if(st2[i]=='b')
b[i]++;
else	if(st2[i]=='o')
o[i]++;
}
if( (b>=1&&b>=1&&o>=1) || (b>=1&&o>=1&&b>=1) || (o>=1&&b>=1&&b>=1))
printf("yes\n");
else
printf("no\n");
}
return 0;
}

``````
1 Like

## For “bob” there are three possible permutations 1. “bob” 2. “obb” 3. “bbo”. So we need to find out these permutations are possible to make out from those two string or not. If it is possible then print “yes” and if not then print “no”. One thing we can notice here is that there are only eight possible permutations we can have from those strings. We can generate all those strings using binary encoding and store in a string array. Reason for only 8 possible permutations is - If we take ith character from the first string we cannot take the ith character from the second string. Here is my solution below:

``````#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define max1 1001
ll n,m;
int main()
{
//fast
ll t;
cin>>t;
while(t--)
{
string s1,s2;
cin>>s1>>s2;
string s3;
s3="000";//picking all characters from 1st string.
s3="001";//picking first two characters from 1st string and last character from 2nd string
s3="010";//first and last character from 1st string and middle character from 2nd string
s3="011";//last two characters from 2nd string and 1st character from 1st string
s3="100";//only first character from 2nd string and rest from 1st string
s3="101";//ends characters from 2nd string and middle from 1st string
s3="110";//first two characters from 2nd string and last from 1st string
s3="111";//all are from 2nd string.
//Generating all the strings from above encoding.
for(int i=0;i<8;i++)
{
for(int j=0;j<3;j++)
{
if(s3[i][j]=='0')
{
s3[i][j]=s1[j];
}
else
{
s3[i][j]=s2[j];
}
}
}
int flag=0;
for(int i=0;i<8;i++)
{
if(s3[i]=="bob" || s3[i]=="obb" || s3[i]=="bbo")
{
flag=1;
break;
}
}
if(flag)//checking
cout<<"yes\n";
else
cout<<"no\n";
}
}
``````

Note: Instead of storing the encoding first and then generate all the strings, we can do it directly.
I hope this solution will make it easy for you to understand.

1 Like

Much shorter in Python using the same approach of checking for each permutation- ‘bob’, ‘bbo’ and ‘obb’

``````for i in range(int(input())):
front = input()
back = input()

lis = [[i, j] for i, j in zip(front, back)]

if ('o' in lis and 'b' in lis and 'b' in lis) or ('b' in lis and 'o' in lis and 'b' in lis) or ('b' in lis and 'b' in lis and 'o' in lis):
print('yes')
else:
print('no')``````
1 Like

This suggests a whole series of harder potential challenges of longer words with different amounts of repeated letters, eventually perhaps reaching:

“Given m two-sided cards and a series of n words, how many ways can each word be made from the cards?”

1 Like

Since we can permutate the cards in any order that we wanted and as long as it can spell “Bob” in the end, shouldn’t the below work? Basically, we just have to find the letter b, o, and b on 3 separate cards, whether on the top or the flip side of the card.

*** Edit: I also translate my code to python and compare to the example code and both code split out the same. However, when I submit my code in C, the system just did not accept it at all.

*** Edit: Nevermind :). I debug it and now know why my code was wrong. I forgot about the situation where the ob and be on one card. For example “obb” and “bbb”. That would make my code produce false even though there is an o, because my code would evaluate for the b first. Thank you for this discussion. Without it, I might never beable to debug the code.

*** Edit: OMG, I am so stupid, I can’t believe I forgot, what whould happen if “o” and “b” were together :(. All the code I posted earlier was wrong. The author’s code is the best for looping. The only method that is faster than that is a bit of a cheat. Nonetheless, I put the cheat code first. All the code below the cheat code is just for archiving.

My Correct Code, After Learning About o,b were together on the same line

``````def spellBob ( s, t ):
result = False

if (s == 'o' or t == 'o') and (s == 'b' or t == 'b') and (s == 'b' or t == 'b'):
result = True
elif (s == 'o' or t == 'o') and (s == 'b' or t == 'b') and (s == 'b' or t == 'b'):
result = True
elif (s == 'o' or t == 'o') and (s == 'b' or t == 'b') and (s == 'b' or t == 'b'):
result = True

return result
``````

WRONG CODE FOR C

``````int main()
{
int c, i, ind;
char a, b;

scanf("%d",&c);

for (i = 0; i <= c; i++){
gets(a);
gets(b);

char m[] = "bob";

for ( ind = 0; ind < 3; ind++ ){
if ( a[ind] == m || b[ind] == m ){
m = '1';
} else if ( a[ind] == m || b[ind] == m ){
m = '1';
} else if ( a[ind] == m || b[ind] == m ){
m = '1';
}
}

if ( m == '1' && m == '1' && m == '1'){
printf("yes\n");
} else {
printf("no\n");
}
}
return 0;
}
``````

WRONG CODE FOR Python. Note that the author’s code is right.

``````T = int(input())
for _ in range(T):
s = input()
t = input()
ok = False
for i in range(3):
if s[i] == 'o' or t[i] == 'o':
cnt = 0
for j in range(3):
if j != i:
if s[j] == 'b' or t[j] == 'b':
cnt += 1
if cnt == 2:
ok = True
print("yes" if ok else "no");

b1 = 'b'
o  = 'o'
b2 = 'b'

for i in range(3):
if s[i] == b1 or t[i] == b1:
b1 = '1'
elif s[i] == o or t[i] == o:
o = '1'
elif s[i] == b2 or t[i] == b2:
b2 = '1'

bob = b1 + o + b2

print("yes" if bob == "111" else "no");
print"\n"
``````

I test the following test case again them and they spat out the same result.

``````STDIN Below:
7
"nbo"
"bcn"
"ebo"
"bcn"
"nbo"
"bcn"
"oxe"
"nob"
"oxe"
"nbb"
"oxe"
"nbb"
"xoo"
"boo"
``````

Wrong Code

``````b1 = 'b'
o  = 'o'
b2 = 'b'

for i in range(3):
if s[i] == o or t[i] == o:
o = '1'
elif s[i] == b1 or t[i] == b1:
b1 = '1'
elif s[i] == b2 or t[i] == b2:
b2 = '1'

bob = b1 + o + b2

print("yes" if bob == "111" else "no");
print"\n"``````

package continueFromDefault;
import java.util.*;
public class SpellBob {

``````	public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner sc = new Scanner(System.in);

int cases = sc.nextInt();

while(cases-->0)
{
String s1 = sc.next();
String s2 = sc.next();

char arr[] = s1.toCharArray();
char arr1[]  = s2.toCharArray();

int counter = 0;

//1
if(arr=='b'||arr=='o')
counter++;
else
if(arr1=='b'||arr1=='o')
counter++;

//2
if(arr=='o'||arr=='b')
counter++;
else
if(arr1=='b'||arr1=='o')
counter++;

//3
if(arr=='o'||arr=='b')
counter++;
else
if(arr1=='b'||arr1=='o')
counter++;

if(counter==3)
System.out.println("yes");
else
System.out.println("no");

}
}

}
``````

why codechef compiler gives an error?

I have used permutation to do this using the below code

import java.util.Scanner;

public class Main {

``````public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int arr1[][]= {	{0,1,2},
{0,2,1},
{1,0,2},
{1,2,0},
{2,0,1},
{2,1,0}	};
char ch[]= {'b','o','b'};
/*for(int i=0;i<6;i++) {
for(int j=0;j<3;j++) {
System.out.print(arr1[i][j]);
}
System.out.println(" ");
}*/
int numOfTestCase=sc.nextInt();
for(int i=0;i<numOfTestCase;i++) {
String s1=sc.next();
char sp1[]=s1.toCharArray();
String s2=sc.next();
char sp2[]=s2.toCharArray();
int count=0;
for(int j=0;j<6;j++) {
int num1=0;
count=0;
for(int k=0;k<3;k++) {
//System.out.println(arr1[j][k] + " "+ "unm1" + " "+num1+ " j"+" "+j+" "+k);
if(sp1[arr1[j][k]] == ch[num1] || sp2[arr1[j][k]] == ch[num1]) {
count++;
}else
break;
num1++;
}
if(count==3)
break;
}
if(count==3)
System.out.println("yes");
else
System.out.println("no");
}
}
``````

}

#include <stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
int i,j,t;
int *temp;

``````scanf("%d",&t);
temp=(int*)malloc(sizeof(t));
for(i=0;i<t;i++)
{

char s1;
char s2;
scanf("%s",s1);
scanf("%s",s2);

int b[]={0,0,0};
int o[]={0,0,0};

for(j=0;j<3;j++)
{
if(s1[j]=='b')b[j]++;
else if(s1[j]=='o')o[j]++;

if(s2[j]=='b')b[j]++;
else if(s2[j]=='o')o[j]++;
}

if((b>=1 && b>=1 &&o>=1) || (o>=1 && b>=1 &&b>=1)||(b>=1 && o>=1 && b>=1))
{
temp[i]=1;
}
else
{
temp[i]=0;
}

}
system ("clear");
for(i=0;i<t;i++)
{
if(temp[i]==0)
{
printf("no\n");
}
else
{
printf("yes\n");
}
}

return 0;
``````

}

Given below is what i implemented in c++.can someone tell me what am i doing wrong here?
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–){
string up,down;
int j,ans=0;
fflush(stdin);
cin>>up;
cin>>down;
vector b;
vector f;
for(int i=0;i<3;i++){
b.push_back(true);//for cards
f.push_back(true);//for bob
}
string bob =“bob”;
for(int i=0;i<3;i++){
for(j=0;j<3;j++){
if(b[j]&&f[i]){
if(up[j]==bob[i]||down[j]==bob[i]){
b[j]=false;
f[i]=false;

``````          }
}
}
if(f[i])
break;
}
for(int i=0;i<3;i++){
if(b[i])
ans=1;
if(f[i])
ans=2;
}

if(!ans)
cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}``````

I’ve used a basic approach. The 3 different cards need to have a ‘b’ or an ‘o’. Also we need at least 1 ‘o’ and 2 'b’s on different cards. I’ve checked for various possibilities and it holds good.

``````#include<iostream>
using namespace std;
int main()
{
int T,j,k=0,l=0;
cin>>T;
while(T--)
{
string a,b;
cin>>a;
cin>>b;
for(j=0;j<3;j++)
{
if((a[j]=='b')||(b[j]=='b'))
++k;                       //count
if((a[j]=='o')||(b[j]=='o'))   //dont use else if
++l;
else break;
}
if((j==3)&&(k>=2)&&(l>=1))
cout<<"yes\n";
else
cout<<"no\n";
k=0;l=0;
}
return 0;
}

``````

But this is not working for strings “lol” and “obb” when it should. Please help me if you find anything.

hey,

I am definite about the accuracy of my code, but I somewhat get awrong answer…

this is the code:

``````t = int(input())
``````

for _ in range(t):
a,b,c=[s for s in input()]
d,e,f=[r for r in input()]
a+=d
b+=e
c+=f

``````letters=[a,b,c]

bob=""

for i in letters:
for j in i:
if j=='b' and bob.count('b')<2:
bob+=j
elif j=='o' and bob.count('o')<1:
bob+=j
if len(bob)==3:
else:
``````

print(x)

1 Like

I can’t see how m ever gets set. If there’s a b available, it sets m.

That is true. If there is one b available it will set m. However, if m is already found and there is another b, it will set m.

The condition is that there must be 2 b on a separate cards, and an o on one other separate card.

Try the code, and test it again the example test case. It will work. But for some reason, it will not run on the system. It just spits out 0.00 memory ran. Thus, I assumed, it didn’t even get run at all.

My approach using DFS

``````#include <iostream>
#include <string>
using namespace std;

bool dfs(string& a, string& b, int i, int nb, int no){
if(i>2){
if(nb+no==0) return true;
return false;
}
return (nb>0 && (a[i]=='b' || b[i]=='b') && dfs(a, b, i+1, nb-1, no)) || (no>0 && (a[i]=='o' || b[i]=='o') && dfs(a, b, i+1, nb, no-1));
}

int main(){
int t, n, i;
string a, b;
cin >> t;
while(t-->0){
cin >> a;
cin >> b;
if(dfs(a, b, 0, 2, 1)) cout << "yes\n";
else cout << "no\n";
}
return 0;
}``````

whats wrong in my code???

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

int main() {
int t;
cin>>t;
while(t–){
string s1,s2,a=“bob”;
cin>>s1>>s2;
int k=0,p;
for(int i=0;i<3;i++)
p[i] = 1;
for(int i=0;i<s1.length();i++){
for(int j=0;j<s2.length();j++){
if(((s1[j]==a[k])||(s2[j]==a[k]))&&p[j]){
p[j] = 0;
k++;
break;
}
}
}
if(k==3)
cout<<“yes”<<endl;
else
cout<<“no”<<endl;
}
return 0;
}

Can Someone tell me what’s wrong with my code?

for _ in range(int(input())):
a=input()
b=input()
s=[‘b’,‘o’,‘b’]
if a==“bob” or b==“bob”:
print(“yes”)
else:
for i in range(len(a)):
if (a[i] in s) and (b[i] in s):
if b[i]==“o”:s.remove(b[i])
elif a[i]==“o”:s.remove(a[i])
else:s.remove(a[i])
elif a[i] in s:
s.remove(a[i])
elif b[i] in s:
s.remove(b[i])
if len(s)==0:
print(“yes”)
else:
print(“no”)