[Solution] Equal Binary Subsequences solution codeforces

Equal Binary Subsequences solution codeforces – Everool has a binary string 𝑠s of length 2𝑛2n. Note that a binary string is a string consisting of only characters 00 and 11. He wants to partition 𝑠s into two disjoint equal subsequences. He needs your help to do it.

Table of Contents

[Solution] Equal Binary Subsequences solution codeforces

You are allowed to do the following operation exactly once.

  • You can choose any subsequence (possibly empty) of 𝑠s and rotate it right by one position.

In other words, you can select a sequence of indices 𝑏1,𝑏2,,𝑏𝑚b1,b2,…,bm, where 1𝑏1<𝑏2<<𝑏𝑚2𝑛1≤b1<b2<…<bm≤2n. After that you simultaneously set

𝑠𝑏1:=𝑠𝑏𝑚,sb1:=sbm,
𝑠𝑏2:=𝑠𝑏1,sb2:=sb1,
,…,
𝑠𝑏𝑚:=𝑠𝑏𝑚1.sbm:=sbm−1.

Can you partition 𝑠s into two disjoint equal subsequences after performing the allowed operation exactly once?

A partition of 𝑠s into two disjoint equal subsequences 𝑠𝑝sp and 𝑠𝑞sq is two increasing arrays of indices 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn and 𝑞1,𝑞2,,𝑞𝑛q1,q2,…,qn, such that each integer from 11 to 2𝑛2n is encountered in either 𝑝p or 𝑞q exactly once, 𝑠𝑝=𝑠𝑝1𝑠𝑝2𝑠𝑝𝑛sp=sp1sp2…spn𝑠𝑞=𝑠𝑞1𝑠𝑞2𝑠𝑞𝑛sq=sq1sq2…sqn, and 𝑠𝑝=𝑠𝑞sp=sq.

If it is not possible to partition after performing any kind of operation, report 1−1.

If it is possible to do the operation and partition 𝑠s into two disjoint subsequences 𝑠𝑝sp and 𝑠𝑞sq, such that 𝑠𝑝=𝑠𝑞sp=sq, print elements of 𝑏b and indices of 𝑠𝑝sp, i. e. the values 𝑝1,𝑝2,,𝑝𝑛p1,p2,…,pn.

[Solution] Equal Binary Subsequences solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1051≤t≤105). Description of the test cases follows.

The first line of each test case contains a single integer 𝑛n (1𝑛1051≤n≤105), where 2𝑛2n is the length of the binary string.

The second line of each test case contains the binary string 𝑠s of length 2𝑛2n.

It is guaranteed that the sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case, follow the following output format.

If there is no solution, print 1−1.

Otherwise,

  • In the first line, print an integer 𝑚m (0𝑚2𝑛0≤m≤2n), followed by 𝑚m distinct indices 𝑏1b1𝑏2b2, …, 𝑏𝑚bm(in increasing order).
  • In the second line, print 𝑛n distinct indices 𝑝1p1𝑝2p2, …, 𝑝𝑛pn (in increasing order).

If there are multiple solutions, print any.

[Solution] Equal Binary Subsequences solution codeforces

input

Copy
4
2
1010
3
100010
2
1111
2
1110
output

Copy
0
1 2
2 3 5
1 2 5
3 2 3 4
1 4
-1

[Solution] Equal Binary Subsequences solution codeforces

In the first test case, 𝑏b is empty. So string 𝑠s is not changed. Now 𝑠𝑝=𝑠1𝑠2=𝟷𝟶sp=s1s2=10, and 𝑠𝑞=𝑠3𝑠4=𝟷𝟶sq=s3s4=10.

In the second test case, 𝑏=[3,4,5]b=[3,4,5]. Initially 𝑠3=𝟶s3=0𝑠4=𝟶s4=0, and 𝑠5=𝟷s5=1. On performing the operation, we simultaneously set 𝑠3=𝟷s3=1𝑠4=𝟶s4=0 and 𝑠5=𝟶s5=0.

So 𝑠s is updated to 101000 on performing the operation.

Now if we take characters at indices [1,2,5][1,2,5] in 𝑠𝑝sp, we get 𝑠1=𝟷𝟶𝟶s1=100. Also characters at indices [3,4,6][3,4,6] are in 𝑠𝑞sq. Thus 𝑠𝑞=100sq=100. We are done as 𝑠𝑝=𝑠𝑞sp=sq.

In fourth test case, it can be proved that it is not possible to partition the string after performing any operation.

 

For Solution

“Click Here”

Leave a Comment