Canadian Computing Olympiad: 2020 Day 2, Problem 1

In the city of RedBlue, every pair of buildings is connected by a road, either red or blue. To switch from travelling along red roads to blue roads or vice versa costs one ticket. The length of a route is the number of buildings that are visited. For example, the following route has a length of five and costs one ticket:

If we wanted to travel on a blue road again after visiting vertex 3 for the second time, we would need another ticket, for a total of two tickets:

You are a travelling salesperson visiting the city of RedBlue, and you wish to visit each building at least once, while minimizing repeated visits of the same buildings. You have not yet decided which building you are starting your route from, so you would like to plan out all possible routes. Furthermore, you only have access to one ticket. For each building, you would like to find a route of minimum length that begins at that building, visits all the buildings at least once, and uses at most one ticket.

Input Specification

The first line will contain a single integer $N$ $(2\le N\le 2000)$, the number of buildings in RedBlue.

Lines $2$ to $N$ each contain a string, with line $i$ containing the string $C_i$, representing the colours of the roads connected to building $i$. The string $C_i=C_{i,1}{C}_{i,2}\dots C_{i,i-1}$ has a length of $i-1$ and consists only of the characters R and B. If $C_{i,j}$ is R, then the road between buildings $i$ and $j$ is red. Otherwise, it is blue.

Output Specification

Output $2N$ lines. Lines $2i-1$ for $1\le i\le N$ should each contain a single integer $M_i$, representing the length of the travel plan starting at building $i$. Lines $2i$ for $1\le i\le N$ should each contain $M_i$ space separated integers, describing the order in which you visit the buildings, starting at building $i$.

Scoring

For every one of your travel plans, a score is computed. Let $K_i$ be the length of the optimal route starting at each building, and let $M_i$ be the length of your route.

• If $M_i$ is greater than $2K_i$, then your score will be $0$, and you will receive a verdict of Wrong Answer.
• If $M_i$ is equal to $K_i$, then your score will be $25$.
• Otherwise, you will receive a score of $\lfloor 8+8\times \frac{2K_i-M_i}{K_i-1}\rfloor$.

Your score for the test case is the minimum score for each travel plan.

If any of your plans are invalid, your score will be $0$, and you will receive a verdict of Wrong Answer.

Your submission's score is the minimum score over all test cases.

Sample Input

4
R
RR
BRB

Possible Output for Sample Input

5
1 4 2 1 3
6
2 3 1 2 3 4
5
3 1 2 3 4
4
4 3 1 2

Explanation of Possible Output for Sample Input

RedBlue looks like this:

The route starting from building 3 has an optimal length of 4 by visiting the buildings in the order 3, 2, 1, 4. The solution's route has a length of 5, meaning the score is equal to $\lfloor 8+8\times \frac{2\times 4-5}{4-1}\rfloor =16$.