SRM 741, D2, 250-Pointer (DigitStringDiv2)

James S. Plank

Originally: Fri Nov 2 14:14:14 EDT 2018
Last modified: Tue Jan 26 14:14:18 EST 2021

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: November, 2018
Competitors who opened the problem: 87
Competitors who submitted a solution: 81
Number of correct solutions: 51
Accuracy (percentage correct vs those who opened): 63.0%
Average Correct Time: 14:55

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a string S composed of the characters '0' through '9'.
You are also given a number X.
Return the number of substrings of S that don't start with zero, and, when converted to a number, are greater than X.
The topcoder constraints have S limited to 9 characters or less, and X less than 777,444,111. That's really lame. Instead, in my main() and tests, I'll limit S to 18 characters, and X to 777,444,111,777,444,111.
Two substrings are different when they have different starting indices and sizes. See example 3 below.

Examples

       S     X        Answer
-  ------   --        -------
0     "0"    1        0
1    "10"    9        1: Only "10"
2   "471"   47        2: "471" and "71"
3  "2222"   97        3: "2222" and both instances of "222"

Testing yourself

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

Think of this as a Big-O exercise -- if you implement the lamest solution you can think of, is it fast enough? My lame solution: generate all substrings of S using the substr() method of strings; if a substring doesn't start with '0', then convert it to a long long with a string stream, and compare with X.

What's the Big-O here? O(n²) substrings when the string is size n. Substring extraction and conversion is O(n). So the lame solution is O(n³). With n capped at 20, I think we're good to go -- we don't need to do anything smart.

I suspect that the reason that only 63% of the coders got this one is due to two reasons:

They didn't have the right loops.
They didn't convert to an integer correctly (the Topcoder problem didn't even require a long long).

There are a lot of loops that come to mind with a problem like this. Here are three:

for (i = 0; i < S.size(); i++) {
  for (j = 0; j < i; j++) {
    // Starting index is j.
    // Ending index is i.

for (i = 0; i < S.size(); i++) {
  for (j = i+1; j <= S.size(); j++) {
    // Starting index is i.
    // Ending index is j.

for (i = 0; i < S.size(); i++) {
  for (j = 1; i + j <= S.size(); j++) {
    // Starting index is i.
    // Size is j.

I'm going to suggest to you that the third is the best, largely because it then makes it easy to extract the substring with S.substr(i,j).

As far as converting to a long long, I'd use sscanf() from C stdio library. You don't need to error check, because S is guaranteed to hold digits and fit into a long long. In the topcoder version of the problem, atoi() will work, since it returns in int.

If you're not using sscanf(), then you'll need to use a stringstream.

The most efficient solution here is to use C entirely, and to enumerate the starting and ending indices. Then, you store the ending character, change it to the null character, call sscanf(), and change the ending character back. That avoids all the substring copying of the C++ solutions.

Regardless, the constraints here are so small that it doesn't matter.

I'll put all three solutions below:

Solution using C++ substrings and a stringstream

This is in Solution-Stringstream.cpp:

int DigitStringDiv2::count(string S, int X)
{
  int start, size;
  int total;
  string sub;
  long long val;
  istringstream ss;

  total = 0;

  /* Enumerate all starting positions and sizes. */

  for (start = 0; start < S.size(); start++) {
    if (S[start] != '0') {
      for (size = 1; start+size <= S.size(); size++) {
   
        /* Extract the substring and turn it into a number. */
  
        sub = S.substr(start, size);
        ss.clear();
        ss.str(sub);
        ss >> val;
  
        /* Add one to the total if the number is big enough. */
  
        if (val > X) total++;
      }
    }
  }

  /* Return the total. */

  return total;
}

Solution using sscanf and C++ substrings

Here you are still making a copy of the substring, but you are using sscanf() to do the conversion. This is in Solution-Sscanf.cpp. Only the difference from the previous solution is shown:

  /* Enumerate all starting positions and sizes. */

  for (start = 0; start < S.size(); start++) {
    if (S[start] != '0') {
      for (size = 1; start+size <= S.size(); size++) {
   
        /* Extract the substring and turn it into a number. */
  
        sub = S.substr(start, size);
        sscanf(sub.c_str(), "%lld", &val);
        if (val > X) total++;
      }
    }
  }

  /* Return the total. */

  return total;
}

Solution using C

Again, this is the most efficient, because you aren't making copies of the substrings: This is in Solution-C.cpp.

int DigitStringDiv2::count(string S, long long X)
{
  int i, j;
  int c;
  char *s;
  int total;
  long long val;

  /* Make a C-string copy of the string */

  s = strdup(S.c_str());
  total = 0;

  /* Enumerate all starting and ending indices: */

  for (i = 0; i < S.size(); i++) {
    if (s[i] != '0') {
      for (j = i+1; j <= S.size(); j++) {

        /* Copy the end character, set it to the null character, 
           convert with sscanf and restore the end character. */

        c = s[j];
        s[j] = '\0';
        sscanf(s+i, "%lld", &val);
        if (val > X) total++;
        s[j] = c;
      }
    }
  }

  /* Return the total.  Since you want to avoid memory leaks, you should free s too. */

  free(s);
  return total;
  
}