Connection Status:
Competition Arena > RowAcross

RowAcross

TCO20 Europe Qualification · 2020-10-02 · by misof

TCO20 Europe Qualification · 2020-10-02 · by misof · Greedy, Simple Math, Simple Search, Iteration, Simulation
Class Name: RowAcross
Return Type: String[]
Method Name: row
Arg Types: (int, int)
Problem Statement

Problem Statement

A group of N people just reached a river they want to cross. The only means they can use to cross the river is a nearby boat with a single paddle. The boat can carry at most C people. Paddling the boat across the river takes one minute (regardless of how many people are in the boat). Each time the boat goes from one river bank to the other, exactly one person has to paddle. It is not allowed to change the person who paddles while crossing the river.

Get all people across the river as quickly as possible.

Let the strain on a person be the number of times they paddled across the river. Among all shortest schedules, pick any one that minimizes the maximum strain.

Return the schedule as a String[]. Use the first N uppercase English letters to represent the people. For each trip across the river, return a String with the people in the boat, with the person who paddles the boat listed first.

Constraints

  • N will be between 1 and 26, inclusive.
  • C will be between 2 and 26, inclusive.
Examples
0)
13
4
Returns: {"ABCD", "B", "EFGH", "H", "IJKL", "K", "MBKH" }

Four people go to the other side ('A' paddles), then 'B' brings the boat back. The same thing is repeated two more times. After six minutes, we have nine people at the desired bank of the river and four are still on the original bank. These four are 'B', 'H', 'K', and 'M'. Out of them, 'M' is the only person who hasn't paddled yet, so we have them take everyone else to the other side and we are done. Note that the maximum strain for this solution is 1: nobody had to paddle more than once.

1)
8
6
Returns: {"ACGHEF", "FAC", "DABCF" }

In the returned solution two people ('A' and 'C') make unnecessary trips back and forth, but that does not matter. Three minutes is the optimal time, and the returned solution also clearly minimizes the maximum strain.

2)
7
3
Returns: {"ABC", "B", "DBE", "C", "FCG" }
3)
11
11
Returns: {"ABCDEFGHIJK" }
4)
16
9
Returns: {"ABCDEFGHI", "B", "JBKLMNOP" }

Submissions are judged against all 202 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RowAcross with a public method vector<string> row(int N, int C) · 202 test cases · 2 s / 256 MB per case

Submitting as anonymous