Round 1B had easier problems, but it was not easy to qualify from. ACRush, the Code Jam 2008 Champion, finished all the problems in less than 45 minutes. Solving problem B alone was not enough to qualify.

Problem A was not the favorite choice of the contestants, probably because of the long statement, although it was mostly about parsing. Problem B was easier to implement, but it required a little more thinking. Problem C needed some optimizations and was the last one to be implemented by most of the contestants.

63 people got 100 points, just one less than Round 1A. 3 of them submitted in the last minute.

Congratulations to all the people that qualified for Round 2!

Cast

Problem A. *Decision Tree* Written by Pavel Nalivaiko. Prepared by Frank Chu and Igor Naverniouk.

Problem B. *The Next Number* Written by John Dethridge. Prepared by Frank Chu and Marius Andrei.

Problem C. *Square Math* Written by Junbin Teng. Prepared by Xiaomin Chen and Daniel Rocha.

Contest analysis presented by Marius Andrei, Igor Naverniouk, and Xiaomin Chen.

Solutions and other problem preparation provided by Tomek Czajka, Pablo Dal Lago, Ante Derek, Derek Kisman, Petr Mitrichev, and Cosmin Negruseri.

Decision trees -- in particular, a type called classification trees --
are data structures that are used to classify *items* into *categories*
using *features* of those items. For example, each animal is either
"cute" or not. For any given animal, we can decide whether it is cute
by looking at the animal's features and using the following decision tree.

(0.2 furry (0.81 fast (0.3) (0.2) ) (0.1 fishy (0.3 freshwater (0.01) (0.01) ) (0.1) ) )

A decision tree is defined recursively. It always has a root node and a weight. It also, optionally, has a feature name and two sub-trees, which are themselves decision trees.

More formally, a decision tree is defined using the following grammar.

The part inside the square brackets,tree::=(weight[featuretreetree])weightis a real number between 0 and 1, inclusivefeatureis a string of 1 or more lower case English letters

To figure out how likely the animal is to be cute, we start at the root
of the tree with probability *p* set to 1. At each node, we multiply
*p* by the weight of the node. If the node is a leaf (has no sub-trees),
then we stop, and the value of *p* is the probability that our animal
is cute. Otherwise, we look at the feature associated with the node. If our
animal has this feature, we move down into the first sub-tree and continue
recursively. If it does not have this feature, then we move down into the
second sub-tree and continue in the same way.

For example, a beaver is an animal that has two features: *furry* and
*freshwater*. We start at the root with *p* equal to 1. We multiply
*p* by 0.2, the weight of the root and move into the first sub-tree
because the beaver has the *furry* feature. There, we multiply *p*
by 0.81, which makes *p* equal to 0.162. From there we move further down
into the second sub-tree because the beaver does not have the *fast* feature.
Finally, we multiply *p* by 0.2 and end up with 0.0324 -- the probability
that the beaver is cute.

You will be given a decision tree and a list of animals with their features. For each item, you need to return the probability that the animal is cute.

The first line of input contains a single integer, **N**, the number of
test cases. **N** test cases follow.

Each test case description will start with a line that contains an integer
**L** -- the number of lines that describe a decision tree. The next **L**
lines will contain a decision tree in the format described above. The line
after that will contain **A** -- the number of animals. The next **A**
lines will each contain the description of one animal in the following format.

animalnfeature_{1}feature_{2}...feature_{n}

For each test case, output one line containing "Case #**x**:"
followed by exactly **A** lines, one per animal, in the same order as they
appear in the input. Each line should contain the probability that the animal
is cute. Answers that are precise to within an absolute or relative error of
10^{-6} will be considered correct.

Time limit: 30 seconds per test set.

Memory limit: 1 GB.

1 ≤ **N** ≤ 100

All weights will be between 0 and 1, inclusive.

All weights will consist of only digits with at most one decimal point.

The weights will not start or end with a decimal point.

The weights will not have more than one 0 before a decimal point.

All animals and features will consist of between 1 and 10 lower case
English letters.

All animal names within a test case will be distinct.

All feature names for a single animal will be distinct.

Each of the **L** lines in a decision tree definition will have at most 80
characters, not including the endlines.

1 ≤ **L** ≤ 10

1 ≤ **A** ≤ 10

0 ≤ **n** ≤ 5

1 ≤ **L** ≤ 100

1 ≤ **A** ≤ 100

0 ≤ **n** ≤ 100

Sample Input

1 3 (0.5 cool ( 1.000) (0.5 )) 2 anteater 1 cool cockroach 0

Sample Output

Case #1: 0.5000000 0.2500000

You are writing out a list of numbers. Your list contains all numbers with exactly **D _{i}** digits in its decimal representation which are equal to

For example, you might be writing every number with two '1's and one '5'. Your list would begin 115, 151, 511, 1015, 1051.

Given **N**, the last number you wrote, compute what the next number in the list will be.

The first line of input contains an integer **T**, the number of test cases in the input. **T** lines follow, one for each test case, each containing a single integer **N**.

For each test case, output

Case #whereX:K

Memory limit: 1 GB.

Time limit: 20 seconds.

1 ≤ T ≤ 50

1 ≤ N ≤ 10^{6}

Time limit: 30 seconds.

1 ≤ T ≤ 500

1 ≤ N ≤ 10^{20}

Sample Input

3 115 1051 6233

Sample Output

Case #1: 151 Case #2: 1105 Case #3: 6323

Say we have a square that has **W** cells on each side and, therefore, **W**^{2} cells total. Let's go further and fill each cell with one of the following:

- A digit from 0 to 9;
- The addition sign (+);
- The subtraction sign (-).

Square Math is the name of a puzzle where, given an arithmetic square, we start from any numeric cell and move either horizontally or vertically a cell at a time, finally ending in a numerical cell. The mathematical expression we get from the traversal is evaluated to get a single value. For example:

2+3 +4- 1+0

The above is a valid arithmetic square of size **W** = 3. If we start from "2", move horizontally right, then vertically down, we'll get "2+4", which gives a value of "6". If we further move horizontally right, then vertically up, we'll get "2+4-3", which is equal to "3".

In Square Math, there is no limit to how many times you can use a particular cell. It is perfectly legal to move from a cell to its neighbor, then back to the original cell. Given an arithmetic square and a list of queries, your task is to find a Square Math expression which evaluates to each query.

For each test case, begin output with "Case #**X**:" on a line by itself, where **X** is the test case number, starting from 1. Then, for each query within the test case, print the Square Math expression which evaluates to the query on a line by itself.

In the case where there are multiple possible Square Math expressions, print the one that is shortest. If there is still a tie, print the lexicographically smallest expression. Remember that '+' is lexicographically smaller than '-'.

Memory limit: 1 GB.

1 ≤ **T** ≤ 60

Time limit: 30 seconds.

2 ≤ **W** ≤ 10

1 ≤ **Q** ≤ 20

1 ≤ each query ≤ 50

Time limit: 60 seconds.

2 ≤ **W** ≤ 20

1 ≤ **Q** ≤ 50

1 ≤ each query ≤ 250

Sample Input

2 5 3 2+1-2 +3-4+ 5+2+1 -4-0- 9+5+1 20 30 40 3 2 2+1 +4+ 5+1 2 20

Sample Output

Case #1: 1+5+5+9 3+4+5+9+9 4+9+9+9+9 Case #2: 2 5+5+5+5

The hard part here was parsing the tree. An easy way to do this is by using a technique called *recursive descent*. The tree grammar is defined recursively, so it makes sense to parse it recursively, too. Here is a solution in Python.

import re import sys inp = sys.stdin tokens = None ti = -1 def ReadInts(): """Reads several space-separated integers on a line. """ return tuple(map(int, inp.readline().strip().split(" "))) def NextToken(): """Consumes the next token from 'tokens'. """ global ti assert 0 <= ti < len(tokens) ti += 1 return tokens[ti - 1] def ParseNode(): """Parses from 'tokens' and returns a tree node. """ global ti assert NextToken() == "(" node = {"weight": float(NextToken())} tok = NextToken() if tok == ")": return node node["feature"] = tok node[True] = ParseNode() node[False] = ParseNode() assert NextToken() == ")" return node def ParseTree(s): """Initializes 'tokens' and 'ti' and parses a tree. """ global tokens global ti s = re.compile(r"\(").sub(" ( ", s) s = re.compile(r"\)").sub(" ) ", s) s = re.compile(r"[ \n]+").sub(" ", " %s " % s) tokens = s[1:-1].split(" ") ti = 0 return ParseNode() def Evaluate(tree, features): ans = tree["weight"] if "feature" in tree: ans *= Evaluate(tree[tree["feature"] in features], features) return ans if __name__ == "__main__": N = ReadInts()[0] for prob in xrange(1, N + 1): n_lines = ReadInts()[0] lines = [inp.readline() for _ in xrange(n_lines)] tree = ParseTree(" ".join(lines)) n_queries = ReadInts()[0] print "Case #%d:" % prob for _ in xrange(n_queries): features = set(inp.readline().strip().split(" ")[2:]) print "%.7f" % Evaluate(tree, features)

For each test case, we read the 'n_lines' lines containing the tree definition, we glue them together using spaces and pass the resulting string to ParseTree().

In ParseTree(), we do some "massaging" to make the string easier to parse. First, we put spaces around each parenthesis by using two simple regular expressions. Next, we replace each sequence of whitespace characters by a single space and make sure there is always exactly one space character at the beginning and the end of the input. Finally, we strip off the leading and trailing spaces and split the rest into tokens.

The ParseNode() function does the rest. It uses the NextToken() function to read one token at a time from the 'tokens' list and returns a simple dictionary representation of a tree node.

Once we have the tree as a dictionary, we then use Evaluate() to do a tree traversal from the root to a leaf and compute the answer for each input animal.

A number of contestants have noticed that there is an even easier way to parse the tree. Most dynamic, interpreted languages give you access to their built-in parser, and by manipulating the input a little bit, it is possible to use make the language's interpreter do the parsing for you! This means using "eval" in JavaScript or Python, or "read" in Lisp. Check out some of the shortest solutions at 1b-a.pastebin.com/d4631e678.

Test Data

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

Let **x** be our input. We want to find the next number **y**. We denote L(*s*) to be the length of *s*, i.e., the number of digits in *s*.

*Case 1*. If all the digits in *x* are non-increasing, for example *x* = 776432100, then *x* is already the biggest one among the numbers in the list with L(*x*) digits. The next number, *y*, must have one more digit, that is, one more 0. Actually *y* must be the smallest one with L(*x*)+1 digits. To get *y*, we put the smallest non-zero digit in front, and all the other digits are put in non-decreasing order.

*Case 2*. Otherwise, *x* can be written as the concatenation *x* = *a**b*, where *b* is the longest non-increasing suffix of *x*, so *d*, the last digit of *a* is smaller than the first digit of *b*. Let *d'* be the smallest among all the digits in *b* that are bigger than *d*.

Because *b* is non-increasing, *x* is the biggest number among those who has L(x) digits and starts with prefix *a*. The first L(*a*) digits of *y* must be bigger than *a*. The smallest we can do is to replace *d* with *d'*, and then for the rest digits, we arrange them in non-decreasing order.

Let us do another example. *x* = 134266530. Then *a* = 1342, *b* = 66530, *d* = 2, and *d'* = 3. The next number is *y* = 134302566.

In fact, we can unify the two cases above. Since the number of 0's is not restricted, we can just imagine there is one more 0 in the beginning of *x*, thus Case 1 is reduced to Case 2.

The above described is actually exactly the procedure to get the next permutation of a finite sequence in certain languages. Below is a solution that is essentially one line in C++. From the author:

deque<char> f; ... f.push_front('0'); next_permutation(f.begin(), f.end()); if (f.front() == '0') f.pop_front();

Test Data

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

The problem would be a lot easier if there were only plus signs used. With the presence of the negative signs, a valid expression might get to a large value in the middle, then decrease back to the value we are looking for. Will that be the shortest answer for a certain query at all?

First of all, let us denote a non-zero digit in the square *pos* if it has at least one neighbor that is a plus sign; call it *neg* if it has one minus sign as its neighbor. A digit can be both pos and neg. We assume there are both pos digits and neg digits in the square. Let **q** be the value we are looking for.

Let g be the gcd (greatest common divisor) of all the digits in the square. If g is not 1, in order to find a solution for q, it must be a multiple of g. Dividing everything by g, we may assume from now on that the gcd of all the numbers in the square is 1. The situation is further simplified when all our numbers are between 0 and 9 -- in this case, the above implies that there must be two digits, **a** and **b**, in the square, such that gcd(a, b) = 1.

*Case 1*. **a** is pos and **b** is neg. Take any shortest path **P** from **a** to **b** in the square. Let **q'** be the value of this path. q' is between [-200, 200]. Let t = q - q'. We prove the case t ≥ 0; the other case is similar and left to the readers.

Since gcd(a, b)=1, one of the numbers t, t+b, t+2b, ..., t+(a-1)b is a multiple of **a**. This means we can find non-negative numbers x and y such that ax - by = t, where y < a (therefore x < t/a + b). We start from **a**, since it is a positive digit, we use the plus sign to repeat at **a** x times, then follow **P**. After reaching **b**, we use the minus sign to repeat y times. The path just described evaluates to the query **q**.

*Case 2*. Both **a** and **b** are pos, there is a neg digit **c**. If **c** is co-prime with either **a** or **b**, we handle it as Case 1. Otherwise c has to be 6.

Pick any shortest path **P** that connects **a**, **b**, and **c**. Suppose it evaluates to q'. Pick a non-negative z such that q - q' + 6z ≥ ab - a - b + 1. We use a basic fact in number theory here

If positive integers a and b are co-prime, then for any t ≥ ab - a - b + 1, there exist non-negative integers x and y such that ax + by = t.To get an answer for query q, we use the path

*Case 3*. Both **a** and **b** are neg. This is similar to Case 2, and we leave it to the readers.

Thus we proved that for any solvable query, there is a path that is not long, as well as any partial sum on the path cannot be too big. The rough estimate shows that any of the paths cannot take more than 1000 steps. One can get a better bound by doing more careful analysis.

Our solution is a BFS (breadth first search). The search space consists all the tuples (r, c, v), where (r, c) is the position of a digit, and denote A(r, c, v) to be the best path that evaluates to v, and ends at the position (r, c).
We know there are at most 200 such (r, c)'s (20^{2}/2), and at most (much less than) 20000 such v's from the bound we get.

The only difference with a standard BFS is that, because of the lexicographical requirement, we may need to update the answer on a node. But we never need to re-push it into the queue, since it is not yet expanded.

Test Data

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