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.
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.
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.
For each test case, output a line in the following format:
Case #X: VWhere X is the case number (starting from 1) and V is the minimum number of seconds before war begins.
Time limit: 20 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100
The answer will never exceed 1018
1 ≤ the length of each line < 10
1 ≤ the length of each line < 61
3 11001001 cats zig
Case #1: 201 Case #2: 75 Case #3: 11
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
You know the position and velocity of each firefly at t = 0, and are only interested in
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 vzEach of these lines describes one firefly: (x, y, z) is its initial position at time t = 0, and (vx, vy, vz) is its velocity.
For each test case, output
Case #X: dmin tminwhere X is the test case number, starting from 1. Any answer with absolute or relative error of at most 10-5 will be accepted.
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
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
Case #1: 0.00000000 1.00000000 Case #2: 1.00000000 6.00000000 Case #3: 3.36340601 1.00000000
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
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.
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 Qwhere P is the number of prison cells and Q is the number of prisoners to be released.
For each test case, output one line in the format
Case #X: Cwhere X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.
Memory limit: 1 GB.
1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.
Time limit: 20 seconds.
1 ≤ P ≤ 100
1 ≤ Q ≤ 5
Time limit: 30 seconds.
1 ≤ P ≤ 10000
1 ≤ Q ≤ 100
2 8 1 3 20 3 3 6 14
Case #1: 7 Case #2: 35
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.
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
N = int(sys.stdin.readline().strip())
for qw in range(1, N+1):
print 'Case #%d:' % qw,
num = sys.stdin.readline().strip()
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!
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.
We did the calculations using vectors. It can also be carried out with 3-dimensional coordinates.
The exact formula of the distance from a point to a line in 3d space.
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;
}