# Google Code Jam Archive — Round 1C 2009 problems

## Overview

In the last match of Round 1, the competition was as exciting as the first two.

Interestingly, when the author created the first problem with a nice story, he did not notice that it actually was a mixture of flavors from the first problems (Multi-base Happiness and The Next Number) from the other two matches. The second problem turns out to be a simple exercise in geometry. And the third one, standard dynamic programming.

183 people enjoyed full scores, while 2337 contestants has at least one correct submission. As in Round 1B, solving all three small inputs correctly was not sufficient to advance.

We hope the problems were educational and pleasant, and all of you had fun.

Cast

Problem A. All Your Base Written and prepared by Bartholomew Furrow.

Problem B. Center of Mass Written by Xiaomin Chen. Prepared by Xiaomin Chen and Igor Naverniouk.

Problem C. Bribe the Prisoners Written by Nandini Seshadri. Prepared by John Dethridge.

Contest analysis presented by Bartholomew Furrow, Xiaomin Chen, and Marius Andrei.

Solutions and other problem preparation provided by Marius Andrei, Tomek Czajka, Derek Kisman, Petr Mitrichev, Fábio Moreira, and Daniel Rocha.

### Problem

In A.D. 2100, aliens came to Earth. They wrote a message in a cryptic language, and next to it they wrote a series of symbols. We've come to the conclusion that the symbols indicate a number: the number of seconds before war begins!

Unfortunately we have no idea what each symbol means. We've decided that each symbol indicates one digit, but we aren't sure what each digit means or what base the aliens are using. For example, if they wrote "ab2ac999", they could have meant "31536000" in base 10 -- exactly one year -- or they could have meant "12314555" in base 6 -- 398951 seconds, or about four and a half days. We are sure of three things: the number is positive; like us, the aliens will never start a number with a zero; and they aren't using unary (base 1).

Your job is to determine the minimum possible number of seconds before war begins.

### Input

The first line of input contains a single integer, T. T test cases follow. Each test case is a string on a line by itself. The line will contain only characters in the 'a' to 'z' and '0' to '9' ranges (with no spaces and no punctuation), representing the message the aliens left us. The test cases are independent, and can be in different bases with the symbols meaning different things.

### Output

For each test case, output a line in the following format:

`Case #X: V`
Where X is the case number (starting from 1) and V is the minimum number of seconds before war begins.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100
The answer will never exceed 1018

### Small dataset

1 ≤ the length of each line < 10

### Large dataset

1 ≤ the length of each line < 61

### Sample

Sample Input
```3
11001001
cats
zig
```
Sample Output
```Case #1: 201
Case #2: 75
Case #3: 11
```

## B. Center of Mass

### Problem

You are studying a swarm of N fireflies. Each firefly is moving in a straight line at a constant speed. You are standing at the center of the universe, at position (0, 0, 0). Each firefly has the same mass, and you want to know how close the center of the swarm will get to your location (the origin).

You know the position and velocity of each firefly at t = 0, and are only interested in t ≥ 0. The fireflies have constant velocity, and may pass freely through all of space, including each other and you. Let M(t) be the location of the center of mass of the N fireflies at time t. Let d(t) be the distance between your position and M(t) at time t. Find the minimum value of d(t), dmin, and the earliest time when d(t) = dmin, tmin.

### Input

The first line of input contains a single integer T, the number of test cases. Each test case starts with a line that contains an integer N, the number of fireflies, followed by N lines of the form

`x y z vx vy vz`
Each of these lines describes one firefly: (x, y, z) is its initial position at time t = 0, and (vx, vy, vz) is its velocity.

### Output

For each test case, output

`Case #X: dmin tmin`
where X is the test case number, starting from 1. Any answer with absolute or relative error of at most 10-5 will be accepted.

### Limits

Time limit: 20 seconds per test set.
Memory limit: 1 GB.
All the numbers in the input will be integers.
1 ≤ T ≤ 100
The values of x, y, z, vx, vy and vz will be between -5000 and 5000, inclusive.

3 ≤ N ≤ 10

3 ≤ N ≤ 500

### Sample

Sample Input
```3
3
3 0 -4 0 0 3
-3 -2 -1 3 0 0
-3 -1 2 0 3 0
3
-5 0 0 1 0 0
-7 0 0 1 0 0
-6 3 0 1 0 0
4
1 2 3 1 2 3
3 2 1 3 2 1
1 0 0 0 0 -1
0 10 0 0 -10 -1
```
Sample Output
```Case #1: 0.00000000 1.00000000
Case #2: 1.00000000 6.00000000
Case #3: 3.36340601 1.00000000
```

### Notes

Given N points (xi, yi, zi), their center of the mass is the point (xc, yc, zc), where:

```xc = (x1 + x2 + ... + xN) / N
yc = (y1 + y2 + ... + yN) / N
zc = (z1 + z2 + ... + zN) / N
```

## C. Bribe the Prisoners

### Problem

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

### Input

The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as

`P Q`
where P is the number of prison cells and Q is the number of prisoners to be released.
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.

### Output

For each test case, output one line in the format

`Case #X: C`
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.

### Limits

Memory limit: 1 GB.
1 ≤ N ≤ 100
QP
Each cell number is between 1 and P, inclusive.

### Small dataset

Time limit: 20 seconds.
1 ≤ P ≤ 100
1 ≤ Q ≤ 5

### Large dataset

Time limit: 30 seconds.
1 ≤ P ≤ 10000
1 ≤ Q ≤ 100

### Sample

Sample Input
```2
8 1
3
20 3
3 6 14
```
Sample Output
```Case #1: 7
Case #2: 35
```

### Note

In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.

## Analysis — A. All Your Base

``` IN A.D. 2101 WAR WAS BEGINNING ... CATS: HOW ARE YOU GENTLEMEN !! CATS: ALL YOUR BASE ARE BELONG TO US ```

This problem, of course, takes place in the halcyon days of A.D. 2100, before all our base became belong to Cats. It also firmly demonstrates that its author still lives in A.D. 2001.

In this problem our job is to read a series of symbols and interpret them as digits of a number in some base. In order to minimize the number, we'll want to use the smallest base possible. We can check how many different characters show up in the number; if that number of characters is k, then we can work in base `max(k,2)` (base 1 is not allowed). From there, it's simply a matter of assigning values from 0 to k to all of the characters. We can't start with a 0, so we should make the first digit a 1; and after that, simply assign the lowest number available to characters from left to right. In that way, "ab2ac999" becomes "10213444" in base 5, or 85499 seconds.

The following is a brief solution in Python:

```import sys

for qw in range(1, N+1):
print 'Case #%d:' % qw,

values = {num[0]: 1}
for c in num:
if c not in values:
sz = len(values)
if sz == 1:
values[c] = 0
else:
values[c] = sz
result = 0
base = max(len(values), 2)
for c in num:
result *= base
result += values[c]
print result
```

One final note: on our official Google Group, user Damien pointed out the following:

"The first example case in All Your Base implies the alien language uses a left-right notation. If that assumption is wrong and they actually used right-left you'd be 54 seconds late for the war: 11001001 binary = 201 decimal, but the reverse 10010011 is 147 decimal. Dangerous assumption to make don't you think? :-)"

I hate to say it, but he's right; even though 2219 people solved this problem, we may still be taken by surprise!

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

## Analysis — B. Center of Mass

Let Pi and Vi be the initial position and the velocity of the i-th firefly; its position at time t is given by Pi + tVi. Therefore, the center of mass at time t is

M(t) = ∑ (Pi + t Vi) / n = ∑ Pi / n + t ∑ Vi / n = Pave + t Vave,
where Pave (= M(0)) and Vave are the average initial position and average speed. Thus we show that the center of mass is also moving on a straight ray (a half line) with constant speed. (One special case is that the average speed could be 0, when the center of mass does not move at all.)

So, the problem is actually finding the closest distance from a point (the origin) to a ray, an elementary geometry problem. This is an easy exercise with many possible short solutions. One can use basic manipulations or calculus to derive the exact formula for the answers. One may also notice that the distance function d(t) is convex in t, thus use trinary search to find the best t. As always, we encourage the readers to download correct solutions from the scoreboard.

### Note

We did the calculations using vectors. It can also be carried out with 3-dimensional coordinates.

### Reference

The exact formula of the distance from a point to a line in 3d space.

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

## Analysis — C. Bribe the Prisoners

This problem is solved by dynamic programming. For each pair of cells a ≤ b, we want to compute dp[a][b], the best answer if we only have prisoners in cells from a to b, inclusive. Once we decide the location of c, the first prisoner between a and b to be released, we face the smaller sub-problems dp[a][c-1] and dp[c+1][b]. The final answer we want is dp[1][P].

It is clear we only need to solve those dp[a][b]'s where both a and b are either 1, P, or adjacent to a prisoner to be released. Thus the number of sub-problems we need to solve is just O(Q2).

Here is the annotated judge's solution.

```int p[200]; // prisoners to be released.
map<pair<int, int>, int> dp;

// Finds the minimum amount of gold needed,
// if we only consider the cells from a to b, inclusive.
int Solve(int a, int b) {
// First, look up the cache to see if the
// result is computed before.
pair<int, int> pr(a, b);
if(mp.find(pr) != mp.end()) return mp[pr];

// Start the computation.
int r = 0;
for(int i=0; i<Q; i++) {
if(p[i] >= a && p[i] <= b) {
int tmp = (b-a) + Solve(a, p[i]-1) + Solve(p[i]+1, b);
if (!r || tmp<r) r=tmp;
}
}
mp[pr]=r;
return r;
}
```

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