Connection Status:
Competition Arena > RedGreenBlueLight

RedGreenBlueLight

SRM 822 · 2022-01-16 · by misof

SRM 822 · 2022-01-16 · by misof · Math
Class Name: RedGreenBlueLight
Return Type: int[]
Method Name: move
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are in charge of preparing the next big hit: a show called the calamari game.

For this show you have created a variation of a children's game. You call it "red light, green light, blue light". Your version of this game looks as follows:

There are some participants. Initially, each participant is some number of steps away from the goal line. You are given these distances in the int[] steps.

The game is played in turns. Each turn looks as follows:

  • Each participant turns on one of the three lights on their helmet: red, green, or blue.
  • A scary mechanical doll with a machine gun will choose one of the colors. The players with the chosen color are allowed to take one step towards the goal line. All other players are immediately eliminated from the game.

The players win when at least one of them reaches the goal line. The doll wins when everyone gets eliminated.

Given the starting locations of all players, determine whether a cooperating group of players has a winning strategy. If they don't, return {-1}. If they do, find one winning set of choices the players should make in the first turn of the game. Return a int[] with one element for each player (in the order in which they are given in the input). Each element of the return value should be 0, 1, or 2. These values represent the three different light colors each player can choose from.

Constraints

  • steps will contain between 1 and 1000 elements, inclusive.
  • Each element of steps will be between 1 and 999,999,999, inclusive.
Examples
0)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: {0, 2, 2, 1, 0, 2, 0, 0, 2, 1 }

As long as these players don't make the mistake of just choosing one or two colors only, they will win the game after its first round.

1)
{11, 11, 11, 11, 11, 11, 11, 11, 11, 11}
Returns: {-1 }

The doll can guarantee to eliminate at least one player per round, and if it does so, this bunch of players doesn't stand a chance.

2)
{7, 8, 9, 7, 7, 8, 9, 8, 7, 9, 7, 7, 8, 8}
Returns: {-1 }

The doll can use better strategies than the one described in the previous example. For example, whenever there are 14 players as in this example, the doll can easily make sure that at most four of them will reach the next turn.

3)
{1, 2, 3, 4, 5, 6, 7, 999888777, 2, 3, 4, 5, 2, 3, 2, 9, 1, 7, 2, 3, 4, 5, 6, 7, 15}
Returns: {2, 0, 1, 1, 0, 2, 1, 2, 0, 2, 1, 1, 0, 2, 0, 2, 1, 0, 1, 0, 2, 1, 2, 2, 1 }
4)
{1}
Returns: {-1 }

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

Coding Area

Language: C++17 · define a public class RedGreenBlueLight with a public method vector<int> move(vector<int> steps) · 108 test cases · 2 s / 256 MB per case

Submitting as anonymous