Peculiar Partitioning

Anachor Replay of BUET Inter Univ...
Limits 1s, 1.0 GB

You are given an array aa of length nn. You need to find a sub-sequence SS of the array such that gcd(sum(S),sum(S))>1.gcd(sum(S), sum(\overline S) )> 1. In other words, the gcd of sum of elements in SS and sum of elements not in SS is greater than 1. It is also required that both SS and S\overline S are non-empty.


The first line contains an integer, n(2n106)n (2 \leq n \leq 10^6).

The second line contains nn space-separated integers a1,a2,,an(1ai2000)a_1, a_2, \cdots, a_n (1 \leq a_i \leq 2000).


If there is no sub-sequence of the array such that print a single word “No” .

Otherwise, on the first line print a single word “Yes” . On the second the line print a single integer k (1kn1)k \ (1 \leq k \leq n-1), the length of the chosen subsequence. On the third line print kk space seperated distinct integers c1,c2,ck (1cin)c_1, c_2, \cdots c_k\ (1 \leq c_i \leq n), the indices of the elements of the chosen subsequence.

If there are multiple solutions, print any of them. You can print the indices of the chosen subsequence in any order.


6 2 3 5 8
4 2 3

Here a4,a2,a3a_4, a_2, a_3 are the chosen elements. Their sum is 5+2+3=105+2+3=10. The other elements sum to 6+8=146+8=14. Since, gcd(10,14)>1gcd(10, 14) > 1, this is a valid answer.

[1,5][1 , 5], [3,4][3, 4] , [1,2,5,4][1, 2, 5, 4] are also valid subsequences.

1 3

Given a sub-sequence SS of an array aa, S\overline S is the sub-sequence formed by taking all elements in aa and not in SS. For example, given an array a=[10,20,30,40,50]a = [10, 20, 30, 40, 50] and the subsequence S=[20,30,50]S = [20, 30, 50], then S=[10,40]\overline S = [10, 40].


Login to submit.


33% Solution Ratio
AbrarSamitEarliest, 6M ago
AbrarSamitFastest, 0.1s
AbrarSamitLightest, 65 MB
niaj_pialShortest, 1718B
Toph uses cookies. By continuing you agree to our Cookie Policy.