[Solution] PerMEXuation solution codechef

PerMEXuation solution codechef – You are given an integer NN and a (00-indexed) binary string AA having length N+1N+1.

Find any permutation PP of 0,1,2,...,N10,1,2,…,N−1 (or determine that it does not exist) that satisfies the following conditions for all ii (0iN0≤i≤N):

  • if Ai=0Ai=0: No contiguous segment of PP has mexmex equal to ii
  • if Ai=1Ai=1: There exists at least one contiguous segment of PP that has mexmex equal to ii

PerMEXuation solution codechef

If multiple permutations exist that satisfy the given conditions, print any.

Note: mexmex of a segment is the smallest non-negative number that does not occur in that segment.

Input Format

  • The first line contains the number of test cases TT. Description of the test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line of each test case contains the binary string AA of length N+1N+1.

Output Format

For each test case print :

  • YesYes if there exists a permutation PP that satisfies the conditions described in the statement, followed by the permutation PP in the next line (If multiple permutations exist that satisfy the given conditions, print any).
  • NoNo otherwise.

You may print each character of YesYes and NoNo in uppercase or lowercase (for example, yesyesyEsyEsYESYES will be considered identical).

PerMEXuation solution codechef

  • 1T1041≤T≤104
  • 2N31052≤N≤3⋅105
  • |A|=N+1|A|=N+1
  • It is guaranteed that the sum of NN over all test cases does not exceed 31053⋅105.

Sample Input 1 

4
2
111
5
110100
5
110101
7
11100111

Sample Output 1 

Yes
0 1
No
Yes
0 2 1 4 3
Yes
0 1 3 4 2 5 6

PerMEXuation solution codechef

Test case-1: One of the possible permutations satisfying the given conditions is [0,10,1] because:

  • mex([1])=0mex([1])=0. Therefore the condition is satisfied for i=0i=0.
  • mex([0])=1mex([0])=1. Therefore the condition is satisfied for i=1i=1.
  • mex([0,1])=2mex([0,1])=2. Therefore the condition is satisfied for i=2i=2.

Test case-2: It can be proven that no permutation exists that satisfies the given conditions.

Test case-3: One of the possible permutations satisfying the given conditions is [0,2,1,4,30,2,1,4,3] because:

  • mex([2])=0mex([2])=0. Therefore the condition is satisfied for i=0i=0.
  • mex([0,2])=1mex([0,2])=1. Therefore the condition is satisfied for i=1i=1.
  • There does not exist any segment with mex=2mex=2. Therefore the condition is satisfied for i=2i=2.
  • mex([0,2,1])=3mex([0,2,1])=3. Therefore the condition is satisfied for i=3i=3.
  • There does not exist any segment with mex=4mex=4. Therefore the condition is satisfied for i=4i=4.
  • mex([0,2,1,4,3])=5mex([0,2,1,4,3])=5. Therefore the condition is satisfied for i=5i=5.

Leave a Comment