Connection Status:
Competition Arena > FilmSort

FilmSort

TCO19 Wildcard Fun Round · 2019-08-16 · by misof

TCO19 Wildcard Fun Round · 2019-08-16 · by misof · Greedy, Simple Math, Simple Search, Iteration
Class Name: FilmSort
Return Type: int[]
Method Name: sort
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You have N reels, numbered 0 through N-1. One of the reels is empty. Each of the others contains a film with some movie. The films are numbered 1 through N-1.

The collection is messed up: the reel numbers don't necessarily match the film numbers, and some films are wound backwards on their reels.

You would like to sort your collection. More precisely, you would like to have it in the state in which reel 0 is empty and each other reel x contains the film x, wound in the correct direction (so that the movie plays forwards, not backwards, when played from the reel).

The only operation you can do is to take a reel with a film and to rewind the film from that reel onto the reel that is currently empty. Note that each such operation reverses the film.

You are given a description of the collection in the int[] reels with N elements. For each i, reel i contains the film abs(reels[i]), and if reels[i] is negative, that film is currently reversed. As a special case, 0 denotes the empty reel.

Find any sequence of at most 5*N operations that sorts the collection. Return the sequence as a int[] containing, for each operation in chronological order, the number of the reel from which you move a film. If there is no such sequence, return {-1} instead.

Notes

  • Any valid solution with at most 5*N operations will be accepted. You are not required to minimize the number of operations.

Constraints

  • N will be between 1 and 50, inclusive.
  • reels will contain exactly N elements.
  • Absolute values of the elements of reels will form a permutation of 0, 1, ..., N-1.
Examples
0)
{0, 1, 2, 3}
Returns: { }

This collection is already sorted correctly, no moves are needed.

1)
{-2, 1, 0, 3}
Returns: {0, 3, 0 }

The shortest solution has just one operation: rewind the film from reel 0 onto reel 2. Note that this reverses the film. Our solution's output does two more operations after that - to illustrate that you do not have to return the shortest possible solution.

2)
{2, 0, 1, 3}
Returns: {0, 2, 1, 0 }

Note that this input cannot be solved in two operations. The sequence of operations {2, 0} produces the collection {0, -1, -2, 3} that is not correct yet: films 1 and 2 are wound incorrectly.

3)
{0, 1, -2}
Returns: {-1 }

We are sorry, but there is no way to fix this collection.

4)
{0}
Returns: { }

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

Coding Area

Language: C++17 · define a public class FilmSort with a public method vector<int> sort(vector<int> reels) · 81 test cases · 2 s / 256 MB per case

Submitting as anonymous