Connection Status:
Competition Arena > LightbulbRow

LightbulbRow

SRM 813 · 2021-09-15 · by misof

SRM 813 · 2021-09-15 · by misof · Greedy, Simple Search, Iteration, Simulation
Class Name: LightbulbRow
Return Type: String
Method Name: solve
Arg Types: (string, int, int)
Problem Statement

Problem Statement

There is a row of N lightbulbs. The lightbulbs are numbered 0 through N-1 from left to right. Each lightbulb is on (denoted 'O') or off (denoted 'X').

You are given the initial states of all bulbs as a String bulbStates with N characters.


You are currently standing at bulb number startIndex.

Your goal is to have the correct level of illumination: exactly goalCount lightbulbs must be on.


You can perform three types of action:

  • If you are at a lightbulb with a number X > 0, you can take a step left: to bulb X-1. This action is denoted '<'.
  • If you are at a lightbulb with a number X < N-1, you can take a step right: to bulb X+1. This action is denoted '>'.
  • You can switch the lightbulb where you stand (turning it off if its on and vice versa). This action is denoted 'S'.

Find any sequence of at most 3*N actions that reaches the desired goal. Return a String describing those actions.

Notes

  • Any valid solution will be accepted. It is not necessary to minimize the number of actions taken.
  • The value N is not given explicitly. You can determine it by looking at the number of characters in bulbStates.
  • The character that denotes a lit lightbulb is the capital letter oh (not a zero).
  • You are not allowed to step left when standing at the leftmost bulb, or step right when standing at the rightmost bulb.

Constraints

  • bulbStates will have between 1 and 500 characters, inclusive.
  • Each character in bulbStates will be 'O' or 'X'.
  • Let N denote the number of characters in bulbStates.
  • startIndex will be between 0 and N-1, inclusive.
  • goalCount will be between 0 and N, inclusive.
Examples
0)
"XXXXXXXXXX"
4
3
Returns: "S>>S"

All lightbulbs start off. We start at lightbulb 4. The returned solution corresponds to turning this lightbulb on, taking a step left, turning lightbulb 3 on, taking three steps right, and turning lightbulb 6 on.

1)
"XXXXOOOXXX"
0
3
Returns: "SSSS"

We currently have exactly three lit lightbulbs, so one valid solution is to do nothing (i.e., return an empty string). However, just to illustrate that you don't have to return the shortest possible solution, our solution flips the state of bulb 0 four times.

2)
"XXXXOOOXXX"
0
2
Returns: ">>>>S"

Sometimes you start with too many lit lightbulbs, so you have to turn some off.

3)
"OXXXXXOXXXOXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXOXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXOXXXXXXOXXXXXXXXXXXXXXXOXXXXXXXOXXXXXXXOXXXXXXOXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXX"
2
110
Returns: "<<>S>S>S>S>S>>S>S>S>>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>>S>>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>S>>S>S>S>S>S>S>S>S>S>S>>S>>S>S"
4)
"OOXOOOXOOOOOOOOOOOOOOOOOXOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOXOOOOOOOOOOXXOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOXOOOOXXOOOOOOOOOOOXOXOOOOOOXOOOOOOOOOOOOOOOOOOXOXOXOOOOOOOOOOOOOOOXXOOOOXOOOOXOOOOOXOOOOOOOOXOOOOOOXOOOOOOOOXOOOOOOOOOOOOXOOOOOOOOOXOOOOXOOOOOOOOOOOOOOOOOOOOOOOXOOXOXOOXOOOOOOOOXOXOOOOOOXOOOOOOOOOOOXXOOXOOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOOXOOOOOXOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOXOOXOOOOOOOOOOOOOOOOOOOOOOXOOOXOXOOOOOO"
47
460
Returns: "<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<>>S>>>>S>>>>>>>>>>>>>>>>>>S>>>>>S>>>>>>>>>>>>>>>>>>>S>>>>>>>>>>>>>S>>>>>>>>>>>S>S>>>>>>>>>>>S>>>>S>>>>>>>>>>>>>>>>S>>>>>>>>>>>>>>>>>>>>>>S>>>>>>>>>>>>S>>>>>S>S>>>>>>>>>>>>S>>S>>>>>>>S>>>>>>>>>>>>>>>>>>>S>>S>>S>>>>>>>>>>>>>>>>S>S>>>>>S>>>>>S>>>>>>S>>>>>>>>>S>>>>>>>S>>>>>>>>>S>>>>>>>>>>>>>S>>>>>>>>>>S>>>>>S>>>>>>>>>>>>>>>>>>>>>>>>S>>>S>>S>>>S>>>>>>>>>S>>S>>>>>>>S>>>>>>>>>>>>S>S>>>S>>>>>>>>S"

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

Coding Area

Language: C++17 · define a public class LightbulbRow with a public method string solve(string bulbStates, int startIndex, int goalCount) · 111 test cases · 2 s / 256 MB per case

Submitting as anonymous