SRM 736, D1, 250-Pointer (DigitRotation)

James S. Plank

Tue Sep 11 16:10:51 EDT 2018

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

Now you can compute everything above in constant time.