01 Subsequence solution codechef

01 Subsequence solution codechef

You are handed a binary string SS, but not in any ordinary form. Instead of being directly given the value of SS, you are given an array CC of size NN representing the 01-compression representation of SS. This means SS first contains C1C1 00 characters, then C2C2 11 characters, then C3C3 00 characters, and so on. For example, the array C=[2,3,4,3]C=[2,3,4,3] corresponds with the binary string 001110000111001110000111.

01 Subsequence solution codechef

You are allowed to modify SS by swapping elements of CC. More specifically, you are allowed to swap CiCi and CjCj as long as CiCi and CjCj both encodes blocks of the same character. For example, from C=[2,3,4,3]C=[2,3,4,3], you can swap C1C1 and C3C3 because both of them encode blocks of 00‘s, turning CC to [4,3,2,3][4,3,2,3] and SS to 000011100111000011100111. However, you cannot swap C1C1 and C2C2 because C1C1 encodes a block of 00‘s, while C2C2 encodes a block of 11s.

Perform the swapping operation in any way as many times as you want (including zero times) so that the final string SS has as many 0101 subsequences as possible. As a reminder, a subsequence of a string is a sequence that can be derived by deleting zero or more characters without changing the order of the remaining characters.

You need to find any optimal final array CC, for which the number of 0101 subsequence will be the largest possible.

Input Format

01 Subsequence solution codechef

  • The first line contains TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer NN – the size of the array CC.
  • The second line of each test case contains NN integers C1,C2,,CNC1,C2,…,CN – the 0101-compression representation of SS.

Output Format

01 Subsequence solution codechef

For each test case, output two lines: the first line contains NN integers representing the optimal array CC, and the second line contains the maximum number of 0101 subsequences.

Constraints

  • 1T10001≤T≤1000
  • 1N1001≤N≤100
  • 1Ci10001≤Ci≤1000

Sample Input 1

01 Subsequence solution codechef

1
4
2 3 4 3

Sample Output 1

01 Subsequence solution codechef

4 3 2 3
30

Explanation

  • Test case 11: C=[2,3,4,3]C=[2,3,4,3], which means SS corresponds to 001110000111001110000111. The optimal list of operations is to only swap C1C1 and C3C3, resulting in C=[4,3,2,3]C=[4,3,2,3] and S=S= 000011100111000011100111, which has 3030 subsequences of 0101.
  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.