HackerEarth October Easy 2021 Editorial Solutions 

Likeable Arrays

Bob and Alice are two friends, they have an array $A$ consisting of $N$ integers, $A_1,A_2,A_3...,A_N$. Alice likes the arrays in which if element $X$ is present it must have exactly $X$ or zero occurrences. So, Bob has decided to convert this array to an array which Alice likes. To do that, he can perform the following two operations:

•         Add an element of any value to array $A$.
•         Remove an element from array A.

Find the minimum number of operations Bob has to perform so that array is liked by Alice.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the number of elements in array $A$.
• The second line of each test case contains $N$ space-separated integers of array $A$.

Output format

Print $T$ lines. For each test case:

• Print a single line indicating the minimum number of operations to be performed.

Constraints

$1\le T\le 20000$

$1\le N\le 200000$

$1\le A_i\le {10}^9\mathrm{\forall }i\in [1,N]$

The sum of $N$ over all test cases does not exceed 200000.

Sample Input

1
5
3 2 3 1 2

Sample Output

1

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

According to the defination: 1 should have exactly one or zero occurence, 2 should have two or zero occurences and 3 should have three or zero occurences.

So for three, we have two options, either we remove both occurences or add one occurence, it will be optimal to add one occurence.

Program Code in C++

1. #include <bits/stdc++.h>
2. using namespace std;
3. int solve(vector<int> A){
4. int ans=0;
5. map<int,int> m;
6. for(int i=0;i<A.size();i++){
7. if(m.find(A[i])==m.end()) m[A[i]]=1;
8. else m[A[i]]++;
9. }
10. for(auto itr:m){
11. if(itr.first==itr.second) continue;
12. else{
13. if(itr.second>itr.first) ans+=(itr.second-itr.first);
14. else ans+=min(itr.second,itr.first-itr.second);
15. }
16. }
17. return ans;
18. }
19.  
20. int main(){
21. int t;
22. cin>>t;
23.  
24. while(t--){
25. int n;
26. cin>>n;
27. vector<int> A(n);
28. for(int i=0;i<n;i++) cin>>A[i];
29. cout<<solve(A)<<endl;
30. }
31. }

Good Strings

There are N binary strings (consisting of 0s and 1s) in a table. A pair of strings is good if there exists at least one character in common in both strings.
Find the number of good pairs of strings.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the number of strings on the table.
• Next $N$ lines of each test case contain the strings present on the table.

Output format

Print $T$ lines. For each test case:

• Print a single line indicating the number of good pairs of strings.

Constraints

$1\le T\le 10000$

$1\le N\le 100000$

$1\le LengthofString\le 5$

The sum of length over all test cases does not exceed 500000.

Sample Input

2
3
11
00
00000
5
01
1111
0001
11
01

Sample Output

1
10

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

First Test Case:   String 2 and 3 have character 0 in common

Second test case: All strings have 1 in common so answer is number of pairs, which is 10

Program Code in C++

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. int32_t main()
5. {
6.  
7. {
8. ios_base::sync_with_stdio(false);
9. cin.tie(NULL);
10. }
11. int t;
12. cin>>t;
13. while(t--)
14. {
15. int n;
16. cin>>n;
17. string arr[n];
18. int all0=0,all1=0;
19. for(int i=0;i<n;i++)
20. {
21. cin>>arr[i];
22. int countzero=0;
23. for(int j=0;j<arr[i].length();j++)
24. {
25. if(arr[i][j]=='0')
26. {
27. countzero++;
28. }
29. }
30. if(countzero==arr[i].length())
31. {
32. all0++;
33. }
34. else if(countzero==0)
35. {
36. all1++;
37. }
38. }
39. int all=all0+all1;
40. int ans=(n*(n-1))/2-(all>=2 ? (all*(all-1))/2 : 0)+(all0>=2 ? (all0*(all0-1))/2 : 0)+(all1>=2 ? (all1*(all1-1))/2 : 0);
41. cout<<ans<<endl;
42. }
43. }

Ternary Palindromes

You are given a ternary string $S$ of length $N$ consisting of 0, 1, and 2. Your task is to determine the number of distinct permutations of $S$ for which satisfies the below condition:

Let $R$ be the permutation of $S$, $R$ is valid if the count of all palindromic substrings (sizes from 1 to $N$) does not exceed $N$.

Input format

• The first line contains an integer denoting the number of test cases $T$.
• The first line of each test case contains a ternary string $S$.

Output format

Print $T$ lines. For each test case:

• Print a single line indicating the number of ways to rearrange S such that the number of palindromes does not exceed $N$.

Constraints

$1\le T\le 20000$

$1\le N\le 200000$

The sum of the length of strings over all test cases does not exceed 200000.

Sample Input

2
201
22011

Sample Output

6
2

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

First test case:  All the permutations of this string are different and valid.
"012","021","102","120","210" and "201".

Second test case: Two permutations are valid.
"12012" and "21021"

In each of the above strings there are only 1 length palindromes, which is equal to length of string.

Program Code in C++

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main() {
4. ios::sync_with_stdio(false);
5. cin.tie(0);
6. int t;
7. cin >> t;
8. vector<string> base{"012", "021", "102", "120", "201", "210"};
9. while (t--) {
10. string s;
11. cin >> s;
12. int n = s.size();
13. vector<string> perms;
14. for (int j = 0; j < 6; ++j) {
15. string str;
16. for (int i = 0; i < n; ++i) {
17. str += base[j];
18. }
19.  
20. str.resize(n);
21. perms.push_back(str);
22. }
23.  
24. int res = 0;
25. for (int j = 0; j < 6; ++j) {
26. int cnt1[3] = {0};
27. int cnt2[3] = {0};
28.  
29. for (int i = 0; i < n; ++i) {
30. cnt1[perms[j][i] - '0']++;
31. cnt2[s[i] - '0']++;
32. }
33.  
34. if (cnt1[0] == cnt2[0] and cnt1[1] == cnt2[1] and cnt1[2] == cnt2[2]) {
35. res++;
36. }
37. }
38.  
39. cout << res << '\n';
40. }
41. }

Deque Sorting

You are given an array $A$ of $N$ distinct integers, your task is to sort the given array using the below operation.

•  Choose any element, take it out of the array without changing the order of other elements, and put it back either in front or back.

Your task is to print the minimum number of operations to achieve this.

Input format

• The first line contains an integer denoting the number of test cases $T$. 
• The first line of each test case contains an integer $N$ denoting the number of elements in array $A$.
• The second line of each test case contains $N$ space-separated integers of array $A$.

Output format

Print $T$ lines. For each test case:

• Print a single line indicating the minimum number of operations to be performed.

Constraints

$1\le T\le 20000$

$1\le N\le 200000$

$1\le A_i\le {10}^9\mathrm{\forall }i\in [1,N]$

All $A_i$ are distinct.

The sum of N over all test cases does not exceed 200000.

Sample Input

1
5
7 3 1 5 4

Sample Output

3

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

[7,3,1,5,4] in the beginning, for optimal conversion:

• Remove 5 and insert in the end  [7,3,1,4,5]
• Remove 7 and insert in the end  [3,1,4,5,7]
• Remove 1 and insert in the beginning [1,3,4,5,7]

There is no way which involves lesser than three steps.

Program Code in C++

1. #include<bits/stdc++.h>
2. using namespace std;
3. typedef long long int ll; 
4. #define pi(x) cout<<x;
5. #define ps(x) cout<<x<<" ";
6. #define pnl(x) cout<<x<<"\n";
7. #define for0(n) for(i=0;i<n;i++)
8. #define for1(n) for(i=1;i<=n;i++)
9. #define m(x) memset(x,0,sizeof x);
10. #define nl cout<<"\n";
11. #define mp make_pair
12. #define pb push_back
13. #define fr first
14. #define se second
15. int main(){
16. ios_base::sync_with_stdio(false);
17. cin.tie(NULL);
18. cout.tie(NULL);
19. ll test,h,p,i,j,xy,flag=0,n,u,count,d,o1=0,o2=0,s,e,l,r,x,y,m,z,max1,x1,y1,k,x2,y2,z1,z2,sum,min1;
20. cin>>test;
21. while(test--){
22. cin>>n;
23. vector<pair<ll,ll>>a(n);
24. for(i=0;i<n;i++){
25. cin>>a[i].first;
26. a[i].second=i;
27. }
28. sort(a.begin(),a.end());
29. max1=1;
30. x1=1;
31. for(i=1;i<n;i++){
32. if(a[i].second>a[i-1].second){
33. x1++;
34. }else{
35. x1=1;
36. }
37. max1=max(max1,x1);
38. }
39. cout<<n-max1<<"\n";
40. }
41. return 0;
42. }