SIGMABATS - Editorial

Problem Link:

Fool’s Programming Contest

Sigma Bats

Author: Amul Agarwal

Testers: Ishaan Shah, Sanyam Shah, Sambasai Andem and Tejas Chaudhari

Editorialist: Keyur Chaudhari

DIFFICULTY:

HARD

EXPLANATION:

Hints

In this problem, we have to find out the letters in font “Arial” which when overturned (rotated by 180 degree upside-down). If the string is formed only from the letters found above, the expected output is “YES”, else “NO”.

Explanation of hints

Upside-down part

To reach this part of solution, we have to observe 2 critical hints:

  1. lives “overturned”
  2. “bat rules the rest” → We know that a “bat” at “rest” is upside-down
    We could use these 2 hints to reach the conclusion that we had to look at the letters upside down.

Extra information to avoid ambiguity

  1. We specified planet “Arial” to establish a standard font to avoid any ambiguity about the font to be considered.

  2. None of the test cases had any letter from the string “gimw” to avoid ambiguity since few could have been unsure about m and w being same upside-down. Thus adding any of these letters to your list or not adding would not make a difference.

If the input string consists of letters only from the letters of string “zxsqunbdplo”, then the output is “YES”, else “NO”.

Explanation for valid string

allowedCharacters = “zxsqunbdplo”
z → z
x → x
s → s
q → b
u → n
n → u
b → q
d → p
p → p
l → l
o → o


Tester's Solution
#include <bits/stdc++.h>

using namespace std;

int main()
{
	vector<bool> bat(26, false);
	bat['b' - 'a'] = true;
	bat['d' - 'a'] = true;
	bat['l' - 'a'] = true;
	bat['n' - 'a'] = true;
	bat['o' - 'a'] = true;
	bat['p' - 'a'] = true;
	bat['q' - 'a'] = true;
	bat['s' - 'a'] = true;
	bat['u' - 'a'] = true;
	bat['x' - 'a'] = true;
	bat['z' - 'a'] = true;
	int T;
	cin >> T;
	while(T--)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		bool flag = true;
		for(auto c: s)
		    flag &= bat[c - 'a'];
		if (flag)
			cout << "bat\n";
		else
			cout << "not bat\n";
	}
	return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

signed main()
{
    int testCases = 0;
    cin >> testCases;
    string allowed = "zxsqunbdplo";
    set<char> arial;
    for (auto ch : allowed)
        arial.insert(ch);
    while (testCases--) {
        int n;
        string a;
        cin >> n >> a;
        bool flag = true;
        for (auto ch : a) {
            if (arial.count(ch) == 0) {
                flag = false;
                break;
            }
        }
        if (flag)
            cout << "bat\n";
        else
            cout << "not bat\n";
    }
    return 0;
}