# Google Code Jam Archive — Practice Session 2018 problems

## Overview

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.

## A. Number Guessing

### Welcome to the Practice Session!

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.

### Problem

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.

### Input and output

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.

### Limits

1 ≤ T ≤ 20.
A = 0. N = 30.
Time limit: 10 seconds per test set.
Memory limit: 1GB.

B = 30.

B = 109.

### Sample interaction

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
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
```

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
printline 31 to stdout     // guesses 31
flush stdout
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
printline 31 to stdout     // guesses 31
flush stdout
```

### Local Testing Tool

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.

## B. Senate Evacuation

### Welcome to the Practice Session!

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.

### Problem

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!

### Input

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, P1, P2, ..., PN, where Pi represents the number of senators of the party named after the i-th letter of the alphabet.

### Output

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.

### Limits

1 ≤ T ≤ 50.
No party will have an absolute majority before the start of the evacuation.
1 ≤ Pi ≤ 1000, for all i.
Time limit: 30 seconds per test set.
Memory limit: 1GB.

#### Test set 1 (Visible)

2 ≤ N ≤ 3.
sum of all Pi ≤ 9.

#### Test set 2 (Hidden)

2 ≤ N ≤ 26.
sum of all Pi ≤ 1000.

### Sample

 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.

## C. Steed 2: Cruise Control

### Welcome to the Practice Session!

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.

### Problem

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 Ki and is traveling at its maximum speed of Si kilometers per hour.

Horses are very polite, and a horse H1 will not pass (move ahead of) another horse H2 that started off ahead of H1. (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 H1 catches up to another slower horse H2, H1 reduces its speed to match the speed of H2.

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?

### Input

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 Ki and Si: the initial position (in kilometers) and maximum speed (in kilometers per hour) of the i-th of the other horses on the road.

### Output

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.

### Limits

1 ≤ T ≤ 100.
0 < Ki < D ≤ 109, for all i.
KiKj, for all i ≠ j. (No two horses start in the same position.)
1 ≤ Si ≤ 10000.
Time limit: 10 seconds per test set.
Memory limit: 1GB.

1 ≤ N ≤ 2.

1 ≤ N ≤ 1000.

### Sample

 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.

## D. Bathroom Stalls

### Welcome to the Practice Session!

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.

### Problem

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 LS and RS, 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(LS, RS) is maximal. If there is only one such stall, they choose it; otherwise, they choose the one among those where max(LS, RS) 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(LS, RS) and min(LS, RS) be?

### Input

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.

### Output

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(LS, RS), and `z` is min(LS, RS) as calculated by the last person to enter the bathroom for their chosen stall S.

### Limits

1 ≤ T ≤ 100.
1 ≤ KN.
Time limit: 30 seconds per test set.
Memory limit: 1GB.

1 ≤ N ≤ 1000.

1 ≤ N ≤ 106.

1 ≤ N ≤ 1018.

### Sample

 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.

## Analysis — A. Number Guessing

### Test set 1

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`.

### Test set 2

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

Initially, we know the answer P is in [1, 109], which is a big range! To cut that range by half, our first guess will be (1 + 109) / 2 = 5×108. If the judge sends back `TOO_SMALL`, we will know that P is in [1, 5×108). Similarly, if the judge sends back `TOO_BIG`, P is in (5×108, 109]. Otherwise, P is 5×108 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 log2109 = 29.897353 < 30 tries to guess P correctly.

### Sample Solutions

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:

#### Bash:

``````read t
for p in \$(seq 1 \$t); do
a=\${line[0]}
b=\${line[1]}
tail=\$b
while true; do
echo \$mid
if [[ "\$s" == "CORRECT" ]]; then
break
elif [[ "\$s" == "TOO_BIG" ]]; then
tail=\$(( mid - 1 ))
elif [[ "\$s" == "TOO_SMALL" ]]; then
else
exit 0
fi
done
done

``````

#### C:

``````#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;
}

``````

#### C#:

``````using System;

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

``````

#### C++:

``````#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")
else
tail = m - 1;
}
}
return 0;
}

``````

#### Go:

``````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
_ <- getNum
singleCase (a+1) b
solve (n-1)

main = do
hSetBuffering stdout NoBuffering
t <- getNum
solve t

``````

#### Java:

``````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);
}
}
}

``````

#### JavaScript:

``````var readline = require('readline');

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(' ');
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:

``````<?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);
}
?>

``````

#### Python2:

``````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)

``````

#### Python3:

``````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)

``````

#### Ruby:

``````\$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
``````

## Analysis — B. Senate Evacuation

### Test set 1

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.

### Test set 2

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.

## Analysis — C. Steed 2: Cruise Control

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.

## Analysis — D. Bathroom Stalls

### Test set 1

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(NK) time and thus finish immediately, but even a slow O(N2K) 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.

### Test set 2

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:

1. Find any longest subsequence of consecutive empty stalls.
2. 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!
repeat K times:
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.

### Test set 3

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(log2 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.