# BIO 2021 Q1a: Down Pat

I was practicing question 1a of the British Informatics Olympiad 2021 past paper.

A pat is a single letter or a string of letters which can be split into a left and right string (of at least 1 letter) where: each is the reverse of a pat; and all the letters in the left string are later in the alphabet than all the letters in the right string.
For example:

• BA is a pat as it splits into B and A, both of which are single letters and therefore pats, and B is alphabetically after A. AB is not a pat as the alphabetical rule would be broken;
• Similarly ED is a pat but DE is not;
• DEC is a pat as it splits into DE (whose reverse ED is a pat) and C.
• CEDAB splits into CED and AB, whose reverses are pats and C, E, and D are after A and B alphabetically.

Write a program that reads in two strings from a line, s1 then s2, each between 1 and 6 uppercase letters inclusive. You should output three lines, each containing a YES or NO indicating, in order, if s1 is a pat, if s2 is a pat, and if s1s2 (the combination of the two words) is a pat. You must get all three lines of output correct to score marks.

For this I wrote this code (I split it into different files so that I can reuse is_pat() for q1b and q1c):

q1.h

#include <string>

bool is_pat(std::string str);


q1.cc

#include <algorithm>

#include "q1.h"

const std::string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

bool is_pat(std::string str) {
if (str.length() == 1) return true;

std::string left, right;
for (int seperator = 1; seperator < str.length(); ++seperator) {
left = str.substr(0, seperator);
right = str.substr(seperator, str.length() - seperator);

char min_left = ALPHABET[ALPHABET.length() - 1];
for (char c : left) {
if (c < min_left) {
min_left = c;
}
}

char max_right = ALPHABET[0];
for (char c : right) {
if (c > max_right) {
max_right = c;
}
}

std::reverse(left.begin(), left.end());
std::reverse(right.begin(), right.end());

if (max_right < min_left) {
return is_pat(left) && is_pat(right);
}
}

return false;
}


q1a.cc

#include <iostream>

#include "q1.h"

inline std::string yes_or_no(bool val) {
return val ? "YES" : "NO";
}

int main() {
std::string s1, s2;
std::cin >> s1 >> s2;

std::cout << yes_or_no(is_pat(s1)) << std::endl;
std::cout << yes_or_no(is_pat(s2)) << std::endl;
std::cout << yes_or_no(is_pat(s1.append(s2))) << std::endl;

return 0;
}


Example run:

DE C
NO
YES
YES


(More test cases can be found in the mark scheme.)

I would be grateful to hear of any improvements that could be made to this code. (I am still a bit new to c++, so please point out if any bit of my code is not idiomatic.)

EDIT
@J_H highlighted a logic error in q1.cc (although this did not affect the final answer of any of the tests in the mark scheme). Please could all future reviews review the code with the lines:

if (max_right < min_left) {
return is_pat(left) && is_pat(right);
}


replaced by:

if (max_right < min_left && is_pat(left) && is_pat(right)) {
return true;
}


Please prefer conventional spelling: separator. Otherwise this reads just fine.

# save some work

        std::reverse(left.begin(), left.end());
std::reverse(right.begin(), right.end());

if (max_right < min_left) {


We could lazily defer those reversals by placing them within the if body.

# correctness

        if (max_right < min_left) {
return is_pat(left) && is_pat(right);


Are you sure you can eagerly return there? I mean, if one or the other conjunct fails, shouldn't we continue on with the loop, testing other candidate break points?

Rather than iterating, you might find that recursing here is a convenient way to backtrack.

Conversely, if you have a proof about feasible pats, you might like to offer a sketch of it here. Or comment on the loop variant which keeps bringing us closer to a solution.

# endl does a flush

You have a few endls which could be simple "\n" newlines.

• I suppose it was by chance that the final output for none of the test cases in the mark scheme was affected by the logic error? Commented Jul 30 at 2:41