SRM 708, D2, 500-Pointer (BuildingStrings)

James S. Plank

Mon Feb 20 15:40:35 EST 2017
First, if K is less than or equal to 50, you can solve the problem with a single string -- one composed of a single character repeated K times. We're going to use this fact as a base case to solve our problem. We are going to build a "return vector", which is a vector of strings that we will return as a solution to the problem. It will start as an empty vector. Then:

Now, how do we construct this last string? We'd like it to have a large score, because that way we'll be subtracting a lot from K, and hopefully we'll terminate in 50 iterations or less.

Here's the approach I took. Take a look at the following string:

s = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx"
This string has a maximum score of all strings 50 characters or fewer. The score is 1300. If this string is ≤ K, then this is a good string to start with, because it will subtract the maximum amount from K. Keep doing this until K is less than 1300. You'll note that K's maximum value is 50,000, which, when divided by 1300 is 38, so as long as you can solve smaller values of K in 12 iterations or fewer, you can solve the problem.

When K is less than 1300, what I did was repeatedly remove the last character from s, calculate its score, and see if I could use that. If you think about it, that reduces K's value to under 50 in almost every case. (I'm going to let you think about that on your own). I will assert that when K is less than 1300, you'll need a maximum of three strings whose scores sum to K if you do it in this way. Again, I'll let you prove that assertion on your own time. That gives you an approach to solve the problem. Let me summarize:

  1. Start with s as defined above and an empty return vector.
  2. While K ≥ 1300, add s to the return vector and decrement K by 1300.
  3. Now, while K > 50, do the following:
  4. If K ≤ 50 and K ≥ 1, then construct a string composed of a single character repeated K times, add it to the return vector and return the vector.
  5. If K is equal to zero, return the return vector.

My Solution

/* Topcoder SRM 708, D2 500-pointer
 * BuildingStrings
 * James S. Plank
 * Mon Feb 20 15:59:09 EST 2017
 */

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

typedef vector <string> SVec;

class BuildingStrings
{
    public:
        vector <string> findAny(int K);
};

vector <string> BuildingStrings::findAny(int K)
{
    int i, score;
    vector <string> rv;
    string s;

    /* Create the string s */

    for (i = 0; i < 50; i++) s.push_back('a' + i%26);

    /* Do steps 2 and 3 from the writeup -- while s's score is less than
       or equal to K, add it to the return vector and decrement the score 
       from K.  While s's score is greater than K, remove the last letter
       from s.  Do this until K <= 50. */

    while (K > 50) {
        score = (s.size() > 26) ? (26 * s.size()) : (s.size() * s.size());
        while (score <= K) {
            rv.push_back(s);
            K -= score;
        }
        s.pop_back();
    }

    /* Step 4: K is <= 50, so you can create a string of length K with
       a single character.  Its score will be K. */

    if (K > 0) {
        s.clear();
        s.resize(K, 'a');
        rv.push_back(s);
    }

    return rv;
}