- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**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.

- 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 ≤

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.

- Repetitively remove the last character from
- 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.

/* 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; } |