# Codeforces Round #634 PROBLEM C

Problem Link : Problem - C - Codeforces

My Solution is gives TLE although its O(n) . May be I’m missing some case.
I tried comparing outputs from solution from editorial and my code, i am getting correct answer.

UPDATE: I corrected my code based on the suggestion in comments.

Key Takings:

• Initializing vector (200010,0) took long, instead i could have used vector (n+1,0) , or map which worked too.

My Code :

``````<code>
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,val;
cin>>t;
while(t--){
cin>>n;
int distinct=0,max_same = -1;
vector<int> count(200010,0);
for(int i=0;i<n;i++){
cin>>val;
if(count[val] == 0) distinct++;
count[val]++;
max_same = max(count[val] , max_same);
}
(max_same == distinct) ? cout<<max_same-1<<endl : cout<<min(max_same,distinct)<<endl;

}
}``````

try using map for count

1 Like

No your solution is not O(n) you solution takes time T*(max(n,200010));
if T is large your solution is most likely to fail

Thanks, it worked, Just a doubt why doesn’t vector works. I mean accessing count[val] will take O(1) isnt’t it?

Initialsing the vector took that much time.

1 Like

Use unordered_map

It was mentioned that that t can be upto 10^4;a
And every time you initialize that vector of length 2*10^5;
so it is not possible.
try taking n+1 in place of 200100

1 Like

Got it.Thanks. I was struggling to find reason for TLE, when posted doubt on codeforces got 8 downvotes.

TLE maybe because of initialization of a vector of size 200000 but even after fixing that your code will give WA. This is because whenever max_same == n , you are printing 0 .
Consider a case 1 1 1. (Team 1 : ‘1’ , Team 2 : ‘1’) so the max size of team will be one.

@rishav_iitkgp yeah, i had removed that line. but while posting here i pasted old code.
Using Map helped.

For TLE issue rather than unnecessarily declaring `count` of 2.10^5 size, declare it of size N.

I still though there were some issues with code and edited it to this, I didn’t do much testing, just edited a little and tried resubmitting till it got AC My Code
``````#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,val;
cin>>t;
while(t--){
cin>>n;
int distinct=0,max_same = 0;
vector<int> count(n+1,0);
for(int i=0;i<n;i++){
cin>>val;
if(count[val] == 0) distinct++;
count[val]++;
}
for(int val = 1; val <= n; ++val){
max_same = max({min(count[val]-1,distinct),min(count[val],distinct-1), max_same});
}
cout << max_same << "\n";
}
}
``````

use map for finding the max. freq and set for find the total distinct elements

Never use unordered_map in codeforces otherwise, get ready to be hacked (for TLE).

but it makes searches in constant time