11572 - Unique Snowflakes

[f74956227]

Hey! i got AC use a O(nlogn) algorithm.. i want to know if there is a O(N) algorithm for solving this problem ?
Could somone tell me please

[cs_lyxab]

Use radix sort if you like...

[NeeDay]

HEY! This is my wrong code and I just can not find what is the matter.
Or... I am not clear about the problem...

Suggestions and some test cases are welcome.

Thanks.

Code: Select all

#include <iostream>
using namespace std;

int main()
{
	int t;
	cin >> t;
	bool * a = new bool[1000000001];
	long n;
	for(int tt = 0; tt <  t; tt++)
	{
		cin >> n;
		long count = 0;
		long snow;
		memset(a,0,sizeof(a));
		int temp = 0;
		for(long i = 0; i < n; i++)
		{
			cin >> snow;
			if(a[snow])
			{
			    memset(a,0,sizeof(a));
                if(temp > count)
                    count = temp;
                temp = 1;
                a[snow] = 1;
                continue;
			}
			else
			{
			    a[snow] = 1;
			    temp ++;
			}
		}
		if(temp > count)
            count = temp;
		cout << count << endl;
	}
	delete a;
	return 0;
}

[Jan]

Code: Select all

bool * a = new bool[1000000001];

1) You are declaring a huge memory locally.
2) 1000000000 byte = 954 MB (almost), the memory limit is 32 MB.

You can use a map instead of the array. Now it takes O(1) to access, but in a map it will take O(log(n)), but still its feasible. Hope these help.

[NeeDay]

Code: Select all

bool * a = new bool[1000000001];

1) You are declaring a huge memory locally.
2) 1000000000 byte = 954 MB (almost), the memory limit is 32 MB.

You can use a map instead of the array. Now it takes O(1) to access, but in a map it will take O(log(n)), but still its feasible. Hope these help.

Thanks.

I decided to use a set instead of the array. But I still got WA.

I guess there are more mistakes, hoping someone could tell me.

Code: Select all

#include <iostream>
#include <set>

using namespace std;

int main()
{
	int t;
	cin >> t;
	set<long> a;
	long n;
	for(int tt = 0; tt <  t; tt++)
	{
		cin >> n;
		long count = 0;
		long snow;
		a.clear();
		int temp = 0;
		pair<set<long>::iterator,bool> insert_OK;
		for(long i = 0; i < n; i++)
		{
			cin >> snow;
			insert_OK = a.insert(snow);
			if(insert_OK.second)
                temp++;
            else
			{
			    a.clear();
                if(temp > count)
                    count = temp;
                temp = 1;
                a.insert(snow);
                continue;
			}
		}
		if(temp > count)
            count = temp;
		cout << count << endl;
	}
	return 0;
}

[andmej]

Hey! i got AC use a O(nlogn) algorithm.. i want to know if there is a O(N) algorithm for solving this problem ?
Could somone tell me please

I solved it in O(n log n) too. It runs in ~0.7 seconds, but Rio solved it in 0.09 seconds, which makes me believe an O(n) solution does exist.

[vahid sanei]

PLZ HELP ME
I get Wrong ans
here is my code :

Code: Select all

Accepted

[Jan]

Try the following case..

Input:

Code: Select all

1

12
7
4
0
9
4
8
8
2
4
5
5
1

Output:

Code: Select all

4

Hope it helps.

[saiful_sust]

PLZ HELP ME!!!!!!!!!!!!

i m getting WA..................

Code: Select all

code remove.........

[sapnil]

your code do not pass the sample input.

[kbr_iut]

At the contest time i got WA.
I used map.
first i continuously took input.whenever i got an identical number then i make the map empty and took the number unique snowflakes.
In this way i found out the highest number of unique snowflakes.

Is my method wrong?

[Moshiur Rahman]

I am having an impression that, you did the same mistake as I did. At first, I misunderstood the problem statement.
The problem asks to find the highest number of unique snowflakes that comes one after another, not just the number of total unique snowflakes. It can be restated as follows:

Given a sequence. Find the length of the longest continuous sub sequence with no repetitions.

For this input :

Code: Select all

1

5

1
2
1
1
3

the correct answer is:

Code: Select all

2

not 3. However, I used map in my AC solution, but my runtime is too high(1.230 sec). My algorithm is O(nlogn).

[saiful_sust]

PLZ HELP ME!!!!!!!!!!!!
i try some input all are ok..
BUT
i m getting WA..................

Code: Select all

i got it..............

[kbr_iut]

thanx Jony vi(sapnil_sust) and Moshiur Rahman.
but this time I cant pass TL.
can u pliz again help me?

Code: Select all

#include<iostream>
#include<map>
using namespace std;
int num,t,i,j,n,tem,ar[100010];
int main(){
#ifndef ONLINE_JUDGE
	freopen("1.txt","r",stdin);
#endif
	scanf("%d",&t);
	while(t--){
		num=tem=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)scanf("%d",&ar[i]);
		for(i=0;i<n;i++){
			j=i;
			map<int,int>mp;
			while(j<n){
				if(mp[ar[j]]++)break;
				tem++;
				j++;
			}
			if(num<tem)num=tem;
			tem=0;
		}
		printf("%d\n",num);
	}
	return 0;
}

[sapnil]

Code: Select all

1
6
1 2 3 2 4 5

Output is:4