Split AND Sum solution codechef

You are given an array [A1,…,AN][A1,…,AN]. You want to split it into several (≥2)(≥2) subarrays so that the following condition holds:

• Calculate the sum of elements in each subarray. Then, the AND of all these sums is nonzero, where AND denotes the bitwise AND operation.

Determine if it’s possible. If it’s possible, find one such split. You don’t have to minimize the number of subarrays.

Input Format

Split AND Sum solution codechef

• The first line of the input contains a single integer TT −− the number of test cases. The description of the test cases follows.
• The first line of each test case contains a single integer NN −− the length of the array.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, if it’s not possible to split the array so that the condition from the statement holds, output NO.

Otherwise, output YES. In the next line, output KK (2≤K≤N2≤K≤N) −− the number of subarrays you are splitting into.

In the ii-th of the next KK lines, output two integers Li,RiLi,Ri (1≤Li≤Ri≤N1≤Li≤Ri≤N), where [Li,Ri][Li,Ri] denotes the ii-th subarray.

Each number from 11 to NN has to appear in exactly one of the segments [Li,Ri][Li,Ri].

You can output each letter in either uppercase or lowercase. You can output any solution. You don’t have to minimize KK.

Constraints

• 1≤T≤1051≤T≤105
• 2≤N≤1052≤N≤105
• 0≤Ai<2300≤Ai<230
• Sum of NN over all test cases doesn’t exceed 2⋅1052⋅105

Sample Input 1 

5
4
1 9 8 4
3
0 0 0
2
16 15
5
1 2 6 24 120
7
8 6 0 16 24 0 8

Sample Output 1

Split AND Sum solution codechef

YES
2
2 4
1 1
NO
NO
YES
2
1 2
3 5
YES
3
1 1
6 7
2 5

Explanation

Split AND Sum solution codechef

Test case 11: You can split the array into two subarrays [2,4][2,4] and [1,1][1,1]. They have sums 2121 and 11 correspondingly, whose AND is 11.

Test case 44: You can split the array into two subarrays [1,2][1,2] and [3,5][3,5]. They have sums 33 and 150150 correspondingly, whose AND is 22.

Test case 55: You can split the array into three subarrays [1,1][1,1], [6,7][6,7], [2,5][2,5]. They have sums 88, 88, 4646, whose AND is 88.

It’s possible to show that it’s impossible to split in the desired way in the second and the third test cases.

Solution

“Click Here“