CCO '20 P4 - Travelling Salesperson

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 7.0s
Memory limit: 1G

Author:
Problem type
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 2\,000), 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.


Comments

There are no comments at the moment.