## 11572 - Unique Snowflakes

Moderator: Board moderators

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

### 11572 - Unique Snowflakes

Hey! i got AC use a O(nlogn) algorithm.. i want to know if there is a O(N) algorithm for solving this problem ?
electron
cs_lyxab
New poster
Posts: 3
Joined: Sat Sep 20, 2008 6:58 pm

### Re: 11572

Use radix sort if you like...
NeeDay
New poster
Posts: 3
Joined: Mon Feb 16, 2009 10:57 am

### Re: 11572 - Unique Snowflakes

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

### Re: 11572 - Unique Snowflakes

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

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;
}
``````
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

### Re: 11572 - Unique Snowflakes

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 ?
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
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

### Re: 11572 - Unique Snowflakes

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

Code: Select all

``Accepted``
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
Contact:

### Re: 11572 - Unique Snowflakes

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

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

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

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

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

@@@ Jony @@@
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11572 - Unique Snowflakes

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

### Re: 11572 - Unique Snowflakes

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

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

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

Code: Select all

``````i got it..............
``````
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### Re: 11572 - Unique Snowflakes

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

Code: Select all

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

@@@ Jony @@@