SPELLBOB - Editorial

editorial
, , ,
1

Problem Link

Practice

Contest

Author: Praveen Dhinwa

Tester: Mark Mikhno

Editorialist: Bhuvnesh Jain

Difficulty

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.

Space Complexity

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
2

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
3

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[3] and o[3]).

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

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

Below is an implementation in C:##


 #include<stdio.h>
int main()
{
	int t,i;
	scanf("%d",&t);
	while(t--)
	{
		char st1[3],st2[3];
		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[0]>=1&&b[1]>=1&&o[2]>=1) || (b[0]>=1&&o[1]>=1&&b[2]>=1) || (o[0]>=1&&b[1]>=1&&b[2]>=1))
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}
1 Like
4

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[8];
	s3[0]="000";//picking all characters from 1st string.
	s3[1]="001";//picking first two characters from 1st string and last character from 2nd string
	s3[2]="010";//first and last character from 1st string and middle character from 2nd string
	s3[3]="011";//last two characters from 2nd string and 1st character from 1st string
	s3[4]="100";//only first character from 2nd string and rest from 1st string
	s3[5]="101";//ends characters from 2nd string and middle from 1st string
	s3[6]="110";//first two characters from 2nd string and last from 1st string
	s3[7]="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
5

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[0] and 'b' in lis[1] and 'b' in lis[2]) or ('b' in lis[0] and 'o' in lis[1] and 'b' in lis[2]) or ('b' in lis[0] and 'b' in lis[1] and 'o' in lis[2]):
        print('yes')
    else:
        print('no')
1 Like
6

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
7

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[0] == 'o' or t[0] == 'o') and (s[1] == 'b' or t[1] == 'b') and (s[2] == 'b' or t[2] == 'b'):
        result = True
    elif (s[1] == 'o' or t[1] == 'o') and (s[0] == 'b' or t[0] == 'b') and (s[2] == 'b' or t[2] == 'b'):
        result = True
    elif (s[2] == 'o' or t[2] == 'o') and (s[1] == 'b' or t[1] == 'b') and (s[0] == 'b' or t[0] == 'b'):
        result = True

    return result

WRONG CODE FOR C

int main()
{
    int c, i, ind;
    char a[3], b[3];

    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[0] || b[ind] == m[0] ){
                m[0] = '1'; 
            } else if ( a[ind] == m[1] || b[ind] == m[1] ){
                m[1] = '1'; 
            } else if ( a[ind] == m[2] || b[ind] == m[2] ){
                m[2] = '1'; 
            }
         }

         if ( m[0] == '1' && m[1] == '1' && m[2] == '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"
8

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[0]=='b'||arr[0]=='o')
						counter++;
				else 
					if(arr1[0]=='b'||arr1[0]=='o')
						counter++;
				
				//2
				if(arr[1]=='o'||arr[1]=='b')
						counter++;
				else 
					if(arr1[1]=='b'||arr1[1]=='o')
						counter++;
				
				//3
				if(arr[2]=='o'||arr[2]=='b')
						counter++;
				else 
					if(arr1[2]=='b'||arr1[2]=='o')
						counter++;
			
				if(counter==3)
					System.out.println("yes");
				else
					System.out.println("no");
				
			}
	}

}

why codechef compiler gives an error?

9

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");
	}
}

}

10

#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[3];
 char s2[3];
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[0]>=1 && b[1]>=1 &&o[2]>=1) || (o[0]>=1 && b[1]>=1 &&b[2]>=1)||(b[0]>=1 && o[1]>=1 && b[2]>=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;

}

11

Please Help ME the code is correct and giving output as well but not accepting the code ,please help me

12

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;
 }
}
13

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.

14

hey,

I am definite about the accuracy of my code, but I somewhat get awrong answer…
Can someone please help me?

this is the code:

t = int(input())

answers=[]

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:
    answers.append("yes")
else:
    answers.append("no")

for x in answers:
print(x)

1 Like
15

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

16

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

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.

17

Please Help ME the code is coorect and giving output aswell but not accepting the code

18

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;
}
19

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[3];
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;
}

20

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”)