Connection Status:
Competition Arena > FourLamps

FourLamps

TCO17 Round 2A · 2017-03-31 · by cgy4ever

TCO17 Round 2A · 2017-03-31 · by cgy4ever · Dynamic Programming
Class Name: FourLamps
Return Type: long
Method Name: count
Arg Types: (string, int)
Problem Statement

Problem Statement

Fox Ciel has n lamps. The lamps are arranged in a row from the left to the right, and they are numbered 0 through n-1 in that order. You are given a String init with n characters that describes the initial state of the lamps: init[i] is '1' if lamp i is initially turned on, or '0' if it is initially turned off.

You are also given an int k. Below we describe an operation. Ciel can use that operation at most k times. Compute and return the number of different final states she can obtain. (Two states of lamps are different if there is a lamp that is on in one state but off in the other. The initial state is always one of the possible final states.)

The operation looks as follows:
  1. Ciel chooses four consecutive lamps such that either exactly one of them is on, or exactly one of them is off. (If there is no such group of lamps, Ciel cannot perform any more operations.)
  2. Ciel divides all lamps into a left part and a right part so that the division point is in the middle of the four lamps chosen in the previous step. In other words, if the four chosen lamps are x, x+1, x+2, x+3, the left part is {0, 1, ..., x+1} and the right part is {x+2, ..., n-2, n-1}.
  3. Ciel chooses either the left part or the right part.
  4. Ciel toggles all lamps in the chosen part. (Toggling a lamp means switching it to the opposite state.)

Constraints

  • init will contain between 4 and 50 characters, inclusive.
  • Each character in init will be '0' or '1'.
  • k will be between 1 and 1,000,000,000, inclusive.
Examples
0)
"0001"
2
Returns: 4

As there are only four lamps, there is only one group of four consecutive lamps. If these four lamps satisfy the constraint, the left part will be lamps {0,1} and the right part will be lamps {2,3}. If Ciel performs zero operations, the only possible final state is the initial state "0001". If Ciel performs one operation, she can either toggle the left part or the right part. Toggling the left part produces the state "1101", toggling the right part produces the state "0010". Note that both states produced by the first operation still have the property that enables us to do the next operation: exactly one of the four lamps is off in "1101", and exactly one of them is on in "0010". What states can we reach by performing two operations? Toggling the left part and then the left part again will bring us back to "0001". Toggling the right part twice has the same effect. Toggling the left part and then the right part produces the final state "1110". Toggling the right half and then the left half leads to that state as well. In total there are four possible final states: "0001", "1101", "0010", "1110".

1)
"0001"
1000000000
Returns: 4

In the previous scenario increasing k to 10^9 does not change the answer. The following operations won't produce any new states of the lamps.

2)
"1010"
100
Returns: 1

This time Ciel cannot make any operation because there are no four consecutive lamps with the required property. Thus, the only possible final state is the initial state.

3)
"000111"
3
Returns: 12

These are the states we can get: "000111" "110111" "001000" "111011" "000100" "111000" "001111" "110000" "001011" "110100" "000011" "111100"

4)
"00000010000"
5
Returns: 58
5)
"10101100101010001011000100101000100001101"
58
Returns: 100256132848

Watch for overflow.

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

Coding Area

Language: C++17 · define a public class FourLamps with a public method long long count(string init, int k) · 113 test cases · 2 s / 256 MB per case

Submitting as anonymous