SRM 708, D2, 500-Pointer (BuildingStrings)

James S. Plank

Mon Feb 20 15:40:35 EST 2017

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh. MD5 Hash: 295137ce2977040676e4984765f47cd2
answers.txt. MD5 Hash: 5d79a3ec0fef01d7d2549cef5097b8ee
Problem Given in Topcoder: February, 2017
Competitors who opened the problem: 347
Competitors who submitted a solution: 240
Number of correct solutions: 163
Accuracy (percentage correct vs those who opened): 47.0%
Average Correct Time: 33 minutes, 20 seconds.

In case Topcoder's servers are down

Here is a summary of the problem:

We calculate the "score" of a string to be the number of unique characters in the string, multiplied by its length.
We are given a number, K.
Our goal is to return a vector of strings whose scores add up to K.
Each string in the vector must be of maximum length 50.
The size of the vector must be at most 50.
The strings may only be composed of lowercase letters ('a' through 'z').
K will be between 1 and 50,000.

Examples

#0: K = 49.  One possible vector is {"little", "limak"}: 4*6+5*5 = 49.
#1: K = 15.  One possible vector is {"azz", "xyz"}.
#2: K = 704.  One possible vector is {"aaaaaaaaaa", "abcdefghijklmnopqrstuvwxyz", "aabbcc" }.
#3: K = 37521.  One possible vector is "aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy" 
    repeated 30 times, followed by { "abcd", "aa", "a", "a", "a" }.
#4: K = 1.  One possible vector is {"a"}.

Testing yourself

Compile the program Grader.cpp to the executable grader:

UNIX> g++ -o grader Grader.cpp

Now if you pipe the output of a.out into grader, it will test it to make sure it's correct.

Like the Cryptography Problem, I have a shell script tests.sh, that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

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:

If K is equal to zero, we're done -- we will return the return vector.
If K is less than or equal to 50, we will solve the problem by creating a string, which is a single letter repeated K times. We'll add that string to the return vector and return the vector.
Otherwise, we are going to find a string whose score is ≤ K, and we're going to add it to the return vector and subtract its score from K. We'll repeat this until we have one of the other cases above.

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:

Start with s as defined above and an empty return vector.
While K ≥ 1300, add s to the return vector and decrement K by 1300.
Now, while K > 50, do the following:
- Repetitively remove the last character from s while s's score is greater than K.
- Add s to the return vector, and decrement K by s's score.
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.
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;
}