This Kickstart round began with *Even Digits*, which was a simple adhoc problem.
Then came *Lucky Dip*,which could be solved with some knowledge of basic probability theory.
Finally, we had *Scrambled Words*, whose large dataset involved an elegant observation on the number of distinct lengths of words possible given a fixed total length.

Thanks to everyone who participated!

**Cast**

Problem A (Even Digits): Written and prepared by Jonathan Irvin Gunawan.

Problem B (Lucky Dip): Written and prepared by Celestine Lau.

Problem C (Scrambled Words): Written by Karthik Sundara Raghavan and Akashdeep Nain. Prepared by Lalit Kundu.

Solutions and other problem preparation and review by Ian Tullis, Lalit Kundu, Satyaki Upadhyay, Jonathan Irvin Gunawan, Akashdeep Nain, Shi-Jie Khor, Trung Thanh Nguyen and Hyeonjong Ryu.

Analysis authors:

- Even Digits: Jonathan Irvin Gunawan
- Lucky Dip: Shi-Jie Khor
- Scrambled Words: Satyaki Upadhyay

Supervin has a unique calculator. This calculator only has a display, a plus
button, and a minus button. Currently, the integer **N** is displayed on
the calculator display.

Pressing the plus button increases the current number displayed on the
calculator display by 1. Similarly, pressing the minus button decreases the
current number displayed on the calculator display by 1. The calculator does
not display any leading zeros. For example, if `100`

is displayed
on the calculator display, pressing the minus button once will cause the
calculator to display `99`

.

Supervin does not like odd digits, because he thinks they are "odd". Therefore, he wants to display an integer with only even digits in its decimal representation, using only the calculator buttons. Since the calculator is a bit old and the buttons are hard to press, he wants to use a minimal number of button presses.

Please help Supervin to determine the minimum number of button presses to make the calculator display an integer with no odd digits.

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each begins with one line containing an integer
**N**: the integer initially displayed on Supervin's calculator.

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 button presses, as described above.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 10^{5}.

1 ≤ **N** ≤ 10^{16}.

Sample Input

4 42 11 1 2018

Sample Output

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

In Sample Case #1, the integer initially displayed on the calculator has no odd digits, so no button presses are needed.

In Sample Case #2, pressing the minus button three times will cause the
calculator to display `8`

. There is no way to satisfy the
requirements with fewer than three button presses.

In Sample Case #3, either pressing the minus button once (causing the
calculator to display `0`

) or pressing the plus button once will
cause the calculator to display an integer without an odd digit.

In Sample Case #4, pressing the plus button twice will cause the calculator
to display `2020`

. There is no way to satisfy the requirements with
fewer than two button presses.

You are participating in the Grand Kickstart Lucky Dip with many fantastic and amazing prizes (and some not so good ones)!

In this Lucky Dip, there is a bag with **N** items. The i-th item in the
bag has value **V _{i}**. You will put your hand into the bag and
draw one item at random; all items in the bag have an equal probability of
being chosen. The organizers want contestants to feel that they have some
element of choice, so after you draw an item, you can either keep it, or
"redip" by returning it to the bag and drawing again. (Note that the returned
item is now just as likely to be chosen as any of the other items in the bag.)
You may only redip a maximum of

If you play optimally to maximize the value of the item you will end the game with, what is the expected value of that item?

The input starts with one line containing one integer **T**: the number of
test cases. **T** test cases follow.

Each test case consists of two lines. The first line consists of two integers
**N** and **K**: the number of items in the bag, and the maximum number
of times you may redip. The second line consists of **N** integers
**V _{i}**, each representing the value of the i-th item.

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 expected value described above. Your answer will be
considered correct if it is within an absolute or relative error of
10^{-6} of the correct answer. See the
FAQ
for an explanation of what that means, and what formats of real numbers we
accept.

1 ≤

1 ≤

1 ≤

0 ≤

0 ≤

Sample Input

5 4 0 1 2 3 4 3 1 1 10 1 3 15 80000 80000 80000 1 1 10 5 3 16 11 7 4 1

Sample Output

Case #1: 2.500000 Case #2: 6.000000 Case #3: 80000.000000 Case #4: 10.000000 Case #5: 12.358400

In Sample Case #1, you cannot redip, so the expected value is just the mean of the items in the bag which is (1 + 2 + 3 + 4) / 4 = 2.5.

In Sample Case #2, the best strategy is to keep the item of value 10 if you
get it, and redip otherwise. The chance of getting that item (on either the
first or second draw) is 1 - (2/3)^{2} = 5/9, hence the expected value
is (5/9 * 10) + (4/9 * 1) = 6.

In Sample Case #3, since all the items have the same value, it does not matter how many times you redip and hence the expected value is 80000.

Note that cases #3 and #5 would not appear in the Small dataset.

Professor Scrmable noticed spelling mistakes in a research paper she was reviewing, but she had no difficulty in reading or understanding the words. Upon doing some research, she found an interesting article as described below:

According to a study at an English University, it doesn't matter in what order the letters in a word are, the only important thing is that the first and last letter be at the correct place. The rest can be a total mess and you can still read it without a problem. This is because the human mind does not read every letter by itself but the word as a whole.

Or rather ...

Aoccdrnig to a study at an Elingsh uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the corecrt pclae. The rset can be a toatl mses and you can sitll raed it wouthit a porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.

Professor Scrmable wants to explore this concept further and starts compiling different sentences containing similarly scrambled words to send to a popular publication. Unfortunately, the space key on the professor's keyboard is not working, so she has produced one long string of characters. She has asked you to determine how many of the words in her dictionary appear (at least once) as substrings in the long string of characters, either in their original or scrambled forms. (A scrambled form consists of the same set of letters with the first and last letters in the same places, and the others in any order.)

Note that a dictionary word can appear multiple times in the string (though it should be counted
only once since we only need to know whether it shows up at least once). For example, if we had the
word `this`

in the dictionary, the possible valid words which would be counted are
`this`

(original version) and `tihs`

(scrambled version), whereas
`tsih`

, `siht`

and other variations are not valid since they do not start
with `t`

and end with `s`

. Also, `tis`

, `tiss`

, and
`thiss`

are not scrambled forms, because they are not reorderings of the original set of letters.

Since the professor is extremely busy, she gives this task to you, her favorite and most trusted research assistant. Given a dictionary, can you count the number of words in the dictionary that appear as a substring in the professor's string at least once, in either their scrambled or original forms.

The first line of the input gives the number of test cases, **T**. **T** test cases follow.
Each testcase contains three lines. The first line contains an integer **L**. The second line
contains a list of **L** words made of lowercase English letters; these make up the dictionary.
The third line contains two lowercase English letters **S _{1}** and

First we define ord(`c`

) as the decimal value of a character `c`

and
char(n) as the character value of a decimal n. For example,
ord(`'a'`

) = 97 and char(97) = `'a'`

. You can refer to
ASCII table
for other conversions.

Now, define x_{1} = ord(**S _{1}**), x

- x
_{i}= (**A*** x_{i-1}+**B*** x_{i-2}+**C**) modulo**D**.

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 number of words from the
dictionary that appear (in their original or scrambled forms, as defined above) as substrings of the given string.

1 ≤ **T** ≤ 20.

Memory limit: 1 GB.

No two words in the dictionary are the same.

Each word in the dictionary is between 2 and 10^{5} letters long, inclusive.

The sum of lengths of all words in the dictionary does not exceed 10^{5}.

**S _{1}** and

0 ≤

0 ≤

0 ≤

1 ≤

Time limit: 20 seconds.

1 ≤ **L** ≤ 1000.

2 ≤ **N** ≤ 1000.

Time limit: 150 seconds.

1 ≤ **L** ≤ 20000.

2 ≤ **N** ≤ 10^{6}.

Sample Input

1 5 axpaj apxaj dnrbt pjxdn abd a a 50 1 1 1 30

Sample Output

Case #1: 4

In Sample Case #1, using the generation method, the generated string **S** is `aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt`

.
Scrambled or original occurences of dictionary words are highlighted as follows:

`axpaj`

occurs in its scrambled form as

.__aapxj__dnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt`apxaj`

occurs in its scrambled form as

. Note that even though__aapxj__dnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt`apxaj`

is the scrambled form of another dictionary word`axpaj`

, both should be counted.`dnrbt`

occurs twice in its original form as`aapxj`

, though it should be counted only once.__dnrbt__vldptfzbbdbbzxtndrvjblnzjfpvhdhhpxj__dnrbt__`pjxdn`

occurs in its scrambled form as`aa`

. Note this occurence overlaps with occurence of another dictionary word, but still they're counted independently.__pxjdn__rbtvldptfzbbdbbzxtndrvjblnzjfpvhdhh__pxjdn__rbt`abd`

doesn't occur at all.

**Note**: We do not recommend using interpreted/slower languages for the Large dataset of this problem.

To make our discussion easier, let us define a **beautiful** integer as an
integer which has only even digits in its decimal representation.

One useful observation for solving this problem is that we either only want to press the minus button or only want to press the plus button. It is useless to have both types in the same sequence, since they cancel each other out.

Therefore, we want to either keep pressing the minus button, or keep pressing the plus button, until we have a beautiful integer. Let M be the minimum number of minus button presses before reaching a beautiful integer, and let P be the minimum number of plus button presses before reaching a beautiful integer. Then the answer is the smaller of M and P.

Note that for this problem, the answer for an input **N** is bounded above
by **N**, since we can just press the minus button **N** times to reach
the beautiful integer `0`

. Therefore, since
**N** ≤ 10^{5}, we can solve the Small dataset using complete
search.

We can loop over a value i in the range [0, N], and, for each i, check whether
**N**+i or **N**-i is a beautiful integer. If that is the case, then we
break the loop and return i as the answer.

Iterating over the range [0, **N**] would be too slow for this dataset.
Therefore, we need another approach.

To find the value of M, we must find the largest beautiful integer that is
still no greater than **N**. Let us call this integer X. Similarly, to
find the value of P, we can find the smallest beautiful integer that is still
no smaller than **N**. Let us call this integer Y.

We can find X by decreasing the first odd digit in **N** by one and then
replacing all digits to the right of that odd digit with the largest even
digit (i.e. `8`

). For example, if **N**=`4436271`

,
then X=`4428888`

. This can create a leading 0, which we can simply
drop the leading 0 in that case. If there are no odd digits in **N**, then
**N** is a beautiful integer, thus X=**N**.

By constructing X this way, it is guaranteed that there will be no beautiful
integer between X and **N**, since the next beautiful integer after X would
be larger than **N** at the first odd digit. For the example above, the
next beautiful integer after X is `4440000`

, which is larger than
**N**.

Similarly, we can find Y by increasing the first odd digit in **N** by one
and replacing all digits to the right of that odd digit with the smallest even
digit (i.e. `0`

). If there are no odd digits in **N**, then
**N** is a beautiful integer, thus Y=**N**. However, when finding Y, we
must watch out for some tricky cases. If the first odd digit is
`9`

, then we must replace the digit directly to the left of that
odd digit as well with the next even digit. For example, if
**N**=`86912`

, then Y=`88000`

.

Another tricky case is when the digit directly to the left of the first odd
digit is `8`

. In this case, we must replace the digit directly to
the left of that `8`

digit as well, and keep doing this until we
have a non-`8`

digit. For example, if
**N**=`6488962`

, then Y=`6600000`

. Finally, if all
digits to the left continue to be `8`

until we reach the leftmost
digit, or if the first digit of **N** is a 9, then we must add the smallest
non-zero even digit (i.e. `2`

) as a new digit on the left. For
example, if **N**=`88892`

or **N**=`91112`

, then
Y=`200000`

.

Once we know X and Y, we also know M and P, and we can take the smallest of those values, just as we did before.

Test Data

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

There are two cases to consider for the small dataset: **K** = 0 and
**K** = 1.

When **K** = 0, we must accept the first item which we draw. Since the
chance of obtaining each item is the same, the expected value is the average
value of all the items in the bag.

When **K** = 1, we note that if we redip, the expected value that we draw
is going to be the same as the case when **K** = 0. Thus, the best strategy
is to keep the item if the value of the item is greater than the average value
of the items in the bag, or return the item otherwise.

Thus, we have the following equations to compute the values for E[0] and E[1]:

E[0] = ΣV/_{i}NE[1] = Σ max(V, E[0]) /_{i}N

The values for E[0] and E[1] can be computed in O(**N**) time.

When **K** > 1, we may proceed with a similar recursion as in the case when
**K** = 1. Given k redips, we should keep the item if the value of the item
is greater than the expected value for k-1 redips, and we should return the
item otherwise. This gives rise to the following recursion:

E[k] = Σ max(V, E[k-1]) /_{i}N

Computing E[**K**] using the above approach requires us to compute E[0],
E[1], ..., E[**K** - 1], each of which requires O(**N**) time. Thus,
the total runtime amounts to O(**N****K**), which is fast enough to pass
the large dataset. However, it is possible to derive an even faster solution.

Suppose we have already computed the value for E[k - 1]. If our array of
**V _{i}**s is sorted, we can use a binary search to quickly
determine the quantity of items which have value less than or equal to E[k - 1]. Let us
denote this quantity with x

On the other hand, there is an equal likelihood for drawing each of the
remaining **N** - x_{k} items. This gives us the following
equation for E[k]:

E[k] = x_{k}* E[k - 1] /N+ Σ_{i>xk}V/_{i}N

For fast computation, we precompute by sorting the array of
**V _{i}**s in increasing order, and computing the suffix sums for the
array. We will then compute E[0], E[1], ..., E[

Test Data

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

Let us first discuss how to check if two words are equivalent. A word is equivalent to another if
their corresponding starting and ending letters are same and the sets of letters in between are
either the same or permutations of each other.
To check if two words are equivalent, after verifying that their starting and ending letters are
equal, we populate a frequency array of the characters in each string and check if the two
frequency arrays are same or not. Since the strings in this problem consist of only lowercase
English letters, the array only needs to hold 26 integers (the counts of those letters'
frequencies), and we can compare two such arrays very quickly.
arrays will be very fast. An example of this would be the frequency away [1, 1, 2, 0, ... 0]
for the string `bcca`

.

Given the relatively small caps on **L** and **N** in the Small dataset, one solution that
may come to mind is as follows: For each word in the dictionary,
iterate over the Professor's text and check for substring match at each position in the text
using the method of frequency arrays described above. But we should think carefully about how we
check substrings against each other. Suppose that the length of our dictionary word is W. If we do
it naively, for each position in the text (assume the length of the dict word
is W), we check the substring of length W starting at that position by iterating over it, which is
suboptimal. We should maintain a running frequency array. Suppose the frequency array is populated
for the substring starting at position *i*. When we move our substring window one character
to the right,
we need to decrement the frequency of text[i] and increment the frequency of text[i+l]. This will
give us the frequency array of the substring starting at position *i+1*.
These two operations take constant time.

Since we iterate over the whole text for every dictionary word and there are **L** words and
the length of the text is **N**, the total time complexity of this
solution will be O(**N****L**).

The above approach will not work in the large dataset because there are too many words in the dictionary.

The solution for this dataset hinges on the observation that if the total length of the words in
the dictionary is bounded by **M**, the maximum possible number of distinct word lengths is
atmost **√M**. This can be seen as follows. Let X be the bound on the number
of distinct lengths; then X*(X+1)/2 ≤ **M**.

The above solution is now modified by iterating over only those lengths which are present in the
dictionary, and for each such length, we perform the same process as above, checking against only
the dictionary words with that length.. Let **M** be
the upper bound on the dictionary which is given as 10^{5}.
Since there are at most **√M** distinct lengths, the overall complexity of
the solution is O(**N** **√M**).

Test Data

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