SRM 691, D2, 300-Pointer (Plusonegame)

James S. Plank

• Problem Statement.
• A main() with the examples compiled in.
• A skeleton that compiles with main.cpp.

• Problem Given in Topcoder: May, 2016
• Competitors who opened the problem: 430
• Competitors who submitted a solution: 360
• Number of correct solutions: 300
• Accuracy (percentage correct vs those who opened): 69.8%
• Average Correct Time: 24 minutes, 0 seconds.

Now, let's think about where the plus signs go with respect to the digits. If there are any zeros in the string, they are going to go first, before any plus signs. Why? Because if you put a plus sign before a zero, you have increased the penalty of each zero. If you put zero's first, then they incur no penalty.

Ok, so you put all of the zeros first. Now, what about ones? Well, if you have a plus sign, you should put one of them before the one's. Then the one's don't incur any penalty.

You keep doing this for every digit, until you run out of digits. At that point, you simply put all of the remaining plus signs at the end of the string, because plus signs at the end of the string don't penalize you.

Now, let's think of how best to program this one. I think that the cleanest way to do it is to have a vector with ten elements. Element i is the number of occurrences of the digit 'i'. Additionally, you need to count the plus signs. Then, you can construct the return string from these two pieces of data.

In example 0, the string is "1++". That means that your vector is {0,1,0,0,0,0,0,0,0,0}, and your count of plus signs is 2. Your answer will be "+1+". In example 4, your vector is {2,1,2,0,1,0,1,0,0,0}, and your count of plus signs is 19. Your answer will be "00+1+22++4++6+++++++++++++".

Here are all six examples, printing the vector and the number of plus signs, before calculating the return value:

UNIX> a.out 0
Digit_Counts: {0,1,0,0,0,0,0,0,0,0}
Plus_Signs:   2
+1+
UNIX> a.out 1
Digit_Counts: {0,0,0,0,1,1,0,0,0,1}
Plus_Signs:   0
459
UNIX> a.out 2
Digit_Counts: {0,0,0,0,0,0,0,0,0,0}
Plus_Signs:   6
++++++
UNIX> a.out 3
Digit_Counts: {0,0,1,0,0,0,0,0,0,0}
Plus_Signs:   6
++2++++
UNIX> a.out 4
Digit_Counts: {2,1,2,0,1,0,1,0,0,0}
Plus_Signs:   19
00+1+22++4++6+++++++++++++
UNIX> a.out 5
Digit_Counts: {0,3,0,0,0,0,0,0,0,5}
Plus_Signs:   2
+111+99999
UNIX> 

I have it commented below, too:

/* Topcoder SRM 691, D2, 300-Pointer
 * James S. Plank
 * November, 2016
 */

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

class Plusonegame
{
    public:
        string getorder(string s);
};

string Plusonegame::getorder(string s)
{
    vector <int> Digit_Counts;   /* This is the number of times each digit appears in the string */
    int Plus_Signs;              /* This is the number of times that the plus sign appears in the string */
    string rv;                   /* The return string. */
    int i, j;

    /* Initialize Plus_Signs and Digit_Counts to zero. */

    Plus_Signs = 0;
    Digit_Counts.resize(10, 0);

    /* Count the digits and the plus signs. */

    for (i = 0; i < s.size(); i++) {
        if (s[i] == '+') {
            Plus_Signs++;
        }
        else {
            Digit_Counts[s[i]-'0']++;
        }
    }

    /* Print out the digits and the plus signs. */

    printf("Digit_Counts: {%d", Digit_Counts[0]);
    for (i = 1; i < 10; i++) printf(",%d", Digit_Counts[i]);
    printf("}\n");
    printf("Plus_Signs:   %d\n", Plus_Signs);

    /* Create the return string from Digit_Counts and the number of plus signs. */

    for (i = 0; i < 10; i++) {
        for (j = 0; j < Digit_Counts[i]; j++) rv.push_back('0'+i);
        if (Plus_Signs > 0) {
            rv.push_back('+');
            Plus_Signs--;
        }
    }

    /* If there are still plus signs, put them at the end of the return string. */

    while (Plus_Signs > 0) {
        rv.push_back('+');
        Plus_Signs--;
    }

    return rv;
}