### 11572 - Unique Snowflakes

Posted:

**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 ?

Could somone tell me please

Could somone tell me please

The Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=50&t=42609

Page **1** of **3**

Posted: **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 ?

Could somone tell me please

Could somone tell me please

Posted: **Sun Feb 15, 2009 5:42 pm**

Use radix sort if you like...

Posted: **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.

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

Posted: **Mon Feb 16, 2009 12:35 pm**

Code: Select all

`bool * a = new bool[1000000001];`

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.

Posted: **Tue Feb 17, 2009 7:03 am**

Thanks.Jan wrote:1) You are declaring a huge memory locally.Code: Select all

`bool * a = new bool[1000000001];`

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.

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

Posted: **Tue Feb 17, 2009 8:05 pm**

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

Could somone tell me please

Posted: **Fri Feb 20, 2009 2:07 pm**

Posted: **Fri Feb 20, 2009 10:25 pm**

Try the following case..

**Input:**
**Output:**
Hope it helps.

Code: Select all

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

Code: Select all

`4`

Posted: **Sun Feb 22, 2009 1:30 pm**

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

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

Code: Select all

```
code remove.........
```

Posted: **Mon Feb 23, 2009 3:40 pm**

Posted: **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?

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?

Posted: **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 :
the correct answer is:
not **3**. However, I used map in my AC solution, but my runtime is too high(1.230 sec). My algorithm is O(nlogn).

The problem asks to find the highest number of unique snowflakes that comes

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

For this input :

Code: Select all

```
1
5
1
2
1
1
3
```

Code: Select all

```
2
```

Posted: **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..................Code: Select all

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

Posted: **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?

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

Posted: **Tue Feb 24, 2009 5:42 pm**

Code: Select all

```
1
6
1 2 3 2 4 5
```