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
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
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 3D-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 3D-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.
4 1 9 011 12345
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 ≤ 109
0 ≤ Y ≤ 109
1 ≤ Z ≤ 109
0 ≤ A[i] < Z
1 ≤ m ≤ n ≤ 1000
1 ≤ m ≤ n ≤ 500000
2 5 5 0 0 5 1 2 1 2 3 6 2 2 1000000000 6 1 2
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;
}
}
As the problem clearly states, there are 3D-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
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
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