List of Lists LISTLIST Solution Codechef

List of Lists LISTLIST Solution

You are given a positive integer NN and an array AA of size NN. There are NN lists L1,L2…LNL1,L2…LN. Initially, Li=[Ai]Li=[Ai].

You can perform the following operation any number of times as long as there are at least 22 lists:

  • Select 22 (non-empty) lists LiLi and LjLj (i≠ji≠j)
  • Append LjLj to LiLi and remove the list LjLj. Note that this means LjLj cannot be chosen in any future operation.

Find the minimum number of operations required to obtain a set of lists that satisfies the following conditions:

  • The first element and last element of each list are equal.
  • The first element of all the lists is the same.

Print −1−1 if it is not possible to achieve this via any sequence of operations.

Input Format

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

Output Format

For each test case, print a single line containing one integer: the minimum number of operations required to obtain an array of lists that satisfies the given conditions.

Print −1−1 if it is impossible to achieve such an array of lists.

Constraints

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

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1 

3
1
1
2
1 2
3
1 1 2

Sample Output 1 

0
-1
2

Explanation

Test case 11: There is only one list [1][1], and it trivially satisfies the condition so no operations are required.

Test case 22: There are only 22 ways to do an operation – either take list [1][1] and append it to list [2][2] or take list [2][2] and append it to list [1][1]. In both cases, it is not possible to satisfy both given conditions at the same time. Hence, the answer is −1−1.

Test case 33: Here is one possible order of operations:

  • Select the 33rd list [2][2] and append it to the 11st list [1][1].
  • Then, select the 22nd list [1][1] and append it to the 11st list [1,2][1,2].

Finally, we are left with the single list [1,2,1][1,2,1] which satisfies the given conditions. It can be verified that it is impossible to do this using less than 22 operations.

SOLUTION

Program Python: List of Lists LISTLIST Solution in Python

from collections import Counter
for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    c = Counter(l)
    x = c.most_common(1)[0][1]
    #print(x)
    if n == 1 or x==len(l):
        print(0)
    elif n>=2 and x<=1:
        print(-1)
    else:
        print(len(l)-x+1)

Program C++: List of Lists LISTLIST Solution in C++

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        
        int a[n];
        for(int i = 0; i < n; i++)
        {
            cin>>a[i];
        }
        
        int mx = 1;
        int c = 1;
        sort(a,a+n);
        for(int i = 1; i < n; i++)
        {
            if(a[i] == a[i-1])
            {
                c++;
                mx = max(mx, c);
            }
            else{
                c=1;
            }
        }
        if(n==mx){
            cout<<0<<endl;
            continue;
        }
        if(mx==1){
            cout<<-1<<endl;
            continue;
        }
        cout<<(n-mx)+1<<endl;

    }
    return 0;
}

December Long Challenge 2021 Solution

Leave a Comment

5 × five =