[Solution] Flip Sorting solution codechef

Flip Sorting solution codechef – Chef has a binary string SS of length NN. Chef can perform the following operation on SS any number of times (possibly zero):
  • Choose a number XX (1XN1≤X≤N) that hasn’t been chosen in any previous operation and flip any substring of SS having length XX (i.e. change all 00s to 11s and all 11s to 00s in any substring of SS having length XX).

Flip Sorting solution codechef

Chef wants to sort SS in non-decreasing order using any sequence of operations. Can you help Chef find such a sequence of operations?

If there are multiple answers, print any.

Input Format

  • The first line contains a single integer TT – the number of test cases. Then the test cases follow.
  • The first line of each test case contains an integer NN – the length of the binary string SS.
  • The second line of each test case contains a binary string SS of length NN containing 00s and 11s only.

Output Format

For each test case,

  • Output in the first line KK – the number of operations applied.
  • In each of the following KK lines, output two integers ii and XX – the starting index of the substring selected and the length of the substring. (Note that XX selected should not be used in any of the previous operations)

Flip Sorting solution codechef

  • 1T1001≤T≤100
  • 1N10001≤N≤1000

Sample Input 1 

3
6
110111
9
110110111
5
00111

Sample Output 1 

1
1 2
2
1 2
4 3
0

Flip Sorting solution codechef

Test Case 1: The operations applied are as follows: 11⎯⎯⎯⎯011100011111_0111→000111.

Test Case 2: The operations applied are as follows: 11⎯⎯⎯⎯0110111000110⎯⎯⎯⎯⎯⎯11100000111111_0110111→000110_111→000001111.

Leave a Comment