We hope that you enjoyed the practice session! We have re-posted our analyses for the three previous Code Jam problems here, and we have also posted an analysis and some sample solutions for the new sample interactive problem, Number Guessing.

Number Guessing and its analysis were prepared by Anqi (Joyce) Yang. Additional solutions and other help came from Liang Bai, Md Mahbubul Hasan, Micah Stairs, and Sasan Tavakkol.

If you experience any technical issues interfering with your ability to participate in the Practice Session, please email us immediately at codejam@google.com. We will have limited support during the session, but will get back to you as soon as possible. For all other feedback, we invite you to submit your thoughts and suggestions via this feedback form after the Practice Session.

This problem is a well-known classic; we present it primarily as an opportunity for you to try out the interactive judging system.

We are thinking of an integer P within the range (**A**,**B**] —
that is, **A** < P ≤ **B**. You have **N** tries to guess our
number. After each guess that is not correct, we will tell you whether P is
higher or lower than your guess.

This problem is interactive, which means that the concepts of input and output are different than in standard Code Jam problems. You will interact with a separate process that both provides you with information and evaluates your responses. All information comes into your program via standard input; anything that you need to communicate should be sent via standard output. Remember that many programming languages buffer the output by default, so make sure your output actually goes out (for instance, by flushing the buffer) before blocking to wait for a response. See the FAQ for an explanation of what it means to flush the buffer. Anything your program sends through standard error is ignored, but it might consume some memory and be counted against your memory limit, so do not overflow it. To help you debug, a local testing tool script (in Python) is provided at the very end of the problem statement.

Initially, your program should read a single line containing a single integer
**T** indicating the number of test cases. Then, you need to process
**T** test cases.

For each test case, your program will read a single line with two integers
**A** and **B**, representing the exclusive lower bound and inclusive
upper bound, as described above. In the next line, you will read a single
integer **N**, representing the maximum number of guesses you can make.
Your program will process up to **N** exchanges with our judge.

For each exchange, your program needs to use standard output to send a single
line with one integer Q: your guess. In response to your guess, the judge
will print a single line with one word to your input stream, which your
program must read through standard input. The word will be
`CORRECT`

if your guess is correct, `TOO_SMALL`

if your
guess is less than the correct answer, and `TOO_BIG`

if your guess
is greater than the correct answer. Then, you can start another exchange.

If your program gets something wrong (e.g., wrong output format, or
out-of-bounds values), the judge will send `WRONG_ANSWER`

to your input
stream and it will not send any other output after that. If your program
continues to wait for the judge after receiving `WRONG_ANSWER`

,
your program will time out, resulting in a Time Limit Exceeded error. Notice
that it is your responsibility to have your program exit in time to receive
the appropriate verdict (Wrong Answer, Runtime Error, etc.) instead of a Time
Limit Exceeded error. As usual, if the total time or memory is exceeded, or
your program gets a runtime error, you will receive the appropriate verdict.

If your test case is solved within **N** tries, you will receive the
`CORRECT`

message from the judge, as mentioned above, and then
continue to get input (a new line with two integers **A** and **B**,
etc.) for the next test case. After **N** tries, if the test case is not
solved, the judge will print `WRONG_ANSWER`

and then stop sending output
to your input stream.

You should not send additional information to the judge after solving all test
cases. In other words, if your program keeps printing to standard output after
receiving `CORRECT`

for the last test case, you will get a Wrong Answer judgment.

1 ≤ **T** ≤ 20.

**A** = 0.
**N** = 30.

Time limit: 10 seconds per test set.

Memory limit: 1GB.

**B** = 30.

**B** = 10^{9}.

Here is a piece of pseudocode that demonstrates an interaction for one test set.
Suppose there are three test cases in this test set. The pseudocode first reads an
integer t, representing the number of test cases. Then the first test case begins.
Suppose the correct answer P is 9 for the first test case. The pseudocode first
reads three integers a, b, and n, representing the guessing range and maximum
number of tries, respectively, and then outputs a guess 30. Since 30 is greater
than 9, the string `TOO_BIG`

is received through stdin from the judge.
Then the pseudocode guesses 5 and receives `TOO_SMALL`

in response.
The guess 10 is subsequently printed to stdout which is again too big. Finally
the pseudocode guesses 9, and receives `CORRECT`

because 9 is the
correct answer.

t = readline_int() // reads 3 into t a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 30 to stdout // guesses 30 flush stdout string s = readline() // because 30 > 9, reads TOO_BIG into s printline 5 to stdout // guesses 5 flush stdout s = readline() // reads TOO_SMALL into s since 5 < 9 printline 10 to stdout // guesses 10 flush stdout s = readline() // reads TOO_BIG into s since 10 > 9 printline 9 to stdout // guesses 9 flush stdout s = readline() // reads CORRECT into s

The second test case shows what happens if the code continues to read from stdin
after the judge stops sending info. In this example, the contestant guesses 31,
which is outside the range (0, 30]. As a result, the judging system sends `WRONG_ANSWER`

to the input stream of the pseudocode and stops sending anything after that.
However, after reading `WRONG_ANSWER`

into string s, the code continues to read for
the next test case. Since there is nothing in the input stream (judge has stopped
sending info), the code hangs and will eventually receive a Time Limit Exceeded Error.

a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 31 to stdout // guesses 31 flush stdout string s = readline() // reads WRONG_ANSWER a, b = readline_two_int() // tries to read for the third test case but hangs since // judge has stopped sending info to stdin

If the code in the example above exits immediately after reading `WRONG_ANSWER`

,
it will receive a Wrong Answer judgment instead.

a, b = readline_two_int() // reads 0 into a and 30 into b; note that 0 30 is one line n = readline_int() // reads 30 into n printline 31 to stdout // guesses 31 flush stdout string s = readline() // reads WRONG_ANSWER exit // receives a Wrong Answer judgment

To better facilitate local testing, we provide you the following script.
Instructions are included inside. You are encouraged to add more test cases
for better testing. Please be advised that although the testing tool is
intended to simulate the judging system, it is **NOT** the real judging
system and might behave differently.

If your code passes the testing tool but fails the real judge, please check the Coding section of our FAQ to make sure that you are using the same compiler as us.

If you experience any technical issues interfering with your ability to participate in the Practice Session, please email us immediately at codejam@google.com. We will have limited support during the session, but will get back to you as soon as possible. For all other feedback, we invite you to submit your thoughts and suggestions via this feedback form after the Practice Session.

A small fire started in the senate room, and it needs to be evacuated!

There are some senators in the senate room, each of whom belongs to of one of
**N** political parties. Those parties are named after the first **N**
(uppercase) letters of the English alphabet.

The emergency door is wide enough for up to two senators, so in each step of the evacuation, you may choose to remove either one or two senators from the room.

The senate rules indicate the senators in the room may vote on any bill at any time, even in the middle of an evacuation! So, the senators must be evacuated in a way that ensures that no party ever has an absolute majority. That is, it can never be the case after any evacuation step that more than half of the senators in the senate room belong to the same party.

Can you construct an evacuation plan? The senate is counting on you!

The first line of the input gives the number of test cases, **T**. **T**
test cases follow. Each test case consists of two lines. The first line
contains a single integer **N**, the number of parties. The second line
contains **N** integers, **P _{1}**,

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 evacuation plan. The plan must be a space-separated list of instructions,
in the order in which they are to be carried out, where each instruction is
either one or two characters, representing the parties of the senators to
evacuate in each step.

It is guaranteed that at least one valid evacuation plan will exist. If multiple evacuation plans are valid, you may output any of them.

1 ≤ **T** ≤ 50.

No party will have an absolute majority before the start of the evacuation.

1 ≤ **P _{i}** ≤ 1000, for all i.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

2 ≤ **N** ≤ 3.

sum of all **P _{i}** ≤ 9.

2 ≤ **N** ≤ 26.

sum of all **P _{i}** ≤ 1000.

Input |
Output |

4 2 2 2 3 3 2 2 3 1 1 2 3 2 3 1 |
Case #1: AB BA Case #2: AA BC C BA Case #3: C C AB Case #4: BA BB CA |

The sample output displays one set of answers to the sample cases. Other answers may be possible.

In Case #1, there are two senators from each of the parties A and B. If we remove one from each party every time, the perfect balance is maintained until evacuation is complete.

Case #2 proceeds as follows:

Initially in the room: 3 A, 2 B, 2 C.

Evacuate AA. Still in the room: 1 A, 2 B, 2 C.

Evacuate BC. Still in the room: 1 A, 1 B, 1 C.

Evacuate C. Still in the room: 1 A, 1 B.

Evacuate AB. Evacuation complete!

Note that it would not be valid to begin the evacuation with BC, which would leave 3 A, 1 B, and 1 C in the room; party A would have an absolute majority (3 out of 5 = 60%).

For Case #3, note that `CC AB`

would also be a valid answer, and
`C C AB`

is also valid even though it requires three evacuation
steps instead of two.

If you experience any technical issues interfering with your ability to participate in the Practice Session, please email us immediately at codejam@google.com. We will have limited support during the session, but will get back to you as soon as possible. For all other feedback, we invite you to submit your thoughts and suggestions via this feedback form after the Practice Session.

Annie is a bus driver with a high-stress job. She tried to unwind by going on a Caribbean cruise, but that also turned out to be stressful, so she has recently taken up horseback riding.

Today, Annie is riding her horse to the east along a long and narrow one-way
road that runs west to east. She is currently at kilometer 0 of the road, and
her destination is at kilometer **D**; kilometers along the road are
numbered from west to east.

There are **N** other horses traveling east on the same road; all of them
will go on traveling forever, and all of them are currently between Annie's
horse and her destination. The i-th of these horses is initially at kilometer
**K _{i}** and is traveling at its maximum speed of

Horses are very polite, and a horse H_{1} will not pass (move ahead
of) another horse H_{2} that started off ahead of H_{1}. (Two
or more horses can share the same position for any amount of time; you may
consider the horses to be single points.) Horses (other than Annie's) travel
at their maximum speeds, except that whenever a horse H_{1} catches
up to another slower horse H_{2}, H_{1} reduces its speed to
match the speed of H_{2}.

Annie's horse, on the other hand, does not have a maximum speed and can travel at any speed that Annie chooses, as long as it does not pass another horse. To ensure a smooth ride for her and her horse, Annie wants to choose a single constant "cruise control" speed for her horse for the entire trip, from her current position to the destination, such that her horse will not pass any other horses. What is the maximum such speed that she can choose?

The first line of the input gives the number of test cases, **T**;
**T** test cases follow. Each test case begins with two integers **D**
and **N**: the destination position of all of the horses (in kilometers)
and the number of other horses on the road. Then, **N** lines follow. The
i-th of those lines has two integers **K _{i}** and

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 maximum constant speed (in kilometers per hour) that Annie can use
without colliding with other horses. `y`

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 ≤ **T** ≤ 100.

0 < **K _{i}** <

1 ≤

Time limit: 10 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 2.

1 ≤ **N** ≤ 1000.

Input |
Output |

3 2525 1 2400 5 300 2 120 60 60 90 100 2 80 100 70 10 |
Case #1: 101.000000 Case #2: 100.000000 Case #3: 33.333333 |

In Sample Case #1, there is one other (very slow!) horse on the road; it will reach Annie's destination after 25 hours. Anything faster than 101 kilometers per hour would cause Annie to pass the horse before reaching the destination.

In Sample Case #2, there are two other horses on the road. The faster horse will catch up to the slower horse at kilometer 240 after 2 hours. Both horses will then go at the slower horse's speed for 1 more hour, until the horses reach Annie's destination at kilometer 300. The maximum speed that Annie can choose without passing another horse is 100 kilometers per hour.

A certain bathroom has **N** + 2 stalls in a single row; the stalls on the
left and right ends are permanently occupied by the bathroom guards. The
other **N** stalls are for users.

Whenever someone enters the bathroom, they try to choose a stall that is as far
from other people as possible. To avoid confusion, they follow deterministic
rules: For each empty stall S, they compute two
values L_{S} and R_{S}, each of which is the number of empty
stalls between S and the closest occupied stall to the left or right,
respectively. Then they consider the set of stalls with the farthest closest
neighbor, that is, those S for which min(L_{S}, R_{S}) is
maximal. If there is only one such stall, they choose it; otherwise, they choose
the one among those where max(L_{S}, R_{S}) is maximal. If there
are still multiple tied stalls, they choose the leftmost stall among those.

**K** people are about to enter the bathroom; each one will choose their
stall before the next arrives. Nobody will ever leave.

When the last person chooses their stall S, what will the values of
max(L_{S}, R_{S}) and min(L_{S}, R_{S})
be?

The first line of the input gives the number of test cases, **T**.
**T** lines follow. Each line describes a test case with two integers
**N** and **K**, as described above.

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

,
where `x`

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

is max(L_{S}, R_{S}), and `z`

is min(L_{S}, R_{S}) as calculated by the last person to
enter the bathroom for their chosen stall S.

1 ≤ **T** ≤ 100.

1 ≤ **K** ≤ **N**.

Time limit: 30 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 1000.

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

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

Input |
Output |

5 4 2 5 2 6 2 1000 1000 1000 1 |
Case #1: 1 0 Case #2: 1 0 Case #3: 1 1 Case #4: 0 0 Case #5: 500 499 |

In Sample Case #1, the first person occupies the leftmost of the middle two
stalls, leaving the following configuration (`O`

stands for an
occupied stall and `.`

for an empty one): `O.O..O`

.
Then, the second and last person occupies the stall immediately to the right,
leaving 1 empty stall on one side and none on the other.

In Sample Case #2, the first person occupies the middle stall, getting to
`O..O..O`

. Then, the second and last person occupies the leftmost
stall.

In Sample Case #3, the first person occupies the leftmost of the two middle
stalls, leaving `O..O...O`

. The second person then occupies the
middle of the three consecutive empty stalls.

In Sample Case #4, every stall is occupied at the end, no matter what the stall choices are.

In Sample Case #5, the first and only person chooses the leftmost middle stall.

Since **A** = 0 and **B** = 30 in this test set, and since we get **N** = 30 tries per
test case, we can simply guess every number from 1 to 30 until the judge sends back
`CORRECT`

.

In test set 2, since the answer could be anywhere in the range (0, 10^{9}] and we still
have only 30 guesses, we will use binary search.

Initially, we know the answer P is in [1, 10^{9}], which is a big range! To cut that range
by half, our first guess will be (1 + 10^{9}) / 2 = 5×10^{8}. If the judge
sends back `TOO_SMALL`

, we will know that P is in [1, 5×10^{8}).
Similarly, if the judge sends back `TOO_BIG`

, P is in
(5×10^{8}, 10^{9}]. Otherwise, P is 5×10^{8} and we are done.

We will cut that range further by making our next guess the middle number in that range.
Again, based on the judge response that we get, we will know that either we have guessed P
correctly, or P is in the upper or lower half of the range. We will do this repeatedly, until
`CORRECT`

is received.

Each time we make a wrong guess, the range that we must examine next will always be at most half
the size of our previous range. So, it will take at most log_{2}10^{9} = 29.897353
< 30 tries to guess P correctly.

This problem was intended as an opportunity to get used to our interactive judges. Here are some example solutions in all languages that we support so far:

```
read t
for p in $(seq 1 $t); do
read -a line
a=${line[0]}
b=${line[1]}
read n
head=$(( a+1 ))
tail=$b
while true; do
mid=$(( (head+tail)/2 ))
echo $mid
read s
if [[ "$s" == "CORRECT" ]]; then
break
elif [[ "$s" == "TOO_BIG" ]]; then
tail=$(( mid - 1 ))
elif [[ "$s" == "TOO_SMALL" ]]; then
head=$(( mid + 1 ))
else
# Wrong answer; exit to receive Wrong Answer judgment
exit 0
fi
done
done
```

```
#include <stdio.h>
#include <string.h>
int main() {
int T; scanf("%d", &T);
for (int id = 1; id <= T; ++id) {
int A, B, N, done = 0;
scanf("%d %d %d", &A, &B, &N);
for (++A; !done;) {
int mid = A + B >> 1;
char result[32];
printf("%d\n", mid);
fflush(stdout);
scanf("%s", result);
if (!strcmp(result, "CORRECT")) done = 1;
else if (!strcmp(result, "TOO_SMALL")) A = mid + 1;
else B = mid - 1;
}
}
return 0;
}
```

```
using System;
public class Solution
{
static public void Main ()
{
int num_test_cases = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < num_test_cases; ++i) {
string[] lo_hi_s = Console.ReadLine().Split(' ');
int[] lo_hi = Array.ConvertAll(lo_hi_s, int.Parse);
int num_tries = Convert.ToInt32(Console.ReadLine());
int head = lo_hi[0] + 1, tail = lo_hi[1];
while (true) {
int m = (head + tail) / 2;
Console.WriteLine (m);
string s = Console.ReadLine();
if (s == "CORRECT") break;
if (s == "TOO_SMALL")
{
head = m + 1;
}
else
{
tail = m - 1;
}
}
}
}
}
```

```
#include <iostream>
#include <string>
int main() {
int num_test_cases;
std::cin >> num_test_cases;
for (int i = 0; i < num_test_cases; ++i) {
int lo, hi;
std::cin >> lo >> hi;
int num_tries;
std::cin >> num_tries;
int head = lo + 1, tail = hi;
while (true) {
int m = (head + tail) / 2;
std::cout << m << std::endl;
std::string s;
std::cin >> s;
if (s == "CORRECT") break;
if (s == "TOO_SMALL")
head = m + 1;
else
tail = m - 1;
}
}
return 0;
}
```

```
package main
import (
"fmt"
"strings"
)
func main() {
var t int
fmt.Scanf("%d", &t)
for i := 1; i <= t; i++ {
var a, b, n int
fmt.Scanf("%d %d", &a, &b)
a = a + 1
fmt.Scanf("%d", &n)
for {
m := (a + b) / 2
fmt.Println(m)
var str string
fmt.Scanf("%s", &str)
if strings.EqualFold(str, "CORRECT") {
break
} else if strings.EqualFold(str, "TOO_SMALL") {
a = m + 1
} else if strings.EqualFold(str, "TOO_BIG") {
b = m - 1
}
}
}
}
```

```
import System.IO
getNum :: IO Int
getNum = do
x <- getLine
let n = read x :: Int
return n
bisect :: Int -> Int -> Int -> String -> IO ()
bisect a b m "CORRECT" = return ()
bisect a b m "TOO_SMALL" = singleCase (m+1) b
bisect a b m "TOO_BIG" = singleCase a (m-1)
query :: Int -> IO String
query m = do
putStrLn ( show m )
hFlush stdout
x <- getLine
return x
singleCase :: Int -> Int -> IO ()
singleCase a b = do
let m = (a+b) `div` 2
response <- query m
bisect a b m response
return ()
solve :: Int -> IO ()
solve 0 = return ()
solve n = do
[a, b] <- fmap(map read.words)getLine
_ <- getNum
singleCase (a+1) b
solve (n-1)
main = do
hSetBuffering stdout NoBuffering
t <- getNum
solve t
```

```
import java.util.Scanner;
public class Solution {
public static void solve(Scanner input, int a, int b) {
int m = (a + b) / 2;
System.out.println(m);
String s = input.next();
if (s.equals("CORRECT")) {
return;
} else if (s.equals("TOO_SMALL")) {
solve(input, m + 1, b);
} else {
solve(input, a, m - 1);
}
}
public static void main(String args[]) {
Scanner input = new Scanner(System.in);
int T = input.nextInt();
for (int ks = 1; ks <= T; ks++) {
int a = input.nextInt();
int b = input.nextInt();
int n = input.nextInt();
solve(input, a + 1, b);
}
}
}
```

```
var readline = require('readline');
var rl = readline.createInterface(process.stdin, process.stdout);
expect = 'begin';
rl.on('line', function(line) {
if (expect === 'begin') {
num_test_cases = parseInt(line);
expect = 'lo_hi';
case_counter = 0;
} else if (expect === 'lo_hi') {
lo_hi = line.split(' ');
head = parseInt(lo_hi[0]) + 1;
tail = parseInt(lo_hi[1]);
expect = 'num_tries';
} else if (expect === 'num_tries') {
num_tries = line; // not used.
expect = 'solve';
mid = parseInt((head + tail) / 2);
console.log(mid);
} else if (expect === 'solve') {
if (line === 'CORRECT') {
++case_counter === num_test_cases ? rl.close() : 0;
expect = 'lo_hi';
} else {
line === 'TOO_SMALL' ? head = mid + 1 : tail = mid - 1;
mid = parseInt((head + tail) / 2);
console.log(mid);
}
}
}).on('close',function(){
process.exit(0);
});
```

```
<?php
function solve($a, $b) {
$m = ($a + $b) / 2;
printf("%d\n", $m);
fscanf(STDIN, "%s", $s);
if (strcmp($s, "CORRECT") == 0) {
return;
} else if (strcmp($s, "TOO_SMALL") == 0) {
$a = $m + 1;
} else {
$b = $m - 1;
}
solve($a, $b);
}
fscanf(STDIN, "%d", $t);
for ($ks = 0; $ks < $t; $ks++) {
fscanf(STDIN, "%d %d", $a, $b);
fscanf(STDIN, "%d", $n);
solve($a + 1, $b);
}
?>
```

```
import sys
def solve(a, b):
m = (a + b) / 2
print m
sys.stdout.flush()
s = raw_input()
if s == "CORRECT":
return
elif s == "TOO_SMALL":
a = m + 1
else:
b = m - 1
solve(a, b)
T = input()
for _ in xrange(T):
a, b = map(int, raw_input().split())
_ = input()
solve(a + 1, b)
```

```
import sys
def solve(a, b):
m = (a + b) // 2
print(m)
sys.stdout.flush()
s = input()
if s == "CORRECT":
return
elif s == "TOO_SMALL":
a = m + 1
else:
b = m - 1
solve(a, b)
T = int(input())
for _ in range(T):
a, b = map(int, input().split())
_ = int(input())
solve(a + 1, b)
```

```
$stdout.sync = true
def solve(a, b)
m = (a + b) / 2
puts m
$stdout.flush
s = STDIN.gets.chomp
if s.eql? "CORRECT"
return
elsif s.eql? "TOO_SMALL"
solve(m + 1, b)
else
solve(a, m - 1)
end
end
t = STDIN.gets.chomp.to_i
ks = 1
while ks <= t
a, b = STDIN.gets.split.map &:to_i;
n = STDIN.gets.chomp.to_i
solve(a + 1, b)
ks = ks + 1
end
```

With at most three parties and at most nine senators, various brute force approaches will work. One exhaustive strategy is to generate all possible different evacuation orders, treating senators from the same party as interchangeable, and then try all possible different ways of chopping those into groups of one or two senators.

Another, simpler strategy is to keep randomly choosing and trying one of the nine possible evacuations (A, B, C, AA, AB, AC, BB, BC, CC) as long as the chosen senator(s) exist and the evacuation will not cause a new absolute majority. You may worry that this strategy could get stuck, but the outcome of any legal evacuation will just be another possible test case for the problem, and the statement guarantees that every test case has a solution! With more parties and senators, though, this strategy might bog down in the details of checking the legality of evacuations, so we should come up with a more efficient approach.

Intuitively, it is safest to remove one senator at a time, and to always draw from whichever party has the most remaining senators (or any such largest party, if there is a tie). But this strategy won't always work! For example, if we have two senators from party A and two from party B, and no others, which is a valid test case, then removing one senator from either party will give the other party an absolute majority.

However, this strategy *is* always safe whenever there are more than two
parties present. Suppose that party 1 is currently the largest, or tied for the
largest, of at least three parties, and that we remove a single senator from
party 1. Clearly, making party 1 smaller cannot give it an absolute majority
that it didn't have before. But could some other party acquire an absolute
majority as a result? Suppose that the removal of a senator from party 1 were
to cause party 2, which currently has X senators, to have an absolute majority.
But since party 1 was the largest, or tied for the largest, before a senator
was removed, party 1 must still have at least X-1 senators. Moreover, since at
least one more party is present, there is at least 1 other senator who is not
from party 1 or 2. So there are a total of at least X remaining senators who
are not from party 2, which means the X senators of party 2 are not enough to
give it an absolute majority, so we have a contradiction.

If we start with three or more parties and keep evacuating a single senator from the largest party in this way, then at some point, we must reach a step in which we go from three parties to two parties. These two remaining parties must have only one senator each. Since we just removed the one remaining senator from the third party, it must have been a largest party, so the other two can be no larger. So we can remove this last pair of senators in a single evacuation as a final step.

What if we start with two parties? Since the problem statement guarantees that no party begins with a majority, these parties must have equal numbers of senators. So, we can evacuate them in pairs, one from each party, until the evacuation is complete.

This approach takes more steps than are needed — most of those single evacuations can be paired up — but it gets the job done.

Pop quiz, hotshots! This problem seems pretty complicated at first glance. What do you do?

One natural strategy is to try binary searching on Annie's speed, but it is difficult to directly determine whether a given speed avoids passing another horse; the input data alone does not tell us where each horse is at any given time, because horses might slow other horses down. In theory, we could figure out when faster horses catch up to slower horses and slow down, determine the exact path of each horse, and check whether our chosen speed crosses any of those paths. With only up to two horses in test set 1, this sort of calculation is feasible, but it would be laborious for test set 2.

However, we can avoid all of that work via some observations. To maximize
cruising speed, Annie's horse should reach the destination at exactly the
same time as the horse ahead of her (let's call it Horse A); there is no
reason to leave a gap. Either Horse A will reach the destination without
having to slow down (and so it will be the one that directly limits Annie's
speed), or it will be slowed down at some point by the horse ahead of it
(let's call it Horse B). The same is true for Horse B: either it will never
have to slow down (and so it will be the one that ultimately limits Annie's
speed), or it will be slowed down by the horse ahead of *it*, and so on.
So there will be a single "limiting horse" on the road that ultimately
determines how fast Annie's horse can reach the destination. We claim that
this "limiting horse" is the only horse that matters, and we can disregard
all of the others!

It is easy to see that we can ignore the horses to the east of the limiting
horse; they will reach and pass the destination before the limiting horse
gets there. What about the "intermediate horses" between Annie and the
limiting horse? We know from the way we have defined the limiting horse that
every intermediate horse will catch up to the limiting horse before reaching
the destination. (If one did not, then *it* would be the limiting
horse.) Suppose that Annie chooses a cruising speed that gets her to the
destination at exactly the same time as the limiting horse. We certainly
cannot go faster than this. Moreover, this speed is safe: it cannot possibly
cause Annie to pass any of the intermediate horses. If she were going fast
enough to overtake an intermediate horse, then she would definitely be
going fast enough to pass the limiting horse, since every intermediate
horse will catch up to the limiting horse. This would cause a contradiction.
Therefore, we do not need to worry about the intermediate horses or their
interactions with each other.

So, once we have identified the limiting horse, the strategy is simple: go at
the exact speed that will cause Annie to reach the destination at the same
time as the limiting horse. This speed can be found in constant time. We could
identify the limiting horse directly via the argument in our third paragraph
above, but even this would be unnecessary work. Instead, for each horse in
turn, we can pretend that it is the limiting horse and calculate the cruising
speed that it would force. Then the smallest of those speeds is our answer.
(If any horse allows a faster cruising speed than another, it cannot be the
limiting horse, because that cruising speed would cause Annie to pass the
true limiting horse.) This takes O(**N**) time.

For test set 1, the limits are small enough that you can just simulate
the rules outlined in the statement. Most implementations of a simulation
will run in O(**N****K**) time and thus finish immediately, but even a
slow O(**N**^{2}**K**) implementation like "try every possible
stall for the next person, and for each empty stall run a loop for each side
to check for the closest neighbors" will most likely finish in time.

For test sets 2 and 3, however, something quadratic in the number of stalls won't cut it, so we have to do better.

The critical observation to jump from test set 1 to test set 2 is that only the number of consecutive runs of empty stalls matters at any given time. The next person always chooses the middle stall or the left of the two middle stalls of a longest subsequence of consecutive empty stalls. Moreover, the output format already hints at this: even if you were to choose the rightmost of a set of two middle stalls, or a longest run of stalls other than the leftmost one, the answer would not change. Thus, we can rewrite the algorithm in this equivalent (for the required output) form:

- Find any longest subsequence of consecutive empty stalls.
- Choose the middle or one of the two middle stalls.

Notice that even though there are still ties to be broken, the output is equivalent for all of them. Since the output is equivalent, so is the multiset of lengths of consecutive runs of empty stalls left behind, so the whole process only depends on that multiset. (As a reminder, a multiset is a set in which the same element can appear more than once.) We can write an optimized simulation that solves test set 2 following this pseudocode:

S = {N} - This is a multiset! repeatKtimes: X = max(S) X0 = ceil((X - 1) / 2) X1 = floor((X - 1) / 2) if this is the last step: we are done; answer is X0 and X1 else: remove one instance of X from S insert X0 and X1 into S

If the operations over `S`

are efficient, this will run in
quasilinear time. There are many data structures that support insertion,
finding the maximum, and removal of the maximum in logarithmic time,
including AVL trees, red-black trees, and heaps. Many languages have one such
structure in their standard libraries (e.g., the `multiset`

or
`priority_queue`

in C++, `TreeSet`

in Java, and
`heapq`

module in Python). Since we take O(log **K**) time for
each of K steps, the algorithm takes only O(**K** log **K**) time,
which is fast enough to solve test set 2. However, for test set 3, even
quasilinear time on K is not enough.

The observation required to solve test set 3 is that we are simulating
similar steps over and over again. The first time a bathroom user arrives, we
partition **N** into ceil((**N** - 1) / 2) and
floor((**N** - 1) / 2), which means that numbers between
ceil((**N** - 1) / 2) and **N** will never appear in S. This hints at a
logarithmic number of simulation steps.

Let's divide the work in stages. The first stage processes only **N**.
Then, stage *i*+1 processes all of the values spawned by stage *i*.
So, stage 2 processes up to 2 values: ceil((*i* - 1) / 2) and
floor((*i* - 1) / 2). What about the other stages? It is not hard to
prove by induction that they also process at most two consecutive values:
since stage i processes two consecutive values, they are either 2x and 2x+1 or
2x and 2x-1, for some x (that is, one even and one odd number). Thus, the spawned
values for stage i+1 can only be x and/or x-1.
Since the largest value in each stage is at most half the largest
value of the previous stage, there are a logarithmic number of stages. This all
means that there are at most O(log **N**) different values
that go into S at any point. Of course, some of them appear in S many, many
times. So, the optimization to get the running time low enough for test
set 3 is to process all repetitions of a given value at the same time,
since all of them yield the same X0 and X1 values. We can do that by using a
regular set with a separate count for the number of repetitions.

S = {N} - This is a set, not a multiset! C(N) = 1 P = 0 repeat: X = max(S) X0 = ceil((X - 1) / 2) X1 = floor((X - 1) / 2) P = P + C(X) if P ≥K: we are done; the answer is X0 and X1. else: remove X from S insert X0 and X1 into S add C(X) to the counts of X0 and X1 in C

Once again, we have structures that implement all the required operations in
logarithmic time, yielding an O(log^{2} **N**) running time
overall. In general, adding any good dictionary implementation to the
structure of choice from the test set 2 solution would work, either by
plugging the dictionary functionality into the structure (like
`map`

in C++ or `TreeMap`

in Java) or having a separate
hash-table for the dictionary (which is the easiest implementation in Python).

Moreover, since we proved the population of S is at most 4 at any given time
(only values from two consecutive stages can coexist in S), any implementation
of set and dictionary will provide all operations in constant time, because the
size of the whole structure is bounded by a constant! This makes the overall
time complexity just O(log **N**).

This was a nice problem to put experimentation to work if your intuition was not
enough. After solving test set 1, if you print the succession of values for a
fixed **N**, you may spot the pattern of few values occurring
in the set S, and from there, you can find the mathematical arguments to support
the needed generalization. In harder problems in later rounds, this can become an
even more important asset to tackle problems. As you can see in many parts of last
year's finals live stream,
finalists use experimentation a lot to inspire themselves and/or validate their ideas
before committing to them.