Codeforces Round #634 PROBLEM C

help
1

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;
        	
        	}
        }
2

try using map for count

1 Like
3

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

4

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

5

Initialsing the vector took that much time.

1 Like
6

Use unordered_map

7

See my reply.
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
8

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

9

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.

10

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

11

I tried your code.

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 :sweat_smile:

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";
	}
}
12

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

13

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

14

but it makes searches in constant time

15

Maybe you should read this.

In Short

We always assume hash maps are O (1) per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item only runs into O (1) collisions on average . If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn’t random, especially so if someone is adversarially designing inputs to our code (a.k.a. hacking phase). In particular, if they know our hash function, they can easily generate a large number of different inputs that all collide, thus causing an O(n^2) blow-up.