11572 - Unique Snowflakes

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

11572 - Unique Snowflakes

Post by f74956227 » Sun Feb 15, 2009 1:44 am

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
electron

cs_lyxab
New poster
Posts: 3
Joined: Sat Sep 20, 2008 6:58 pm

Re: 11572

Post by cs_lyxab » Sun Feb 15, 2009 5:42 pm

Use radix sort if you like...

NeeDay
New poster
Posts: 3
Joined: Mon Feb 16, 2009 10:57 am

Re: 11572 - Unique Snowflakes

Post by NeeDay » Mon Feb 16, 2009 11:05 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11572 - Unique Snowflakes

Post by Jan » Mon Feb 16, 2009 12:35 pm

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.
Ami ekhono shopno dekhi...
HomePage

NeeDay
New poster
Posts: 3
Joined: Mon Feb 16, 2009 10:57 am

Re: 11572 - Unique Snowflakes

Post by NeeDay » Tue Feb 17, 2009 7:03 am

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

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11572 - Unique Snowflakes

Post by andmej » Tue Feb 17, 2009 8:05 pm

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.
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11572 - Unique Snowflakes

Post by vahid sanei » Fri Feb 20, 2009 2:07 pm

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

Code: Select all

Accepted
:oops:
Last edited by vahid sanei on Tue Dec 29, 2009 12:02 am, edited 1 time in total.
Impossible says I`m possible

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11572 - Unique Snowflakes

Post by Jan » Fri Feb 20, 2009 10:25 pm

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.
Ami ekhono shopno dekhi...
HomePage

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11572 - Unique Snowflakes

Post by saiful_sust » Sun Feb 22, 2009 1:30 pm

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

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

Code: Select all

code remove.........
Last edited by saiful_sust on Tue Feb 24, 2009 5:52 am, edited 1 time in total.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11572 - Unique Snowflakes

Post by sapnil » Mon Feb 23, 2009 3:40 pm

your code do not pass the sample input.
"Dream Is The Key To Success"

@@@ Jony @@@

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11572 - Unique Snowflakes

Post by kbr_iut » Mon Feb 23, 2009 6:39 pm

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?
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Moshiur Rahman
New poster
Posts: 13
Joined: Mon Sep 08, 2008 6:57 pm
Location: State University of Bangladesh

Re: 11572 - Unique Snowflakes

Post by Moshiur Rahman » Mon Feb 23, 2009 8:08 pm

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).
Never think too hard, let ideas come to you...

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 11572 - Unique Snowflakes

Post by saiful_sust » Tue Feb 24, 2009 5:04 am

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..............

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11572 - Unique Snowflakes

Post by kbr_iut » Tue Feb 24, 2009 5:25 pm

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;
}
Last edited by kbr_iut on Tue Feb 24, 2009 6:18 pm, edited 3 times in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11572 - Unique Snowflakes

Post by sapnil » Tue Feb 24, 2009 5:42 pm

Code: Select all

1
6
1 2 3 2 4 5
Output is:4
"Dream Is The Key To Success"

@@@ Jony @@@

Post Reply

Return to “Volume 115 (11500-11599)”