Insider Subsequences solution codechef

Insider Subsequences solution codechef

You are given an array AA with NN positive integers.

An xx-insider of this array is a subsequence of AA such that xx is strictly in between any two consecutive elements of the subsequence.

More formally, a subsequence S=[s0,s1,sk1]S=[s0,s1,…sk−1] of the array AA is an xx-insider if for every integer ii such that 1ik11≤i≤k−1, either

  • si1<x<sisi−1<x<si or
  • si1>x>sisi−1>x>si

    Insider Subsequences solution codechef

For example, for the array [1,4,2,4][1,4,2,4], the subsequence [1,4,2][1,4,2] is a 33-insider because 1<3<41<3<4 and 4>3>24>3>2. The subsequence [1,2][1,2] is not an xx-insider for any integer xx. The subsequence [1,4][1,4] is a 22-insider as well as a 33-insider.

Let mkmk be the smallest integer such that AA contains an mkmk-insider of length exactly kk. If such an integer does not exist then mk=1mk=−1.

Similarly, let MkMk be the largest integer such that AA contains an MkMk-insider of length exactly kk. If such an integer does not exist then Mk=1Mk=−1.

Find m2,m3,mNm2,m3,…mN and M2,M3,MNM2,M3,…MN.

Input Format

Insider Subsequences solution codechef

  • The first line contains an integer TT, the number of testcases. The description of the TT testcases follows.
  • Each testcase consists of two lines.
  • The first line contains a single integer, NN, the size of the array AA.
  • The second line contains NN space-separated integers, A1,A2,ANA1,A2,…AN, the elements of the array AA.

Output Format

  • For each testcase print two lines.
  • In the first line print N1N−1 space separated integers, the values of m2,m3,mNm2,m3,…mN respectively.
  • In the second line print N1N−1 space separated integers, the values of M2,M3,MNM2,M3,…MN respectively.


Insider Subsequences solution codechef

  • 1T1051≤T≤105
  • 2N1052≤N≤105
  • sum of NN over all testcases 2105≤2⋅105
  • 1Ai1091≤Ai≤109 for all valid ii

Sample Input 1

Insider Subsequences solution codechef

1 2 4 1 5
1 1 1
3 2 1

Sample Output 1 

2 2 2 -1
4 3 3 -1
-1 -1
-1 -1
2 -1
2 -1


Insider Subsequences solution codechef

Test Case 1: The given array is [1,2,4,1,5][1,2,4,1,5].

Insiders of length 22: The only subsequences of length 22 that are xx-insiders for integer values of xx are [1,4],[1,5],[4,1],[2,4],[2,5][1,4],[1,5],[4,1],[2,4],[2,5]. The subsequences [1,4],[1,5],[4,1][1,4],[1,5],[4,1] are 22-insiders. All of them are 33-insiders. The subsequence [2,5][2,5] is also a 44-insider. Thus m2=2m2=2 and M2=4M2=4.

Insiders of length 33: The only subsequence of length 33 that is an xx-insider for some integer xx is [1,4,1][1,4,1], which is clearly both a 22-insider as well as a 33-insider. Thus m3=2m3=2 and M3=3M3=3.

Insiders of length 44: The only subsequence of length 44 that is an xx-insider for some integer xx is [1,4,1,5][1,4,1,5], which is clearly both a 22-insider as well as a 33-insider. Thus m4=2m4=2 and M4=3M4=3.

Insiders of length 55: The only subsequence of length 55 is the array AA itself, which is not an xx-insider for any integer value of xx. Thus m5=M5=1m5=M5=−1.

Hence the answers for this testcase are m=[2,2,2,1]m=[2,2,2,−1] and M=[4,3,3,1]M=[4,3,3,−1].

Test Case 2: The given array is [1,1,1][1,1,1]. Since all elements are equal, none of the subsequences of this array are xx-insiders (for any integer xx). Hence the answers are m=[1,1]m=[−1,−1] and M=[1,1]M=[−1,−1].

Test Case 3: The only subsequence (of length at least 22) that is an xx-insider (for integer values of xx) is [3,1][3,1] which is a 22−insider. Hence the answers are m=[2,1]m=[2,−1] and M=[2,1]M=[2,−1].

Leave a Comment