### 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:

• 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:

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:
• 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.
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 #include #include #include #include using namespace std; typedef vector SVec; class BuildingStrings { public: vector findAny(int K); }; vector BuildingStrings::findAny(int K) { int i, score; vector 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; } ```