In this last sub-round of Google Code Jam 2008 Round 1, 2240 contestants solved at least one dataset, 17 among them got the perfect score of 100 points.

The first problem was the easiest one among the 9 Round 1 problems. It is interesting to note that there were contestants from the first page of the scoreboard who solved all of the datasets, except for A-large.

In the second problem, dynamic programming, a common topic in programming contests, made its first appearance in this tournament. We intended this to be an easy dynamic programming problem with a little trick in number theory. From the scoreboard we can tell that this is not a trivial problem.

The last problem, with a nice story, can be regarded as an exercise in data structures. In fact, the small dataset can be solved using standard dynamic programming. For the large dataset, one needs a way to speed it up. In this analysis we introduce an implementation that uses a binary indexed tree.

**Credits**

Problem A. *Text Messaging Outrage*
Written by Mohamed Eldawy. Prepared by Marius Andrei

Problem B. *Ugly Numbers*
Written and prepared Xiaomin Chen.

Problem C. *Increasing Speed Limits*
Written by Petr Mitrichev. Prepared by Mark Gordon.

Contest analysis presented by Cosmin Negruseri, Xiaomin Chen, and Mark Gordon.

Professor Loony, a dear friend of mine, stormed into my office. His face was red and he looked very angry. The first thing that came out of his mouth was "Damn those phone manufacturers. I was trying to send a text message, and it took me more than ten minutes to type a one-line message." I tried to calm him down. "But what is wrong? Why did it take you so long?" He continued, "Don't you see?! Their placement of the letters is so messed up? Why is 's' the 4th letter on its key? and 'e'? Why is it not the first letter on its key? I have to press '7' FOUR times to type an 's'? This is lunacy!"

"Calm down, my friend," I said, "This scheme has been in use for so long, even before text messaging was invented. They had to keep it that way."

"That's not an excuse," his face growing redder and redder. "It is time to change all this. It was a stupid idea to start with. And while we are at it, how come they only put letters on 8 keys? Why not use all 12? And why do they have to be consecutive?"

"Umm... I... don't... know," I replied.

"Ok, that's it. Those people are clearly incompetent. I am sure someone can come up with a better scheme."

He was one of *those* people, I could see. People who complain about the
problem, but never actually try to solve it.

In this problem, you are required to come up with the best letter placement of keys to minimize the number of key presses required to type a message. You will be given the number of keys, the maximum number of letters we can put on every key, the total number of letters in the alphabet, and the frequency of every letter in the message. Letters can be placed anywhere on the keys and in any order. Each letter can only appear on one key. Also, the alphabet can have more than 26 letters (it is not English).

For reference, the current phone keypad looks like this

key 2: abc key 3: def key 4: ghi key 5: jkl key 6: mno key 7: pqrs key 8: tuv key 9: wxyz

The first press of a key types the first letter. Each subsequent press advances to the next letter. For example, to type the word "snow", you need to press "7" four times, followed by "6" twice, followed by "6" three times, followed by "9" once. The total number of key presses is 10.

The first line in the input file contains the number of test cases **N**.
This is followed by **N** cases. Each case consists of two lines. On the
first line we have the maximum number of letters to place on a key (**P**),
the number of keys available (**K**) and the number of letters in our
alphabet (**L**) all separated by single spaces. The second line has
**L** non-negative integers. Each number represents the frequency of a
certain letter. The first number is how many times the first letter is used,
the second number is how many times the second letter is used, and so on.

For each case, you should output the following

Case #x: [minimum number of keypad presses]

indicating the number of keypad presses to type the message for the optimal layout.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

**P** * **K** ≥ **L**

0 ≤ The frequency of each letter ≤ 1000000

1 ≤ **N** ≤ 10

1 ≤ **P** ≤ 10

1 ≤ **K** ≤ 12

1 ≤ **L** ≤ 100

1 ≤ **N** ≤ 100

1 ≤ **P** ≤ 1 000

1 ≤ **K** ≤ 1 000

1 ≤ **L** ≤ 1 000

Sample Input

2 3 2 6 8 2 5 2 4 9 3 9 26 1 1 1 100 100 1 1 1 1 1 1 1 1 1 1 1 1 10 11 11 11 11 1 1 1 100

Sample Output

Case #1: 47 Case #2: 397

Once upon a time in a strange situation, people called a number *ugly* if
it was divisible by any of the one-digit primes (2, 3, 5 or 7). Thus, 14 is
ugly, but 13 is fine. 39 is ugly, but 121 is not. Note that 0 is ugly. Also
note that negative numbers can also be ugly; -14 and -39 are examples of such
numbers.

One day on your free time, you are gazing at a string of digits, something like:

123456

You are amused by how many possibilities there are if you are allowed to
insert *plus* or *minus* signs between the digits. For example you
can make

1 + 234 - 5 + 6 = 236

which is ugly. Or

123 + 4 - 56 = 71

which is not ugly.

It is easy to count the number of different ways you can play with the digits:
Between each two adjacent digits you may choose put a plus sign, a minus sign,
or nothing. Therefore, if you start with D digits there are 3^{D-1}
expressions you can make.

Note that it is fine to have leading zeros for a number. If the string is "01023", then "01023", "0+1-02+3" and "01-023" are legal expressions.

Your task is simple: Among the 3^{D-1} expressions, count how many of
them evaluate to an ugly number.

The first line of the input file contains the number of cases, **N**. Each
test case will be a single line containing a non-empty string of decimal
digits.

For each test case, you should output a line

Case #X:Y

where **X** is the case number, starting from 1, and **Y** is the
number of expressions that evaluate to an ugly number.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

0 ≤ **N** ≤ 100.

The string in each test case will be non-empty and will contain only
characters '0' through '9'.

Each string is no more than 13 characters long.

Each string is no more than 40 characters long.

Sample Input

4 1 9 011 12345

Sample Output

Case #1: 0 Case #2: 1 Case #3: 6 Case #4: 64

You were driving along a highway when you got caught by the road police for speeding. It turns out that they've been following you, and they were amazed by the fact that you were accelerating the whole time without using the brakes! And now you desperately need an excuse to explain that.

You've decided that it would be reasonable to say "all the speed limit signs I saw were in increasing order, that's why I've been accelerating". The police officer laughs in reply, and tells you all the signs that are placed along the segment of highway you drove, and says that's unlikely that you were so lucky just to see some part of these signs that were in increasing order.

Now you need to estimate that likelihood, or, in other words, find out how many different subsequences of the given sequence are strictly increasing. The empty subsequence does not count since that would imply you didn't look at any speed limits signs at all!

For example, (1, 2, 5) is an increasing subsequence of (1, 4, 2, 3, 5, 5), and we count it twice because there are two ways to select (1, 2, 5) from the list.

The first line of input gives the number of cases, **N**. **N** test
cases follow. The first line of each case contains **n**, **m**,
**X**, **Y** and **Z** each separated by a space. **n** will be
the length of the sequence of speed limits. **m** will be the length of the
generating array A. The next **m** lines will contain the **m** elements
of A, one integer per line (from A[0] to A[**m**-1]).

Using A, **X**, **Y** and **Z**, the following pseudocode will
*print* the speed limit sequence in order. mod indicates the remainder
operation.

```
for i = 0 to n-1
```*print* A[i mod **m**]
A[i mod **m**] = (**X** * A[i mod **m**] + **Y** * (i + 1)) mod **Z**

Note: The way that the input is generated has nothing to do with the intended solution and exists solely to keep the size of the input files low.

For each test case you should output one line containing "Case #**T**:
**S**" (quotes for clarity) where **T** is the number of the test case
and **S** is the number of non-empty increasing subsequences mod
1_{ }000_{ }000_{ }007.

Time limit: 60 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 20

1 ≤ **m** ≤ 100

0 ≤ **X** ≤ 10^{9}

0 ≤ **Y** ≤ 10^{9}

1 ≤ **Z** ≤ 10^{9}

0 ≤ **A[i]** < **Z**

1 ≤ **m** ≤ **n** ≤ 1000

1 ≤ **m** ≤ **n** ≤ 500000

Sample Input

2 5 5 0 0 5 1 2 1 2 3 6 2 2 1000000000 6 1 2

Sample Output

Case #1: 15 Case #2: 13

The sequence of speed limit signs for case 2 should be 1, 2, 0, 0, 0, 4.

This was the one of the easiest problems of Round 1. We simply need to fill
the cell phone keyboard greedily. We put the **K** most frequent letters in
the first positions of the **K** keys, the next **K** most frequent
letters in the second positions, and so on. Any optimal solution will have
this structure because if it does not, then it can be improved by swapping a
more frequent character from a higher indexed position of some key with a less
frequent character from a lower indexed position, thus decreasing the number
of key presses.

Here is code that implements this solution:

long long A[1000]; int main() { int N; cin >> N; for(int t = 1; t <= N; t++) { long long result = 0; int P, K, L; cin >> P >> K >> L; for(int i = 0; i < L; i++) cin >> A[i]; sort(A, A+L); reverse(A, A+L); for(int i = 0; i < L; i++) result += (1 + i / K) * A[i]; cout << "Case #" << t << ": " << result << endl; } }

Test Data

We recommend that you practice debugging solutions without looking at the test data.

As the problem clearly states, there are 3^{D-1} ways you need to
consider. When **D** is no larger than 13, as it is in the small dataset,
one may simply generate all the possible combinations and calculate each of
them. However, with **D** as large as 40, brute force is clearly too slow.

As you might expect from a programming contest, the magic term is dynamic programming. This is the first problem in Google Code Jam 2008 that falls into the standard dynamic programming (DP) category; and one can be assured that there are more to come.

As in any DP problem, the first task is to structure the problem in a good way so there are not too many numbers to compute, and each number can be computed easily from previous ones. If you observe the solutions of the top scorers in this sub-round, you will see, although their algorithms vary to some degre, they all contain the following magic number

2 · 3 · 5 · 7 = 210.

Let us say we have two numbers, x and y, knowing the ugliness of x and y is
not enough to decide whether

For those who prefer mathematical terms, we are using the
Chinese remainder theorem.
Our problem can be viewed as arithmetics on the cyclic group
_{210}, +)

So, let us outline the most central step of our dynamic programming solution. We want to compute

dyn[i][x] := number of ways we get an expression evaluating to x (mod 210) if we only consider the first i characters of the string. (*)

So, we have only 40·210 numbers to consider. For each dyn[i][x], we try
all possible positions for inserting the last '+' or '-' sign. If the last
sign was a '+' before position j (j<i), and the number formed by digits
from position j to position i is d, then we want to know

Here is a masterful implementation from our own Derek Kisman. His complete C++ solution follows the idea above, with a little twist and some nice programming tricks.

#define MOD (2*3*5*7) string s; long long dyn[41][MOD]; main() { int N, prob=1; for (cin >> N; N--;) { cin >> s; memset(dyn, 0, sizeof(dyn)); dyn[0][0] = 1; for (int i = 0; i < s.size(); i++) for (int sgn = (i==0) ? 1 : -1; sgn <= 1; sgn += 2) { int cur = 0; for (int j = i; j < s.size(); j++) { cur = (cur*10 + s[j]-'0')%MOD; for (int x = 0; x < MOD; x++) dyn[j+1][(x+sgn*cur+MOD)%MOD] += dyn[i][x]; } } long long ret = 0; for (int x = 0; x < MOD; x++) if (x%2 == 0 || x%3 == 0 || x%5 == 0 || x%7 == 0) ret += dyn[s.size()][x]; cout << "Case #" << prob++ << ": " << ret << endl; } }

Dynamic programming - Chinese remainder theorem

Test Data

We recommend that you practice debugging solutions without looking at the test data.

This was the hard problem for round 1C, with 398 people solving the small i/o set and 49 people solving the large i/o set during the contest.

The problem asks us to count the number of strictly increasing subsequences of the original sequence. This lends itself nicely to a dynamic programming solution for the small input.

Let f(x) be the number of strictly increasing subsequences that start with node x and S[x] be the value of the sequence at position x. At any node x we can either end the subsequence at x or connect it to any of the following nodes that are strictly greater than node x. Therefore, you could do something like this to find out how many strictly increasing subsequences start at each index.

```
f(x) = 1
for i = n to 1
f(i) = 1
for j = i + 1 to n
if S[i] < S[j]
f(i) = f(i) + f(j)
```

After doing that, solving the original problem is just a matter of summing the number of ways you make a strictly increasing subsequence starting at each position.

The key to solving the large i/o set is to realize we can make the inner loop
run much faster. What we really want to do is sum all of the previous f(j)s
for which

The first two types of trees are fairly easy to implement although they add a
complication since they use an amount of memory proportional to the maximum
value in the sequence. Fortunately this can be worked around by normalizing
S to contain only values between 0 and n-1 without changing the the

Here is an implementation of these ideas in C++.

```
#define MAXN (1<<20)
int sum_bit[MAXN];
int sum_bit_get(int x)
{
int ret = 0;
for(int i = x | MAXN; i < 2 * MAXN; i += i & -i)
ret = (ret + sum_bit[i ^ MAXN]) % 1000000007;
return ret;
}
void sum_bit_add(int x, int v)
{
for(int i = x | MAXN; i; i &= i - 1)
sum_bit[i ^ MAXN] = (sum_bit[i ^ MAXN] + v) % 1000000007;
}
int S[1000000];
int S2[1000000];
int main()
{
int T; cin >> T;
long long X, Y, Z, A[100];
for(int t = 1; t <= T; t++) {
int n, m; cin >> n >> m >> X >> Y >> Z;
for(int i = 0; i < m; i++) cin >> A[i];
// Generate S
for(int i = 0; i < n; i++) {
S[i] = A[i % m];
A[i % m] = (X * A[i % m] + Y * (i + 1)) % Z;
}
// Normalize S
memcpy(S2, S, sizeof(S));
sort(S2, S2+n);
for(int i = 0; i < n; i++)
S[i] = lower_bound(S2, S2+n, S[i]) - S2;
// Calculate f(i) and sum them in to result.
int result = 0;
memset(sum_bit, 0, sizeof(sum_bit));
for(int i = n - 1; i >= 0; i--) {
int add = 1 + sum_bit_get(S[i] + 1);
sum_bit_add(S[i], add);
result = (result + add) % 1000000007;
}
cout << "Case #" << t << ": " << result << endl;
}
return 0;
}
```

In addition to trees, there was a "hacker's"

More Information:

Binary Indexed Tree

Test Data

We recommend that you practice debugging solutions without looking at the test data.