SRM 736, D1, 250-Pointer (DigitRotation)

James S. Plank

Tue Sep 11 16:10:51 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: August, 2018
Competitors who opened the problem: 237
Competitors who submitted a solution: 215
Number of correct solutions: 183
Accuracy (percentage correct vs those who opened): 77.2%
Average Correct Time: 20 minutes, 18 seconds.

If X has 500 characters, then the number of a, b and c combinations is 500 * 499 * 498, which equals 124,251,000. That's too big for topcoder, so you can't enumerate all a, b and c combinations.

However, you can enumerate any two of the three variables, as that number is 500 * 499 = 249,500. Let's focus on a and c. As always, it's best to start with an example, which will help us derive the general case. Suppose our string is "123456789". And suppose that a is 2 and c is 6. We can view our number as follows:

     12     3     456     7    89
      |     |      |      |     |
    digits  a  potential  c   digits
    before        b's         after
      a                         c

Now, let's take a look at all of the rotations involving a and c:

127356489     or:    12 7 356 4 89
127436589     or:    12 7 436 5 89
127453689     or:    12 7 453 6 89

Let's break the sum of these numbers into things that we can compute without needing a loop:

3 * 12 * 10⁷
3 * 7 * 10⁶
2 * 456 * 10³
111 * 3 * 10³
(4+5+6) * 10²
3 * 89 * 10⁰

I'm not going to turn this into a generalized set of equations -- I'm going to let you do that (especially if you are presenting this in CS494).

Now, we can compute each of these in constant time, if we precompute the following arrays:

power[i] is equal to 10ⁱ, modulo 998244353.
digits[i][j] is equal to X.substr(i,(j-i)), but treated as a number, modulo 998244353.
summation[i][j] is equal to the summation of X[i] through X[j], treated as digits of course, and not characters.
ones[i] is equal to 10⁰ + 10¹ + ... 10ⁱ, modulo 998244353.

Now you can compute everything above in constant time.