SRM 727, D1, 250-Pointer (OnlySanta)

James S. Plank

Tue Sep 18 17:11:37 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: January, 2018
Competitors who opened the problem: 150
Competitors who submitted a solution: 141
Number of correct solutions: 82
Accuracy (percentage correct vs those who opened): 54.7%
Average Correct Time: 26 minutes, 27 seconds.

This problem is all conceptual -- the programming is trivial. I'm not sure how to recommend that you solve this problem. Here was my thought process.

When is it ok to simply append "SANTA" to the end?
When is it not ok to simply append "SANTA"?
What can we do in that case?

See if you can use those questions to guide a solution. If not, come back here.

As it turns out, the only time that it's bad to append "SANTA" to the end is if the string contains the subsequence "SAT". In that case, then you can insert an "N" after the first "A" following the first "S". That's guaranteed to be ok -- since it's the first "A" following the first "S", it cannot complete a "SATAN". And then you append an "A" to the string. That certainly can't create a "SATAN" either.

Done:

Solution.cpp

/* Topcoder SRM 727, D1, 250-Pointer
   OnlySanta
   James S. Plank
   Tue Sep 18 18:05:37 EDT 2018
 */

#include <string>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class OnlySanta {
  public:
    string solve(string S);
};

string OnlySanta::solve(string S)
{
  int s, a, t;
  string rv;

  /* Find the first S.  If there's no "S", then appending SANTA will work. */

  s = S.find('S');
  if (s == string::npos) return S + "SANTA";

  /* Find the first A after the S.  
     If there's no subsequence "SA", then appending SANTA will work. */

  a = S.find('A', s);
  if (a == string::npos) return S + "SANTA";

  /* Find the first T after the SA.  
     If there's no subsequence "SAT", then appending SANTA will work. */

  t = S.find('T', a);
  if (t == string::npos) return S + "SANTA";

  /* Now that we've found the first "SAT" subsequence, put an "N" after the "A",
     and an "A" at the end: */

  rv = S.substr(0, a+1) + "N";
  rv += S.substr(a+1);
  rv += "A";
  return rv;
}