This Kickstart round began with *Ambiguous Cipher*, which required an
insight about how to decode a message. Then came *X Squared*, which
seemed to involve a search with an intractably large space, but could be
solved by thinking carefully about the starting state. Next was
*Magical Thinking*, which presented too many possibilities for brute
force to handle, but allowed various solution approaches. Finally, we had
*The 4M Corporation*, which involved building lists of numbers to meet
certain requirements, and could even be solved in constant time with enough
thought!

Thanks to everyone who participated! Kickstart Round D will take place soon; check the Kickstart schedule for more details.

**Cast**

Problem A (Ambiguous Cipher): Written and prepared by Chao Ching (Diana) Chang.

Problem B (X Squared): Written by Ian Tullis. Prepared by Juwuan Turner-Howard.

Problem C (Magical Thinking): Written by Ian Tullis. Prepared by Pablo Heiber and Josef Ziegler.

Problem D (The 4M Corporation): Written and prepared by Ian Tullis.

Solutions and other problem preparation and review by Chao Ching (Diana) Chang, Md Mahbubul Hasan, Lalit Kundu, Igor Naverniouk, Trung Thanh Nguyen, Nipuna Samarasekara, Juwuan Turner-Howard, Ray Robinson Valiente, Erick Wong, and Josef Ziegler.

Analysis authors:

- Ambiguous Cipher: Chao Ching (Diana) Chang and Ian Tullis
- X Squared: Ian Tullis
- Magical Thinking: Ian Tullis
- The 4M Corporation: Ian Tullis

Susie and Calvin are classmates. Calvin would like to be able to pass notes to Susie in class without their teacher or other classmates knowing what they are talking about, just in case the notes fall into the wrong hands. Calvin has devised the a system to encrypt his messages.

Calvin only passes one word to Susie each time, and that word consists of only uppercase letters, because Calvin is so excited to talk to Susie. Each word is encrypted as follows:

- Calvin assigns a number to each letter based on the letter's position
in the alphabet, where
`A`

= 0,`B`

= 1, ...,`Z`

= 25. - For every letter in the word, Calvin determines the encrypted value of the letter by summing the values of the 1 or 2 letter(s) that are adjacent to that letter in the word. He takes that sum modulo 26, and this is the new value of the letter. Calvin then converts the value back to an uppercase letter based on positions in the alphabet, as before.
- The encrypted word is determined by encrypting every letter in the word using this method. Each letter's encryption is based only on the letters from the original unencrypted message, and not on any letters that have already been encrypted

Let's take a look at one of the notes Calvin is writing for Susie. Since
Calvin is always hungry, he wants to let Susie know that he wants to eat
again. Calvin encrypts the word `SOUP`

as follows:

`S`

= 18,`O`

= 14,`U`

= 20, and`P`

= 15.- Calvin encrypts each letter based on the values of its neighbor(s):
- First letter: 14 mod 26 = 14.
- Second letter: (18 + 20) mod 26 = 12.
- Third letter: (14 + 15) mod 26 = 3.
- Fourth letter: 20 mod 26 = 20.

- The values 14 12 3 20 correspond to the letters
`OMDU`

, and this is the encrypted word that Calvin will write on the note for Susie.

It is guaranteed that Calvin will not send Susie any words that cannot be
decrypted at all. For example, Calvin would not send Susie the word
`APE`

, since it does not have any valid decryptions. (That is,
there is no word that Calvin could have encrypted to `APE`

.)

However, Calvin's system is not perfect, and some of the words he sends Susie
can actually be decrypted to multiple words, creating ambiguity! For example,
`BCB`

can be decrypted to `ABC`

or `CBA`

,
among other possibilities.

Susie pulled another all-nighter yesterday to finish school projects, and she is too tired to decrypt Calvin's messages. She needs your help!

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each case is a single line that contains a string
**W** of uppercase letters: an encrypted word that Calvin has sent.

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 decrypted word, or `AMBIGUOUS`

if it is impossible to
uniquely determine the decrypted word.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

**W** consists of only of uppercase English letters.

**W** is decryptable to one or more words. (That is, **W** is the
result of an encryption of some word.)

**W** does not decrypt to the word `AMBIGUOUS`

. (You will only
output that when the decryption is ambiguous.)

2 ≤ the length of **W** ≤ 4.

2 ≤ the length of **W** ≤ 50.

Sample Input

3 OMDU BCB AOAAAN

Sample Output

Case #1: SOUP Case #2: AMBIGUOUS Case #3: BANANA

Note that the last sample case would not appear in the Small dataset.

Sample Cases #1 & #2 were explained in the problem statement.

In Sample Case #3, `BANANA`

is the only word that encrypts to
`AOAAAN`

.

The hot new toy for this year is called "X Squared". It consists of a square
**N** by **N** grid of tiles, where **N** is odd. Exactly 2 ×
**N** - 1 of the tiles are labeled with an `X`

, and the rest
are blank (which we will represent with the `.`

character). In
each move of the game, the player can either choose and exchange two rows of
tiles, or choose and exchange two columns of tiles. The goal of the game is
to get all of the `X`

tiles to be on the two main diagonals of the
grid, forming a larger X shape, as in the following example for **N** = 5:

```
X...X
```

.X.X.

..X..

.X.X.

X...X

You are about to play with your X Squared toy, which is not yet in the goal state. You suspect that your devious younger sibling might have moved some of the tiles around in a way that has broken the game. Given the current configuration of the grid, can you determine whether it is possible to win or not?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each one begins with one line with an integer
**N**, the size of the grid. **N** more lines with **N** characters
each follow; the j-th character on the i-th of these lines is `X`

if the tile in the i-th row and j-th column of the grid has an X, or
`.`

if that tile is blank.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is `POSSIBLE`

if it is possible to win, and `IMPOSSIBLE`

otherwise.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

**N** mod 2 = 1. (**N** is odd.)

The grid has exactly 2 × **N** - 1 `X`

tiles and
exactly **N**^{2} - 2 × **N** + 1 `.`

tiles.

The grid is not already in the goal state, as described in the problem
statement.

3 ≤ **N** ≤ 5.

3 ≤ **N** ≤ 55.

Sample Input

2 3 ..X XX. XX. 3 ... XXX XX.

Sample Output

Case #1: POSSIBLE Case #2: IMPOSSIBLE

In Sample Case #1, one winning strategy is:

- Swap the top row with the middle row.
- Swap the rightmost column with the middle column.

..X XX. X.X XX. -> ..X -> .X. XX. XX. X.X

In Sample Case #2, no sequence of moves can turn the grid into the desired final configuration.

You and **N** of your friends just took the B.A.T. (Binary Answer Test) to
try to get into wizard school. The B.A.T. has **Q** true-false questions,
and each one is worth 1 point. You have no wizard powers, so you just picked
arbitrary answers and hoped for the best.

The results of the test have already been sent out by quail mail, but the quail with your results has not arrived yet. However, each of your friends has told you their list of answers and their total score. You also remember your own list of answers. You are an optimist and you think that you probably did well!

Given that there is one correct list of answers (but you do not know what those answers are), and given your friends' answers and scores, what is the highest score that you possibly could have achieved?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each begins with one line with two integers
**N** and **Q**. Then, **N**+1 lines follow; the i-th of these lines
represents the i-th examinee's list of answers **A _{i}**, and has

`T`

or `F`

(representing True or False).
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 highest score that you possibly could have achieved that is consistent
with the given information.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

The length of **A _{i}** is

Each character of

`T`

or
`F`

, for all i.0 ≤

It is guaranteed that there is at least one possible list of correct answers that is consistent with all of the friends' answers and scores.

**N** = 1.

1 ≤ **Q** ≤ 10.

1 ≤ **N** ≤ 2.

1 ≤ **Q** ≤ 50.

Sample Input

3 1 2 TF FF 1 1 3 TTT TTF 0 2 3 TTF FTF TTT 1 2

Sample Output

Case #1: 2 Case #2: 1 Case #3: 2

Note that the last sample case would not appear in the Small dataset.

In sample case #1, your friend answered `TF`

and you answered
`FF`

, and exactly one of your friend's answers was right. If your
friend was wrong on question 1 and right on question 2, then the real set of
answers is `FF`

and you got both questions right. It is impossible
to do better than this!

In sample case #2, your friend answered all `T`

s and got all of
the questions wrong, so the real set of answers must be all `F`

s,
which means that you got only question 3 right.

In sample case #3, the only possible real lists of answers that are
consistent with the given information are `FTT`

and
`FFF`

. (For example, the real answer list cannot be
`TFT`

; the first friend's answers and score would be consistent
with that, but the second friend would have scored 0 instead of 2.) Of these
two possibilities, `FTT`

is more favorable to you and would give
you a score of 2.

The 4M Corporation has hired you to organize their departments and allocate headcount. You will create at least one department, and each department will receive some positive integer number of employees. It will not be easy, though — you have four different bosses, and each has given you a different instruction:

- The department with the fewest employees must have exactly
**MINIMUM**employees. - The department with the most employees must have exactly
**MAXIMUM**employees. - The average number of employees across all departments must be exactly
**MEAN**. - The median of the number of employees across all departments must be
exactly
**MEDIAN**. As a reminder, the median of a list is the value that, when the list is sorted in nondecreasing order, is in the center (for a list of odd length) or is the average of the two values in the center (for a list of even length).

Moreover, for the sake of efficiency, it is best to avoid creating too many departments. What is the smallest number of departments that you can create, if it is possible to satisfy your bosses' requests?

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each consists of four integers: **MINIMUM**,
**MAXIMUM**, **MEAN**, and **MEDIAN**, in that 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 either the minimum possible number of departments, or
`IMPOSSIBLE`

if it is impossible to satisfy all four bosses'
requests.

1 ≤ **T** ≤ 100.

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **MINIMUM** ≤ 8.

1 ≤ **MAXIMUM** ≤ 8.

1 ≤ **MEAN** ≤ 8.

1 ≤ **MEDIAN** ≤ 8.

The constraints for the Small dataset guarantee that the answer is either
`IMPOSSIBLE`

or is less than 14.

1 ≤ **MINIMUM** ≤ 10000.

1 ≤ **MAXIMUM** ≤ 10000.

1 ≤ **MEAN** ≤ 10000.

1 ≤ **MEDIAN** ≤ 10000.

Sample Input

5 6 4 5 1 7 7 8 8 2 2 2 2 3 7 5 5 1 4 3 4

Sample Output

Case #1: IMPOSSIBLE Case #2: IMPOSSIBLE Case #3: 1 Case #4: 2 Case #5: 3

Sample Case #1 is `IMPOSSIBLE`

because the maximum value cannot be
smaller than the minimum value.

Sample Case #2 is `IMPOSSIBLE`

because the mean and median cannot
be larger than the maximum value.

In Sample Case #3, you can create a single department with 2 employees. This satisfies all four bosses: the department with the fewest employees has exactly 2, the department with the most employees has exactly 2, and the mean and median are both 2.

In Sample Case #4, you can create one department with 3 employees and another
department with 7 employees. Note that it would **not** suffice to create
only one department with 5 employees, because then the department with the
fewest employees would not have exactly 3 and the department with the most
employees would not have exactly 7.

For Sample Case #5, you can create one department with 1 employee and two more departments with 4 employees each.

There are only 26^{2} + 26^{3} + 26^{4} = 475228
words with lengths in the [2, 4] range. The statement tells us exactly how to
encrypt a word, so we can encrypt all possible words and then create a
reverse dictionary. For example, when we find that `SOUP`

encrypts to `OMDU`

, we can create an entry in our reverse
dictionary with key `OMDU`

and value `SOUP`

. If we
ever find that a word has encrypted to a key we already have in the
dictionary (for example, `ABC`

and `CBA`

both encrypt
to `BCB`

), then that key's decryption is ambiguous, and we can
replace the value with `AMBIGUOUS`

.

Once we have done this, solving the problem is easy; we just look up each word in our dictionary and output the value as our answer. We do not need to worry about words with no valid decryption (and thus no dictionary key), because the problem statement guarantees that these will not appear in the datasets.

This method will not work for the Large dataset, though; in that case, there are just too many possible words to stuff into a dictionary in memory! We need another approach.

For now, let's assume our encrypted word has an even length. We will consider words of odd length in the next section.

When a word is being encrypted, every letter in the word (except for the first and last) is encrypted by summing the two letters adjacent to that letter. For the first and last letters, the encrypted value is just the unencrypted value of the one letter adjacent to it. This means that we can easily find the the second and second-to-last letters of the unencrypted word: they are just the first and last letters of the encrypted word, respectively.

Moreover, once we have these "footholds" into the decrypted word, we can use
them to decrypt the rest of the encrypted word! For example, we can decrypt
the encrypted word `ADMZZO`

as follows. In this explanation, we
will denote a letter with E or D (referring to the encrypted or decrypted
words) followed by a number (giving the letter's position in the word,
counting starting from 1.)

- The letter values of the encrypted word are: 0 3 12 25 25 14.
- We know that D2 and D5 equal E1 and E6, as explained above, so we know that our decrypted word has letter values _ 0 _ _ 14 _.
- We will now determine the letters in the even-numbered positions of the decrypted word, going from left to right. We will start by determining D4. We already know that D2 has value 0. Since we know that (D2 + D4) % 26 = E3, then D4 = (E3 - D2) % 26. E3 has value 12, so D4 = (12 - 0) % 26 = 12. So now our decrypted letter values are: _ 0 _ 12 14 _.
- Now that we know D4, we can find D6 in the same way: D6 = (E5 - D4) % 26 = (25 - 12) % 26 = 13. So we have _ 0 _ 12 14 13.
- Then, we do the same thing from right to left, starting with D5. We have D3 = (E4 - D5) % 26 = (25 - 14) = 11, and D1 = (E2 - D3) % 26 = (3 - 11) % 26 = 18. (It is OK to take the modulus of a negative number, but we can also always safely add 26 if we want to only handle positive values, e.g., (3 - 11 + 26) % 26.) So we know all the letter values in the decrypted word: 18 0 11 12 14 13.
- Now we just need to convert this list of decrypted letter values back to
uppercase letters, which results in the decrypted word
`SALMON`

.

This method will allow us to decrypt any word with an even length. Because the method was deterministic and we had no choices about how to decrypt, we can also see that any encrypted word with an even length has exactly one possible decryption; that is, in mathematical terms, decryption is both one-to-one and onto. But what about words with odd lengths?

Let's look back at the example `BCB`

from the problem statement.
We know that D2 = E1 and D2 = E3, so D2 is `B`

. But what about D1
and D3? All we know is that (D1 + D3) % 26 = E2. There are 26 different pairs
for which this is valid! So the decryption is ambiguous.

In fact, this is the case for *any* word of odd length that could appear
in our datasets. Our method above does not apply! Knowing the second and
second-to-last letters of the decrypted word does not help us get the entire
word, since now both of those letters are in even-numbered positions of the
decrypted word; they can only get us letters in the even-numbered positions
of the decrypted word. We have no foothold that we can use to get any of the
letters in the odd-numbered positions. The first letter of the decrypted word
could be any letter, and any choice determines all the others. We have no way
of knowing which of the 26 possibilities Calvin originally encrypted.

The statement tells us that the datasets do not include words like
`APE`

which have no valid decryption, so any word of odd length
in our dataset must have multiple decryptions. With this knowledge, we can
finish our solution: for words of even length, we use the method above, and
for words of odd length, we can just report `AMBIGUOUS`

. Calvin
and Susie should come up with a method that can handle all words, not just
words of even length!

Test Data

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

One straightforward brute-force approach to this problem is to perform a
breadth-first search
of all grids that can be reached using the allowed swap operations, and see
whether the target grid is reachable. However, this can take a while to code.
Moreover, depending on the language used and the implementation details
— e.g., how we choose to store previously seen states and avoid
revisiting them — the search may run too slowly on the **N** = 5
cases. Perhaps a breadth-first search is overkill here; can we identify all
of the reachable states in advance, without exploring?

Let's think about what swap operations *cannot* change. The set of tiles
in a particular row in the initial grid will always remain together, in some
order, in some row (not necessarily the row they started in). This is because
a column swap only changes the relative order of those tiles, and a row swap
only moves that whole set of tiles around together. So, our operations on the
board cannot exchange individual tiles among different rows; they can only
change the internal and relative orders of existing rows.

Because column swaps are the only way to change the internal order within a row, changing one row to have a certain order will give all of the rows that same internal order. However, we can choose whichever internal order we want: we pick the column with the tile we want to be first, and swap that column into the first column position, and so on.

All of the above logic holds for columns as well, and we can operate on the
columns independently enough for our purposes: if we reorder the rows, and
then reorder the columns, the latter operations do not change the chosen
order of the rows. So, we can choose any of the **N**! possible orders for
our **N** rows, and any of the **N**! possible orders for our **N**
columns, for a total of (**N**!)^{2} different states that we can
reach. (Some of these states might have the same pattern of `X`

es
and blank tiles, even if they represent different rearrangements of the
original tiles.) Unlike in our breadth-first search method, we don't need to
worry about exactly how to reach each of these states, even though the end of
the previous paragraph explains how to do so. We know that it is possible to
reach all of them, so if one of them matches the target, the answer is
`POSSIBLE`

. Moreover, we know that these are all of the states
that we can reach, so if none of them matches the target, the answer must be
`IMPOSSIBLE`

.

Now, all we have to do is write some code to permute the rows and columns of
a grid into whatever orders we want. To avoid doing too much duplicate work,
we can pick one row permutation, then apply all possible column permutations
to copies of that, then pick another row permutation, and so on. This method
is essentially a well-targeted
depth-first search,
and its running time is O((**N**!)^{2}). This is easily fast
enough for the Small dataset, in which **N** maxes out at 5. But a
squared-factorial order of growth won't work for the Large dataset! Let's
look for a better method.

Let's think about the target grid state. We can observe that it has one
`X`

tile that is the only `X`

in its row and in its
column; let's call this collection of `X`

, row, and column the
*singleton cross*. The rest of the grid contains a nested set of
**N**/2 of what we will call *rectangles*. Each rectangle is defined
by two rows and two columns, and has an `X`

tile at each of the
four intersections of those rows/columns, and no other `X`

tiles
anywhere else.

Suppose that we start at the target and perform some swap operations. What
happens to our singleton cross and our rectangles? Per our earlier
observation while solving the Small dataset, if two of the corners of a
rectangle are together in the same row, or in the same column, they always
will be; no row or column swaps can possibly split them apart. So swap
operations cannot create or destroy rectangles, although they can change the
relative positions of the four corners. Similarly, no operation can move
additional `X`

tiles into the singleton cross, or take away its
one `X`

tile.

These observations simplify the problem dramatically. We only need to ask:
does the starting grid have exactly **N**/2 rectangles and exactly one
singleton cross? If not, there is no series of swaps that can turn it into
the target, which does have those properties, so the case is
`IMPOSSIBLE`

and we are done. Otherwise, we can transform the
starting grid into the target grid as follows. Choose a rectangle, and
perform row and column swaps such that its corners end up as the outermost
corners of the larger X shape. Then recursively solve the rest of the grid as
a subproblem, and so on. At the end of all this, the singleton cross will
necessarily be in the correct place, since every other place will have been
taken.

With this reframing of the problem in mind, we no longer need to actually
perform or even think about any swaps! We only need to check the starting
grid for rectangles and a singleton row/column. It is possible to do this
with a single pass through the grid, looking at each row in turn. If a row
has zero or more than two `X`

tiles, it cannot be part of a
rectangle or a singleton cross, and so the case is `IMPOSSIBLE`

.
If a row has one `X`

tile, we need it to be part of the singleton
cross; we store the column location of that `X`

, and if we see
another would-be singleton cross row later, the case must be
`IMPOSSIBLE`

. If a row has two `X`

tiles, we note the
columns of those two tiles. Once we have checked all rows, we check to see
that every two-`X`

row's set of `X`

columns pairs up
with exactly one other two-`X`

row's set of `X`

columns, and that no such pair shares any position with any other pair.
Moreover, the position of the `X`

in the singleton cross must be
the sole column unused by any other pair. If all of these things are true,
then the case is `POSSIBLE`

.

This strategy is linear in the size of the input, and it runs fast enough to easily handle the Large dataset, as well as grids much larger than we provide in that dataset! It is also possible to run across greedy methods that carry out the swapping method we described earlier, or something that essentially boils down to it.

Test Data

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

In the Small dataset, there is only one other friend to consider, and we
know how many questions **S _{0}** they got right. We need to
choose exactly

Let's divide the questions into two types: type A when we gave the same answer as our friend, or type D when we gave different answers. Suppose that we assign the questions to sets R and W in some way, and suppose that there is a type D question in set R, and a type A question in set W. Then we got both of those questions wrong! But if we swap the two, then we instead got both questions right. So it is always advantageous to make such swaps, and we should always load up set R with as many type A questions as we possibly can. If there are not enough type A questions to do this, then we must fill up the rest of set R with type D questions.

We can either implement this greedy strategy, or generalize it into a
formula: if X is the number of questions on which we agree with our friend,
then the answer turns out to be **Q** - |**S _{0}** - X|.

Another possible approach for the Small dataset is to use brute force. Even
in the worst case of **Q** = 10, there are only 2^{10} = 1024
different possible sets of answers. We can check all of them and see
which ones are consistent with our friend's score, and which of those gives
us the highest score.

The Large dataset introduces two additional complications. For one thing,
there can now be up to 50 questions, so the brute force approach mentioned
above won't work; 2^{50} is over 10^{15}, and there are far
too many possible sets of answers to check.

Our greedy method above will work for **N** = 1, **Q** = 50, but adding
a second friend introduces some complications. For example, trying to make
greedy decisions about one friend in the same way we did for Small
dataset 1 might cause the other friend to end up with the wrong score.
However, we don't need a greedy approach, because we can take advantage of
the small number of types of questions. When **N** = 2, there are only
four types:

- Both friends agree with us.
- Only friend 1 agrees with us.
- Only friend 2 agrees with us.
- Neither friend agrees with us.

We can try every possible tuple (a, b, c, d) of the numbers of Type 1, 2, 3,
and 4 questions that we got right, with 0 ≤ a ≤ the number of Type 1
questions, 0 ≤ b ≤ the number of Type 2 questions, and so on. Any
tuples that do not cause both friends to have the correct scores should be
discarded. We can then choose the remaining tuple for which a + b + c + d is
maximized. This method is O(**Q**^{4}), but the greatest possible
number of such tuples to check occurs when **Q** = 50 and there are 12 or
13 of each of the four types, and even then, there only about 25000
possibilities to check.

Another option for this dataset is to use dynamic programming. For example, we can start with a set containing only the list [0, 0, 0], which represents that at the start of the test, before any questions are answered, we have 0 points, friend 1 has 0 points, and friend 2 has 0 points. Then, suppose that our answer to the first question is F, our first friend answered T, and our second friend answered F. There are two options: either the real answer to the first question is F (for which case we create the list [1, 0, 1], since we and the second friend have earned a point, but the first friend has not), or the real answer is T (for which case we create the list [0, 1, 0]). Then we replace our old set with the new set ([1, 0, 1], [0, 1, 0]), and for each list in that set, we in turn consider what happens when we answer F or T for the second question, and so on. Once we have finished, we check for the list in which our friends' scores are both correct and we have the highest possible score.

Why is this method any better than brute force? The key difference is that if
we create a list that is already in our set, we do not add another copy of
it, so we do not waste time individually considering many nearly equivalent
(for our purposes) answer sets. Because our scores and our friends' scores
can range from 0 to **Q**, inclusive, there are
(**Q** + 1)^{N + 1} possible lists; since (as an upper bound) we
have to check all of them once for each question, the method is
O(**Q**^{N + 2}). This is O(**Q**^{4}) when
**N** = 2. In practice, this is a "slower O(**Q**^{4})" than
the method above, since we may need to check 51^{3} × 50 =
over 6 × 10^{6} possibilities, but it is still easily fast
enough to solve the Large dataset. The approach also works just fine with a
three-dimensional array instead of a set, but the set lets us avoid checking
for the existence of all possible lists at each step of the process.

Test Data

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

The Limits section of the problem statement tells us that the answer to
every Small test case that is not `IMPOSSIBLE`

is less than 14.
This suggests that brute force is a viable option for the Small dataset. The
tight bounds imposed by **MINIMUM** and **MAXIMUM** help us out as
well. But let's think about the worst case: what if those two values are 1
and 8, respectively, and what if the answer ends up being 13? In that case,
we know that two of the values in the list must be 1 and 8, but if any of the
others can be any integer in [1, 8], then we can have 8^{11} —
over 8 billion — possibilities for the remaining numbers. That's too
much to handle in our limited time!

Fortunately, we can cut this daunting space of possibilities down to size by avoiding redundant lists. In this problem, we don't care about the difference between [1, 1, 2, 3] and [2, 1, 3, 1], for instance. One way to avoid worrying about such differences is to only consider lists that are sorted in nondecreasing order. Even in the worst case mentioned above, there are only about 75,000 different nondecreasing lists that accord with the Small limits. (You can use a combinatorial trick to find this value, or you can just experiment and see.)

One simple way to actually generate those lists is to start with a list
consisting of only **MINIMUM**, then generate all new legal lists that
append one more value to the end of that, then generate all new legal lists
that append one value to the ends of *those* lists, and so on. Since the
number of such lists is small, an approach like this is tractable. Once you
have all the lists, you can check each of them to see if it has the desired
properties, and return the length of the shortest such list, or
`IMPOSSIBLE`

if none of the lists works.

With values in the [1, 10000] range, and no upper bound on the answer, we will never be able to generate all possible lists in time. We need a general, non-brute-force solution.

Let's start with some special cases that might be easy to overlook:

- There are five sets of demands that make the task clearly
`IMPOSSIBLE`

, because they contradict the mathematical definitions of minimum, maximum, mean, and median:**MAXIMUM**<**MINIMUM****MAXIMUM**<**MEDIAN****MAXIMUM**<**MEAN****MEDIAN**<**MINIMUM****MEAN**<**MINIMUM**

- The problem might be solvable with one department. This is possible if
and only if
**MINIMUM**,**MAXIMUM**,**MEAN**, and**MEDIAN**are all the same, so we can easily confirm or rule out this case. - The problem might be solvable with two departments. This requires that
**MEAN**and**MEDIAN**are both exactly (**MINIMUM**+**MAXIMUM**) / 2). If this is true, we have no reason to consider using more departments, so we are done.

Otherwise, suppose that the problem is solvable with three departments. Then
those three values must be **MINIMUM**, **MEDIAN**, and **MAXIMUM**.
Assuming that these values do not already have the correct **MEAN**,
perhaps we can insert more values until they do. We can repeatedly insert one
value to the left of the median and one value to the right. First, we figure
out how much the mean of the existing three values deviates from the desired
mean. (To avoid errors associated with floating-point computation, it is
better to compare the values' sum with **MEAN** times the number of
values.) Suppose (without loss of generality) that the existing sum of values
is too large. Then we can figure out which two values to insert to bring down
this surplus as much as possible; usually, they will be another copy of
**MINIMUM** (on the left) and another copy of **MEDIAN** (on the
right). If inserting even one such pair won't reduce the surplus — that
is, if **MEDIAN** + **MINIMUM** is no smaller than 2 ×
**MEAN** — then this method will never work. Otherwise, we can keep
doing this until the surplus is gone. If inserting that last pair of
**MINIMUM** and **MEDIAN** would overshoot the surplus by an amount K,
we can just insert **MINIMUM** + K instead of the usual **MINIMUM**;
this value will never exceed **MEDIAN**.) We don't even need to carry out
each such step individually; we can figure out exactly how many will be
needed.

Note that since we always insert one value to the left of our original
**MEDIAN** and one to the right, the list always has a copy of
**MEDIAN** in the right place. Also, given any other valid list of odd
length, we can sort that list's values in nondecreasing order and pair them
off (ignoring the first, last and middle elements, which are fixed): the
second value with the second-to-last value, etc. Each of the pairs produced by
our method contributes maximally towards reducing the surplus (except possibly
the last one of value **MINIMUM** + K). So no valid list of odd length can
be strictly shorter, as the total contribution would be strictly smaller.

We aren't done yet, though, because the above method only produces lists with
an odd number of elements. So, regardless of what that method determined, we
need to try something similar starting with four departments: **MINIMUM**,
**MEDIAN**, **MEDIAN**, and **MAXIMUM**. (You may notice that we
could also consider **MEDIAN** - 1 and **MEDIAN** + 1, among other
possible pairs, in place of **MEDIAN** and **MEDIAN**. But there is no
reason to consider this, because it would only restrict the range of new
values we can insert, and thus require more values to adjust the mean.) Once
we get our answer from this four-department method, we can take the smaller
of its answer and the three-department method's answer, or
`IMPOSSIBLE`

if neither method worked.

This solution runs in constant time. Our efficiency-loving bosses at the 4M Corporation will certainly be happy with that!

Test Data

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