Even though about 2000 contestants had already advanced from Rounds 1A and 1B and weren't in the field for this round, Round 1C was still no picnic. To advance, contestants needed to solve at least two complete problems, or at least three small inputs and one large input with a fast enough time.

The problems were slightly easier than previous rounds. *Brattleship* involved finding a winning strategy in a simple game. The small input had one-dimensional boards, and the large input had two-dimensional boards, so coders had to take additional care before submitting their large input as the small input was not a comprehensive set of cases against which to test their code. 3434 people solved the small input correctly, and almost all of them attempted the large as well, but only two thirds of those attempts passed.

*Typewriter Monkey* could be solved easily in linear time with some insights about string matching and probability. However, a slower approach using dynamic programming could solve it as well. The limits were set small enough that a brute force algorithm could solve the small input too.

The solution to *Less Money, More Problems* seems simple, but it was still somewhat difficult to figure out the correct approach.

There were 4312 contestants who downloaded at least one input file in Round 1C. 84% of the contestants solved at least one input file, and 132 contestants got a perfect score.

Congratulations to everyone who has now advanced to Round 2!

Cast

Problem A. *Brattleship* written and prepared by Ian Tullis.

Problem B. *Typewriter Monkey* written by Ian Tullis. Prepared by Carlos Guía Vera.

Problem C. *Less Money, More Problems* written by Ian Tullis. Prepared by David Gómez Cermeño.

Solutions and other problem preparation by Ahmed Aly, David Gómez Cermeño, David Spies, Felix Halim, Ian Tullis, Igor Naverniouk, Ilham Kurnia, Jackson Gatenby, John Dethridge, Jonathan Paulson, and Karim Nosir

In each turn of the game, you name a cell on the board, and your little brother tells you whether that is a hit (one of the cells occupied by the ship) or a miss. (Your little brother doesn't say

Although the ship is not supposed to be moved once it is placed, you know that your little brother, who is a brat, plans to cheat by changing the location of the ship whenever he wants, as long as the ship remains horizontal and completely on the board, and the new location is consistent with all the information he has given so far. For example, for a 1x4 board and 1x2 ship, your little brother could initially place the ship such that it overlaps the leftmost two columns. If your first guess was row 1, column 2, he could choose to secretly move the ship to the rightmost two columns, and tell you that (1, 2) was a miss. If your next guess after that was (1, 3), though, then he could not say that was also a miss and move the ship back to its original location, since that would be inconsistent with what he said about (1, 2) earlier.

Not only do you know that your little brother will cheat, he knows that you know. If you both play optimally (you to minimize your score, him to maximize it), what is the lowest score that you can

The first line of the input gives the number of test cases, **T**. **T** lines follow, each with three space-separated integers **R**, **C**, and **W**: the number of rows and columns of the board, followed by the width of the ship.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum score you can guarantee.

Memory limit: 1 GB.

1 ≤ **W** ≤ **C**.

Time limit: 240 seconds.

**T** = 55.

**R** = 1.

1 ≤ **C** ≤ 10.

Time limit: 480 seconds.

1 ≤ **T** ≤ 100.

1 ≤ **R** ≤ 20.

1 ≤ **C** ≤ 20.

Sample Input

3 1 4 2 1 7 7 2 5 1

Sample Output

Case #1: 3 Case #2: 7 Case #3: 10

If your little brother says it is a hit, then the other cell of the 1x2 ship must be in either (1, 1) or (1, 3), and you just have to name both. If you happen to correctly name the cell where the other part of the ship is, your little brother will just reposition the ship so that (1, 2) is still hit, but your guess is a miss. Notice that your little brother can still move the ship even after it has been hit, as long as the new position is not inconsistent with the information he has already given.

If your little brother says it is a miss, then the only remaining consistent scenario is that the ship is in (1, 3) and (1, 4), and your little brother will be unable to change this from now on; you just need to name those two cells.

So no matter what your little brother does after you say (1, 2), you can finish the game in two more moves after that, for a total of three moves.

Moreover, a three-move solution is optimal, because it is impossible to guarantee a finish in only two moves: without loss of generality, pick a first move. No matter what you pick, there is still a 1x2 area open and your little brother can just move the ship there and claim that you missed. It is impossible for you to sink that ship, which has not yet been hit, with only one more move.

In Case #2, the ship completely fills in the board and so your little brother has only one place to put it. All you have to do is name every cell.

In Case #3, your little brother can always move the 1x1 ship to a cell you have not tried yet, so you must name all 10 cells, only finally getting a hit (and immediately sinking the ship) on the last one.

Your publishing house has decided to use monkeys randomly typing at keyboards to write great works of literature. You are the supervisor for one monkey with a keyboard containing **K** keys, each of which is labeled with an uppercase English letter. (There may be multiple keys displaying the same letter.) The monkey will start with an empty string and repeat the following **S** times: choose a key from its keyboard uniformly at random and press it, adding a copy of that key's letter to the right end of the string. The final resulting string will have length **S**.

You have a *target word* of length **L** that you are hoping the monkey will type. (The target word will not necessarily be a real English word.) This target word may even appear multiple times in what the monkey types. (Overlapping instances count too -- for example, if "ABA" is the target word and the monkey types "ABABA", that contains two instances of the target.)

You plan to pay the monkey one banana for each instance of the target word that it types. When you go to inspect the monkey's work, you will bring along the minimum number of bananas that you need to *ensure* that you will always have enough bananas to pay the monkey, no matter what it has typed. Then, you will pay the monkey one banana for each instance of the target word that it *actually* typed. You will keep the remaining bananas that you brought with you.

What is the expected number of bananas that you will get to keep?

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each consists of three lines. The first contains three space-separated positive integers: **K**, **L**, and **S**. The second contains a string of **K** uppercase English letters representing the monkey's keyboard. The third contains a string of **L** uppercase English letters representing the target word.

For each test case, output one line containing "Case #x: y", where y is the expected number of bananas you will get to keep after paying the monkey.

y will be considered correct if it is within an absolute or relative error of 10
Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

Time limit: 240 seconds.

1 ≤ **K** ≤ 7.

1 ≤ **L** ≤ **S** ≤ 7.

Time limit: 480 seconds.

1 ≤ **K** ≤ 100.

1 ≤ **L** ≤ **S** ≤ 100.

Sample Input

5 7 6 6 BANANAS MONKEY 2 3 4 AA AAA 2 1 2 AB B 6 2 2 GOOGLE GO 26 11 100 ABCDEFGHIJKLMNOPQRSTUVWXYZ ROSENCRANTZ

Sample Output

Case #1: 0.0 Case #2: 0.0 Case #3: 1.0 Case #4: 0.8888889 Case #5: 9.0

In Case #1, the monkey has no chance of typing the target word "MONKEY" even once (because his keyboard lacks most of the letters in "MONKEY"), so you do not bring any bananas along when you visit, and of course you do not pay any. Poor monkey!

In Case #2, the monkey is guaranteed to type "AAAA", which has two overlapping instances of the target word "AAA". You will bring two bananas and then pay both.

In Case #3, the monkey will produce the following outputs with equal probability (1/4 each): "AA", "AB", "BA", "BB". These have 0, 1, 1, and 2 instances of the target word, respectively. You must bring 2 bananas to be ready for the "BB" case, but you will on average pay (0 + 1 + 1 + 2) / 4 = 1.

In Case #4, the monkey has a 1/3 chance of typing a "G" first and a 1/3 chance of typing an "O" second, for a 1/9 chance of typing "GO". You will bring one banana and give it up 1/9 of the time.

In Case #5, the monkey could in theory type "ROSENCRANTZ" up to nine times, but the chances of this happening even once are so small that they are negligible compared to the acceptable margin of error for answers.

Up until today, the nation you live in has used **D** different positive integer denominations of coin for all transactions. Today, the queen got angry when a subject tried to pay his taxes with a giant sack of low-valued coins, and she just decreed that no more than **C** coins of any one denomination may be used in any one purchase. For instance, if **C** = 2 and the existing denominations are 1 and 5, it is possible to buy something of value 11 by using two 5s and one 1, or something of value 12 by using two 5s and two 1s, but it is impossible to buy something of value 9 or 17.

You cannot directly challenge the queen's decree, but you happen to be in charge of the mint, and you *can* issue new denominations of coin. You want to make it possible for *any* item of positive value at most **V** to be purchased under the queen's new rules. (Note that this may not necessarily have been possible before the queen's decree.) Moreover, you want to introduce as few new denominations as possible, and your final combined set of pre-existing and new denominations may not have any repeats.

What is the smallest number of new denominations required?

The first line of the input gives the number of test cases, **T**. **T** test cases follow. Each consists of one line with three space-separated values **C**, **D**, and **V**, followed by another line with **D** distinct space-separated values representing the preexisting denominations, in ascending order.

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of new denominations required, as described above.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

Each existing denomination ≤ **V**.

Time limit: 240 seconds.

**C** = 1.

1 ≤ **D** ≤ 5.

1 ≤ **V** ≤ 30.

Time limit: 480 seconds.

1 ≤ **C** ≤ 100.

1 ≤ **D** ≤ 100.

1 ≤ **V** ≤ 10^{9}.

Sample Input

4 1 2 3 1 2 1 3 6 1 2 5 2 1 3 3 1 6 100 1 5 10 25 50 100

Sample Output

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

In Case #1, it is already possible to make all the required values (1, 2, and 3) using at most one copy of each of the existing denominations.

In Case #2, it suffices to add a denomination of either 3 or 4 -- whichever you choose, only one new denomination is required.

In Case #3, the optimal solution is to add a denomination of 1.

Once we first make a hit, it will take at least W-1 more moves to win, since we have to hit the remainder of the ship.

If there's still more than one possible position for the ship, then the little brother will get at least one more opportunity to answer "miss." To limit the number of additional misses to one, we make moves adjacent to the hits we already have. If we get a "miss," then we will have a row of "hits" with a miss at the end, so we will know the exact location of the ship.

Now, the little brother may as well try to maximize the number of misses we make until we first get a hit. He can't control what cells we name, so all he can do is answer "miss" until we make a guess which must unavoidably be a hit. So we need to find a pattern of guesses that uses as few cells as possible, and such that each possible ship position is covered by one of them. To do this, we use a pattern that chooses every W^{th} cell of each row.

The total number of guesses is then R * floor(C/W) for the pattern, plus W-1 to hit the remainder of the ship, plus 1 more guess if there is more than one possibility for the position of the ship, which occurs if C is not an exact multiple of W. Below is a sample code in C that implements this solution:

#include <stdio.h> int main() { int T, TC, R, C, W, score; scanf("%d", &T); for (TC = 1; TC <= T; TC++) { scanf("%d %d %d", &R, &C, &W); // The R * floor(C/W) for the guess pattern. score = R * (C / W); // Plus W-1 to hit the remainder of the ship. score += W - 1; // Plus 1 more guess if there is more than one // possibility for the position of the ship, // which occurs if C is not an exact multiple of W. if (C % W) score++; printf("Case #%d: %d\n", TC, score); } }

tos.lunar wrote a solution for this question using Haskell, which you can download from the scoreboard.

A recursive search of the game tree, simulating all choices for our moves and the little brother's moves, will also work for the small input.

Test Data

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

This problem naturally has two parts — computing the maximum number of bananas needed, and computing the expected number of bananas needed.

Take, for example, the target string X = ABACABA. To find a string of length S containing the maximum number of copies of X, we start by putting X at the start of the string. Then to fit as many more copies as possible, we want to overlap each copy of X as much as possible with the previous copy. For this example, we could overlap with the final "A" and add "BACABA", but it is even better to overlap with "ABA" and add just "CABA" to get a second copy. To find the maximum amount of overlap, we can just try every possible amount and check which ones work, since L is small. It can also be computed in linear time using the initialization phase of the Knuth-Morris-Pratt algorithm. If the maximum amount of overlap is O, then we can fit 1+(S-L)/(L-O) copies of the string.

To find the expected number of copies, we start by computing the probability P of the word occurring at a fixed place. This is equal to the product of the probabilities for each letter of the word being correct. The probability for a single letter being correct is the fraction of keys which are that letter.

By linearity of expectation, the expected number of copies is then just P multiplied by the number of places the string can occur, which is S-L+1. This is a convenient fact to use, because we don't need to take into account that the string occurring in one position and the string occurring in an overlapping position are not independent events.

Sample implementation in Python:

# Find the maximum amount of overlap. We can just try # every possible amount and check which ones work. def max_overlap(t): for i in range(1, len(t)): if t[i:] == t[0:len(t)-i]: return len(t) - i return 0 # Returns the probability of the target word # occurring at a fixed place. def probability(target, keyboard): P = 1.0 # Compute the product of the probabilities # for each letter of the word being correct. for i in range(len(target)): # The probability for a single letter being correct # is the fraction of keys which are that letter. C = keyboard.count(target[i]) P = P * C / len(keyboard); return P for tc in range(input()): K, L, S = map(int, raw_input().split(' ')) keyboard = raw_input() target = raw_input() res = 0 P = probability(target, keyboard) if P > 0: O = max_overlap(target) max_copies = 1.0 + (S-L) / (L-O) min_copies = P * (S-L+1) res = max_copies - min_copies print("Case #%d: %f" % (tc + 1, res))

Klockan wrote a solution in C++ that also uses this approach, which you can download from the scoreboard.

We could also use a dynamic programming algorithm for both parts of the problem, using O(LS) states, where the state is the number of characters typed and the largest number of characters of the word that are currently matched, and the value at each state is the probability of that state and the maximum number of copies of the word that could have been produced while reaching it. For each of the states where the entire word has just been matched, we add the probability of reaching that state to the expected number of copies of the word, and update the maximum number of copies that are possible. linguo wrote a solution of this type in Python.

Test Data

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

We will incrementally build a set S of denominations that solves the problem using the minimal number of additional denominations, by restricting ourselves to adding denominations from smallest to largest.

As we add denominations to S, we also maintain an integer N, which is the largest value such that we can produce each value up to and including N. In fact, after all of our choices, S will be able to produce exactly the set of values from 0 to N, and no others.

When we add a new denomination X to S, the new set of values we could produce include each of the values we could produce with the existing set S plus between 0 and C of the new denomination X. If X is at most N+1, then this new set of values will be the set of all values from 0 to N+X*C, so we can update N to N+X*C.

So, we initialize S to the empty set, and N to 0.

Then while N is less than V, we do the following:

- Identify the smallest value we cannot produce: N+1.
- If there is still a pre-existing denomination which we haven't used, let the minimum such denomination be X. If X is less than or equal to N+1, we add it to S, and update N to N+X*C.
- Otherwise, we have no way yet to produce N+1 using the denominations we have, so we must add to S a new denomination X between 1 and N+1. This will increase N to N+X*C. We use X=N+1. No other choice for X could lead to a better solution, since for X=N+1, the set of values the new S will be able to produce is a superset of the values S would be able to produce with any other choice.

Finally, when we have a set S which can produce all values up to V, we output the number of new denominations we had to add.

In the above algorithm, the first option — using a pre-existing denomination — can only occur D times. When the second option is chosen, N increases to (C+1)N+C. Since we stop when N reaches V, this will occur O(log V) times. So the overall time complexity is O(D+log(V)).

Sample implementation in Java:

import java.util.*; public class C { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int T = scan.nextInt(); for (int TC = 1; TC <= T; TC++) { int C = scan.nextInt(); int D = scan.nextInt(); int V = scan.nextInt(); Queue<Integer> Q = new ArrayDeque<>(); for (int i = 0; i < D; i++) { Q.add(scan.nextInt()); } long N = 0; int add = 0; while (N < V) { // X = The smallest value we cannot produce. long X = N + 1; if (!Q.isEmpty() && Q.peek() <= X) { // Use pre-existing denomination we haven't used. X = Q.poll(); } else { // No way to produce N+1, add a new denomination. add++; } N += X * C; } System.out.printf("Case #%d: %d\n", TC, add); } } }

Vitaliy's solution in C, which you can download from the scoreboard, is another good example of this approach.

Test Data

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