Equal Number of Prefix Maximums solution codechef

For an array [B1,B2,…,BK][B1,B2,…,BK] of distinct integers, let’s define its weight as the number of its prefix maximums −− that is, of such indexes ii, that Bi>BjBi>Bj for all 1≤j<i1≤j<i.

You are given a permutation [P1,P2,…,PN][P1,P2,…,PN] of integers from 11 to NN. Determine if it’s possible to split it into two nonempty subsequences with equal weights.

Equal Number of Prefix Maximums solution codechef

• The first line will contain TT, the number of test cases. The description of test cases follows.
• The first line of each test case contains a single integer NN −− the length of the permutation.
• The second line of each test case contains NN integers P1,P2,…,PNP1,P2,…,PN −− the permutation.

Output Format

For each test case, if it’s possible to split the permutation into two nonempty subsequences with equal weight, output YES. Otherwise, output NO.

Constraints

• 1≤T≤2⋅1051≤T≤2⋅105.
• 2≤N≤2⋅1052≤N≤2⋅105
• The sum of NN over all test cases does not exceed 2⋅1052⋅105.
• 1≤Pi≤N1≤Pi≤N
• Pi≠PjPi≠Pj for i≠ji≠j

Equal Number of Prefix Maximums solution codechef

5
6
1 2 3 4 5 6
7
1 2 3 4 5 6 7
6
1 4 2 5 3 6
8
5 6 7 8 1 2 3 4
9
5 6 7 8 9 1 2 3 4

Sample Output 1 

YES
NO
YES
YES
NO

Equal Number of Prefix Maximums solution codechef

Explanation of test case 1: We can split the permutation into two subsequences [1,3,4][1,3,4] and [2,5,6][2,5,6], both of which have 33 prefix maximums.

Explanation of test case 2: No matter how we split, both sequences will be increasing, therefore the sum of their weights will be 77, so they can’t be equal.

Explanation of test case 3: One way to split is into [1,4,2][1,4,2] and [5,3,6][5,3,6]. 1,41,4 are prefix maximums of the first sequences, and 5,65,6 of the second one.

Explanation of test case 4: One way to split is into [5,6,7,8][5,6,7,8] and [1,2,3,4][1,2,3,4]. Both have 44 prefix maximums.

Explanation of test case 5: It’s possible to show that the required split does not exist.