EllysLightbulbs

TCC19 South America Final · 2019-06-10 · by espr1t

TCC19 South America Final · 2019-06-10 · by espr1t · Brute Force, Greedy, Recursion

Show categories

Class Name: EllysLightbulbs

Return Type: String

Method Name: getMax

Arg Types: (int, int, vector<string>)

Problem Statement

Elly's home has L lightbulbs. These are controlled by N switches. Each switch turns on a subset of the lightbulbs (possibly none or all of them).

Elly has numbered the lightbulbs 0 through L-1 in decreasing order of importance. For example, the lightbulb in the attic where she goes once per year has a much bigger number than the one in the living room.

Given two different sets of lightbulbs, A and B, we say that A is more important than B if and only if the most important lightbulb on which they differ is in A but not in B. For example, the set {1, 3, 9} is more important than the set {1, 4, 5, 6, 7} because of lightbulb 3.

The house electricity system has a serious flaw: whenever Elly uses a switch which is supposed to turn on a lightbulb that is already on, the bulb burns out and it can no longer be lit.

All lights are currently off. Elly wants to use some (possibly none or all) switches in such a way that in the end the most important set of bulbs will be lit. (Note that some of the bulbs that are not lit in the end may be burned out. Elly does not care about the number of bulbs that burn out.)

You are given the ints N and L, as well as a String[] switches which gives information on which lightbulbs are affected by which switch. Each switch corresponds to one element of switches, and character i of that element is '1' if said switch turns on bulb i, or '0' if it does not do that.

Return a String describing the most important set of lightbulbs Elly can light, with '1' representing a bulb that's on and '0' a bulb that's off. (That is, use '0' for bulbs that have never been turned on and also for bulbs that burned out.)

Constraints

N will be between 1 and 50, inclusive.
L will be between 1 and 50, inclusive.
switches will contain exactly N elements.
Each element of switches will contain exactly L characters.
Each character in switches will be either '0' or '1'.

Examples

3
5
{"01101",
 "10110",
 "01011"}
Returns: "11101"

There are five lightbulbs and three switches: switch X controls bulbs {1, 2, 4}, switch Y controls {0, 2, 3}, and switch Z controls bulbs {1, 3, 4}. Given that we have 3 switches, there are 2^3 = 8 ways to toggle a subset of switches: Toggling just the switch Y gives us the result "10110". Toggling switches X+Y gives "11011" (with bulb 2 burned out). Toggling Y+Z gives "11101" (with bulb 3 burned out). This is the optimal solution. Toggling X+Y+Z gives "10000" (with all four bulbs that are off burned out). For each of the four remaining ways, bulb 0 will not be lit in the end, and therefore none of these is optimal.

10
20
{"00010111011100101010",
 "11110001010110011110",
 "00101010100100000100",
 "11000000111011101000",
 "01100101011001100100",
 "11010010110010000100",
 "01111111011000010001",
 "00001010111010011111",
 "11100011101000011011",
 "10001000011001001111"}
Returns: "11111101000011000110"

1
6
{"101010"}
Returns: "101010"

13
42
{"111100000101100000101010001000010000101011",
 "011010001001100000101000000110001111011110",
 "001101010001100011000100001100001011101001",
 "011110110101000101101110011011011111110110",
 "101011110011110111010010111011001110011011",
 "011001111111111001000001000010100010110011",
 "100100101000101111101100001011111111011111",
 "100111110111011000100101011110110001110001",
 "111110010001110111011011100010000000000100",
 "111000101001011000101001001101111101110110",
 "101110001000001110111111001011101001111001",
 "100100110110010000111100001110100011010101",
 "110011010001100000010001001001111000010111"}
Returns: "111110111111110000010100001000101100001011"

12
50
{"00000000000000000000000000000000000000000000000000", "01111111100011111100011111110001111111000111111110", "01111111100111111110011111111001111111100111111110", "01100000000110000000011000011001100001100000110000", "01100000000110000000011000011001100001100000110000", "01111110000111111100011111111001111111100000110000", "01111110000011111110011111110001111111000000110000", "01100000000000000110011000000001111000000000110000", "01100000000000000110011000000001101100000000110000", "01111111100111111110011000000001100110000000110000", "01111111100011111100011000000001100011100000110000", "00000000000000000000000000000000000000000000000000"}
Returns: "01111111100111111110011111111001111111100111111110"

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

Coding Area

Language: C++17 · define a public class EllysLightbulbs with a public method string getMax(int N, int L, vector<string> switches) · 52 test cases · 2 s / 256 MB per case