Page 1 of 3

11572 - Unique Snowflakes

Posted: Sun Feb 15, 2009 1:44 am
by 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 :o ?
Could somone tell me please

Re: 11572

Posted: Sun Feb 15, 2009 5:42 pm
by cs_lyxab
Use radix sort if you like...

Re: 11572 - Unique Snowflakes

Posted: Mon Feb 16, 2009 11:05 am
by 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;
}

Re: 11572 - Unique Snowflakes

Posted: Mon Feb 16, 2009 12:35 pm
by 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.

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 17, 2009 7:03 am
by NeeDay
Jan wrote:

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

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 17, 2009 8:05 pm
by andmej
f74956227 wrote:Hey! i got AC use a O(nlogn) algorithm.. i want to know if there is a O(N) algorithm for solving this problem :o ?
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.

Re: 11572 - Unique Snowflakes

Posted: Fri Feb 20, 2009 2:07 pm
by vahid sanei
PLZ HELP ME
I get Wrong ans
here is my code :

Code: Select all

Accepted
:oops:

Re: 11572 - Unique Snowflakes

Posted: Fri Feb 20, 2009 10:25 pm
by 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.

Re: 11572 - Unique Snowflakes

Posted: Sun Feb 22, 2009 1:30 pm
by saiful_sust
PLZ HELP ME!!!!!!!!!!!!

i m getting WA.................. :oops: :oops: :oops: :oops: :oops:

Code: Select all

code remove.........

Re: 11572 - Unique Snowflakes

Posted: Mon Feb 23, 2009 3:40 pm
by sapnil
your code do not pass the sample input.

Re: 11572 - Unique Snowflakes

Posted: Mon Feb 23, 2009 6:39 pm
by 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?

Re: 11572 - Unique Snowflakes

Posted: Mon Feb 23, 2009 8:08 pm
by 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).

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 5:04 am
by saiful_sust
saiful_sust wrote:
PLZ HELP ME!!!!!!!!!!!!
i try some input all are ok..
BUT
i m getting WA.................. :oops: :oops: :oops: :oops: :oops:

Code: Select all

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

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 5:25 pm
by 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;
}

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 5:42 pm
by sapnil

Code: Select all

1
6
1 2 3 2 4 5
Output is:4