Analysis: Secret Code by Brian Dean


This problem has a recursive solution where we check, for a string S, whether it could have been created according to each of our 4 rules from a shorter string S' (where we use recursion to then count the number of ways to get S'). Code is shown below (we subtract one at the end since otherwise we would count the base case solution where S is produced with zero applications of our rule, and we require one or more applications).

Since the input can be quite large (length at most 100), we should consider whether this approach will run quickly enough. If we start with a string of length N, then at worst, we will generate:
4 recursive calls on strings of length roughly N/2,
16 recursive calls on strings of length roughly N/4,
64 recursive calls on strings of length roughly N/8,
and so on. By the time we get to recursive calls on strings of length N/64 we will reach our base case, so by the pattern above we will see at most 46 = 212 = 4096 such calls, which is a very small number. We therefore expect this approach to run quite fast for strings of length 100 (if the input size was much larger, however, we would be in trouble).

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

int numways(string s) {
  int ans = 1, L = s.length();

  if (L % 2 == 0 || L == 1) return 1;

  // ABC -> AB + ABC
  if (s.substr(0,L/2) == s.substr(L/2,L/2))
    ans += numways(s.substr(L/2,L/2+1));
  
  // ABC -> ABC + AB
  if (s.substr(0,L/2) == s.substr(L/2+1,L/2))
    ans += numways(s.substr(0,L/2+1));
  
  // ABC -> BC + ABC
  if (s.substr(0,L/2) == s.substr(L/2+1,L/2))
    ans += numways(s.substr(L/2,L/2+1));

  // ABC -> ABC + BC
  if (s.substr(1,L/2) == s.substr(L/2+1,L/2))
    ans += numways(s.substr(0,L/2+1));

  return ans;
}

int main() {
  ifstream fin("scode.in");
  ofstream fout("scode.out");
  string s;

  fin >> s;
  fout << numways(s) - 1 << endl;

  return 0;
}