HEADBOB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Piyush Kumar
Tester: Minako Kojima
Editorialist: Pawel Kacprzak

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Adhoc

PROBLEM:

Indian people use only gestures identified by ‘I’ and ‘N’. Non Indian people use only gestures identified by ‘Y’ and ‘N’. Given a string consisting of only ‘Y’, ‘N’ and ‘I’, decide if the string represents an Indian person, non Indian person or it is impossible to determine which one it represents. For each of these decision answers are: “INDIAN”, “NOT INDIAN” and “NOT SURE”.

QUICK EXPLANATION:

You need to decide if the string contains at least one ‘Y’ or at least one ‘I’ or neither of these letters is presented in the string.

EXPLANATION:

Problem statement ensures that it is impossible to have both ‘Y’ and ‘I’ in the string.

Based on that fact we can easily compute the answer.

If the string contains at least one ‘I’, then any other letter in is it ‘I’ or ‘N’, so the person represented by this string is Indian, hence the answer is “INDIAN”.

On the other hand, if the string contains at least one ‘Y’, then any other letter in it is ‘Y’ or ‘N’, so the person represented by this string is non Indian, hence the answer is “NOT INDIAN”.

Otherwise, if there is no ‘I’ and ‘Y’ in the string, each letter in it is ‘N’, so we cannot be sure if it represents Indian or non Indian, hence the answer is “NOT SURE”.

In order to do that, you can iterate over the string in a single loop:

Pseudo Code

	found = 0
	for(i = 0; i < s.length(); ++i)
             if (s[i] != 'N')
		if(s[i] == 'Y') 
		    res = "NOT INDIAN"
		else if (s[i] == 'I')
		    res = "INDIAN"
		found = 1
		break
	if(found==0)
	    res = "NOT SURE"

	print res        

Complexity

O(n) since we just need a single pass over the string

AUTHOR’S AND TESTER’S SOLUTIONS:

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

RELATED PROBLEMS:

2 Likes

found = 0
for(i = 0; i < s.length(); ++i)
if (s[i] != ‘N’)
if(s[i] == ‘Y’)
res = “NOT INDIAN”
else if (s[i] == ‘I’)
res = “INDIAN”
found = 1
break
if(found==0)
res = “NOT SURE”

print res

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

int main()
{
int t;
cin>>t;
char str[1005];
int len;
while(t–)
{
cin>>len;
cin>>str;
int k=0;
for(int k=0;k<len;k++)
hash[str[k]-‘A’]++;
if(hash[13]>0&&hash[8]>0&&hash[24]==0)
cout<<“INDIAN”<<endl;
else if(hash[13]>0&&hash[8]==0&&hash[24]>0)
cout<<“NOT INDIAN”<<endl;
else
cout<<“NOT SURE”<<endl;
}
}

Problem description is insufficient and has been described in very complex manner

5 Likes

I am not able to find error in my code. It seems to me correct, however I am getting WA. Anyone help please.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class HEADBOB {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(
                new InputStreamReader(
                        System.in));
        int t = Integer.parseInt(br.readLine());
        while(t-- > 0) {
            int size = Integer.parseInt(br.readLine());
            String s = br.readLine();
            boolean alln = false;
            boolean ind = false;
            for(int i = 0, j = s.length(); i < j ; ++i) {
                if(s.charAt(0) == 'N') {
                    alln = true;
                }
                if(alln && s.charAt(i) != 'N') {
                    alln = false;
                }
                if(s.charAt(i) == 'I') {
                    ind = true;
                    break;
                }

            }
            if(ind) {
                System.out.println("INDIAN");
                continue;
            }
            if(alln) {
                System.out.println("NOT SURE");
                continue;
            }
            System.out.println("NOT INDIAN");
        }
    }
}

@brij_raj you should keep

 
if(s.charAt(0) == 'N') {
     alln = true;
} 

outside the loop… because otherwise NNYNN test case fails

help ??

WHAT IS WRONG IN THIS CODE

t= int(input(""))
a=0
b=0
for i in range(0,t):
str=input("")
for j in range(0,len(str)):
a=0
b=0
if (str[j]==‘Y’) :

        a+=1
        
        break

    elif(str[j]=='I') :
       
        b+=1
        break
     


if(a==1):
    print('NOT INDIAN')

elif(b==1):
    print('INDIAN')

else:
    print('NOT SURE')

HELLO EVERYONE.
MY OUTPUT IS CORRECT BUT ON SUBMITTING IT SAYS WRONG. HELP ME WITH THIS.

for _ in range(int(raw_input())):
        s=""
        fore=0
        ind=0
        n=int(raw_input())
        s=raw_input()
        for j in range(len(s)):
            if s[j]=="N":
                fore=1 
                ind=1 
            elif s[j]=="Y":
                fore=1 
                ind=0
            elif s[j]=="I":
                fore=0
                ind=1 
            else:
                fore=2
                ind=2
        if fore==1 and ind==0:
            print "NOT INDIAN"
        elif fore==0 and ind==1:
            print "INDIAN"
        else:
            print "NOT SURE"

@Profile - l_returns - CodeChef Discuss
Thanks.

1 Like

welcome :slight_smile:

why does it shows TLE while it works on o(N)

#include
using namespace std;

int main() {
// your code goes here
int t,n;
char s[1000];
cin>>t;
while(t–){
cin>>n;
cin>>s;
int i,flag=0;
for(i=0;i<n;i++){
if(s[i]==‘I’)
{
flag=1;
cout<<“INDIAN”<<endl;
break;
}
else if(s[i]==‘Y’)
{
flag=1;
cout<<“NOT INDIAN”<<endl;
break;
}
}
if(flag!=1)
cout<<“NOT SURE”<<endl;
}
return 0;
}

Simpler code in Python Based on Editorial’s idea.

t = int(input())
indian = 'I'
yes = 'Y'
no = 'N'
while(t>0):
    n = int(input())
    # fg = 0
    s = input()
    if (indian in s):
        print('INDIAN')
    else:
        if((yes in s)):
           print('NOT INDIAN')
        else:
            print('NOT SURE')
            
    t -= 1

Simple code in python
for _ in range(int(input())):
n=int(input())
string=input()[:n]
print(“INDIAN”) if “I” in string else print(“NOT INDIAN”) if “Y” in string else print(“NOT SURE”)

#include

#include

#include

#include

#include

#include

#include

#include<unordered_set>

#include

#include<unordered_map>

#include<forward_list>

#include

#include

#include

#include

#include

#include

#include

#define nl cout<<"\n"

#define sp cout<<" "

#define ll long long

#define ld long double

#define rep(i,k,n) for(int i = k ; i < n ; i++ )

#define Rep(i,k,n) for(int i = k ; k<n ? in ; k<n ? i++ : i-- )

#define si(x) scanf("%d",&x)

#define sll(x) scanf("%lld",&x)

#define sf(x) scanf("%f",&x)

#define slf(x) scanf("%f",&x)

#define sc© scanf("%c",&c)

#define ss(s) scanf("%s",&s)

#define pi(x) printf("%d",&x)

#define pll(x) printf("%lld",&x)

#define pf(x) printf("%f",&x)

#define plf(x) printf("%f",&x)

#define pc© printf("%c",&c)

#define ps(s) printf("%s",&s)

#define vi vector

#define vc vector

#define pii pair<int,int>

#define vpii vector<pair<int,int> >

#define pb(x) push_back(x)

#define mp(x,y) make_pair{x,y}

#define F first

#define S second

#define srt(a,n) sort(a,a+n)

#define sortall(v) sort(v.begin(),v.end())

#define fa(a,i) fill(a,a+n,i)

#define mm(a,i) memset(a,i,sizeof(a))

#define tr(it,a,beg) for(auto it = a.begin() ; it != a.end() ; it++ )

#define etr(it,a,end) for(auto it = a.rbegin() ; it != a.rend() ; it++ )

#define PI 3.141592653589793116

#define fs(i) fixed<<setprecision(i)

#define s(i) setprecision(i)

#define FastIO ios_base :: sync_with_stdio (0) ; cin.tie(NULL) ;

using namespace std;

const long long INF = 1e18 ;

const int32_t M = 1e9+7 ;

const int32_t MM = 998244353 ;

int chech ( string str )

{

int i = 0 ;

bool in = 0 , nin = 0 , ns = 0 ;

while ( i < str.length() )

{

    if ( str[i] == 'N' && !ns )

    {

        ns = 1 ;

    }

    if ( str[i] == 'Y' && !nin )

    {

        nin = 1 ;

    }

    if ( str[i] == 'I' && !in )

    {

        in = 1 ;

    }

    i++ ;

}

if ( ns && in )

{

    return 0 ;

}

else if ( ns && nin )

{

    return 1 ;

} 

else

{

    return 2 ;

}

}

void solve ()

{

ll t = 0 ; cin>>t ;

ll n ;

string str ;

vector <string> v ;

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

{

    cin>>n>>str ;

    v.push_back(str) ;

}

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

{

    if ( chech (v[i]) == 0 )

    {

        cout<<"INDIAN\n" ;

    }

    else if ( chech (v[i]) == 1 )

    {

        cout<<"NON INDIAN\n" ;

    }

    else

    {

        cout<<"NOT SURE\n" ;

    }

}

}

int main()

{

FastIO

solve() ;

}

Whats wrong with my code
Anyone plz

#include

#include “bits/stdc++.h”

#define ll long long int

using namespace std;

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

ll T;

cin >> T;

while (T--)

{

    ll n;

    string s;

    cin >> n >> s;

    if (s.find('I') != string::npos)

    {

        cout << "INDIAN"

             << "\n";

    }

    else if (s.find('Y') != string::npos)

    {

        cout << "NOT INDIAN"

             << "\n";

    }

    else

    {

        cout << "NOT SURE"

             << "\n";

    }

}

return 0;

}

CAN ANY ONE PLS SAY Y IAM GETTING NZEC ERROR
??

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;
import java.util.Arrays;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
static Scanner sc= new Scanner(System.in);
public static void indian(){
int n=sc.nextInt();
char[]arr=new char[n];
for(int i=0;i<n;i++)arr[i]=sc.next().charAt(0);
int a= Arrays.binarySearch(arr,‘N’);
int b= Arrays.binarySearch(arr,‘I’);
int c= Arrays.binarySearch(arr,‘Y’);
if(a!=-1 && b!=-1)System.out.println(“INDIAN\n”);
else if(a!=-1 && c!=-1)System.out.println(“NOT INDIAN\n”);
else System.out.println(“NOT SURE\n”);

}
public static void main (String[] args) throws java.lang.Exception
{

int tc=sc.nextInt();
for(int i=0;i<tc;i++)indian();
}

}