ArtShift
TCO11 Round 3 · 2011-05-07 · by vexorian
TCO11 Round 3 · 2011-05-07 · by vexorian · Brute Force, Math
Problem Statement
Problem Statement
Let S[0], S[1], ..., S[N-1] be a sequence of colors, each of which is either black or white. An art shift is a permutation (P[0], P[1], ..., P[N-1]) of integers between 0 and N-1, inclusive. It can be used to create a new sequence from the given one. For each i, the integer P[i] represents the position of the character of the previous sequence that will appear in the i-th position of the new sequence. In other words, if an art shift P is applied to a sequence S, the resulting sequence is (S[P[0]], S[P[1]], ..., S[P[N-1]]).
Given a sequence S and an art shift P, we can obtain new sequences, where each next sequence is obtained from the previous one by applying the art shift P. All these sequences are said to be reachable from S using P.
For simplicity, a sequence of N colors can be represented as aString containing N characters, where the i-th character is 'B' if the i-th color in the sequence is black and 'W' if the i-th color is white. Consider an example, where the initial sequence is "WBWWB" and the art shift P = {1,0,2,4,3}. Then after the first application of P we get "BWWBW", after the second application we get "WBWWB" and after the next applications we get "BWWBW", "WBWWB", "BWWBW" and so on. Overall in this case there are 2 different sequences reachable from the initial sequence using the given art shift.
Given an initial sequence, return the maximum number of different sequences that are reachable from it by using a single art shift.
Given a sequence S and an art shift P, we can obtain new sequences, where each next sequence is obtained from the previous one by applying the art shift P. All these sequences are said to be reachable from S using P.
For simplicity, a sequence of N colors can be represented as a
Given an initial sequence, return the maximum number of different sequences that are reachable from it by using a single art shift.
Constraints
- sequence will contain betweeen 1 and 30 characters, inclusive.
- Each character in sequence will be 'B' or 'W'.
Examples
0)
"BW" Returns: 2
We can use an art shift of {1,0} to reach "WB" and then "BW" again for a total of two different reachable sequences.
1)
"BBBWBBB" Returns: 7
2)
"BWBWB" Returns: 6
A possible art shift that allows us to reach 6 different sequences is: {1,2,0,4,3}.
3)
"WWWWWWWWW" Returns: 1
It does not matter what art shift we use; the sequence will always stay the same.
4)
"BBBWBBBBBWWW" Returns: 60
Submissions are judged against all 214 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ArtShift with a public method int maxShifts(string sequence) · 214 test cases · 2 s / 256 MB per case