11572  Unique Snowflakes
Moderator: Board moderators
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 ?
Could somone tell me please
Could somone tell me please
electron
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.
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
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.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 11572  Unique Snowflakes
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;
}
Re: 11572  Unique Snowflakes
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
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.
Are you dreaming right now?
http://www.dreamviews.com
Are you dreaming right now?
http://www.dreamviews.com

 Learning poster
 Posts: 84
 Joined: Fri Jan 09, 2009 4:37 pm
 Location: IRAN
Re: 11572  Unique Snowflakes
Last edited by vahid sanei on Tue Dec 29, 2009 12:02 am, edited 1 time in total.
Impossible says I`m possible
Re: 11572  Unique Snowflakes
Try the following case..
Input:
Output:
Hope it helps.
Input:
Code: Select all
1
12
7
4
0
9
4
8
8
2
4
5
5
1
Code: Select all
4
Ami ekhono shopno dekhi...
HomePage
HomePage

 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.
Re: 11572  Unique Snowflakes
your code do not pass the sample input.
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 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?
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...............................
It is more tough to become a good person.
I am trying both...............................

 New poster
 Posts: 13
 Joined: Mon Sep 08, 2008 6:57 pm
 Location: State University of Bangladesh
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 :
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 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
Never think too hard, let ideas come to you...

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

 Experienced poster
 Posts: 103
 Joined: Tue Mar 25, 2008 11:00 pm
 Location: IUTOIC, DHAKA, BANGLADESH
 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?
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...............................
It is more tough to become a good person.
I am trying both...............................
Re: 11572  Unique Snowflakes
Code: Select all
1
6
1 2 3 2 4 5
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@