Few Different Elements SOLUTION FEWDIFF

Few Different Elements SOLUTION FEWDIFF

Let’s call a sequence with length K good if there are at most K2+1 distinct elements in it. For example, the sequence (3,3,2,1,3) is good, since it contains 3≤52+1 distinct elements, while the sequence (1,4,8,8,2) is not good, since it contains 4>52+1 distinct elements.
 
You are given a sequence of integers A1,A2,…,AN. You may perform any number of operations (including zero) on this sequence. In one operation, you should choose one element of the sequence and replace it by any integer you choose. You want all contiguous subsequences of the resulting sequence to be good. What is the smallest number of operations you need to perform to achieve this?
 
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer ― the smallest number of operations needed to make all contiguous subsequences good.
 
Constraints
1≤T≤40
1≤N≤105
1≤Ai≤109 for each valid i
the sum of N over all test cases does not exceed 5⋅105
Subtasks
Subtask #1 (20 points): the sum of N over all test cases does not exceed 200
Subtask #2 (30 points): the sum of N over all test cases does not exceed 5,000
Subtask #3 (50 points): original constraints
 
Example Input
3
6
1 1 1 2 2 2
4
1 100 10000 1000000
5
1 2 3 2 1
Example Output
0
1
1
Explanation
Example case 1: All contiguous subsequences are already good.
 
Example case 2: For example, (1,100,10000) is not good. It is enough to change the sequence to (1,100,100,1000000), though.
 
Example case 3: For example, (1,2,3) is not good. It is enough to change the sequence to (1,2,1,2,1).
 

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment