Page Contents
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
- List of Lists LISTLIST Solution Codechef
- Valleys and Hills VANDH Solution Codechef
- Rock Paper Scissors ROPASCI Solution Codechef
- Squares Counting GRIDSQRS Solution Codechef
- Pyramid Traversal PYRAMIDMOVES Solution Codechef
- Increasing String INCREAST Solution Codechef
- Utkarsh and Placement tests UTKPLC Solution Codechef
- Check Mate CHECKMATE Solution Codechef