Connection Status:
Competition Arena > BrightLampsRemake

BrightLampsRemake

SRM 705 Sponsored By Blizzard · 2016-12-22 · by cgy4ever

SRM 705 Sponsored By Blizzard · 2016-12-22 · by cgy4ever · Brute Force, Dynamic Programming, Math
Class Name: BrightLampsRemake
Return Type: long[]
Method Name: maxAndCount
Arg Types: (string, vector<string>)
Problem Statement

Problem Statement

This problem has a non-standard time limit: 4 seconds.

There are lots of tasks about lamps and buttons. Today you have to solve another one.

We have m lamps, numbered 0 through m-1. You are given a String init with m characters. The String init describes the initial state of the lamps. If the i-th (0-based) character of init is '1', lamp i is initially turned on. Otherwise, the i-th character of init is '0' which means that lamp i is initially turned off.

In addition to the m lamps there are n buttons, numbered 0 through n-1. Each button is connected to some subset of lamps (possibly none or all of them). You are given the information about the buttons in the String[] buttons. For each i and j, buttons[i][j] is '1' if button i is connected to lamp j, or '0' if they aren't connected.

Pushing a button toggles all lamps that are connected to the button. (I.e., the ones that were on are now off and vice versa.)

You already realized that the order in which you push the buttons does not matter. You also realized that it doesn't make sense to push the same button twice, because that has the same effect as not pushing it at all. Therefore, you have decided that you are going to push each button at most once. This means that there are 2^n ways to push the buttons. For each of those ways we are interested in the number of lamps that would be lit at the end.

Compute two values:
  • X = the largest possible number of lamps that will be turned on after you push some buttons
  • Y = the number of ways in which you can push some buttons so that in the final state exactly X lamps are turned on
Return the long[] {X, Y}. (That is, a long[] of length 2 in which element 0 is X and element 1 is Y.)

Constraints

  • n will be between 1 and 50, inclusive.
  • m will be between 1 and 50, inclusive.
  • init will contain exactly m characters.
  • buttons will contain exactly n elements.
  • Each element in buttons will contain exactly m characters.
  • Each character in init will be '0' or '1'.
  • Each character in buttons will be '0' or '1'.
Examples
0)
"0000"
{"1010", "0100", "0001"}
Returns: {4, 1 }

In the beginning all lamps are off. You can turn them all on by pushing each button once. Thus, it is possible to have X = 4 lamps on. The above way is the only way to achieve this number of lit lamps, hence Y = 1.

1)
"1011"
{"0000", "0000", "0000"}
Returns: {3, 8 }

In the beginning three of the four lamps are turned on. There are three buttons. The buttons don't do anything. Thus, we have X = 3, and each of the Y = 2^3 = 8 ways of pushing the buttons leads to a state in which three lamps are on.

2)
"00000"
{"11000", "01100", "00110", "00011", "10001"}
Returns: {4, 10 }
3)
"10000"
{"11000", "01100", "00110", "00011", "10001"}
Returns: {5, 2 }
4)
"0"
{"0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0",
 "0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0","0"}
Returns: {0, 1125899906842624 }

Watch for overflow.

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

Coding Area

Language: C++17 · define a public class BrightLampsRemake with a public method vector<long long> maxAndCount(string init, vector<string> buttons) · 122 test cases · 2 s / 256 MB per case

Submitting as anonymous