Page 2 of 3

### Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 6:02 pm
sapnil wrote:

Code: Select all

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

i dont have any idea to pass the TL.
can u pliz share ur method.

### Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 6:28 pm
>> If in input every number is equal, you initilize map n times(It is not needed), it is not enough for pass time limit.
>>try map initilize for each test case,not for each repeated data.

>> hope it helps.

Thanks

### Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 6:56 pm
I am sorry.
i am not getting ur point.
if i dont initialize map every time how cud i determine the identical numbers.
suppose.
1 2 3 2 4 5
if i dont initialize my map ....then i will get map[2]>0 in the colored portion.so i havnt any idea to minimize the TL.
I am so stupid.

### Re: 11572 - Unique Snowflakes

Posted: Wed Feb 25, 2009 5:00 am

Code: Select all

``````map<int,int> mp;

mp[1]=1;
mp[2]=2;
mp[3]=3;
mp[2]=4;<
mp[4]=5;
mp[5]=6;
``````
Now when u going for 4'th number(2),you find 2 occured before and location is 2(current location is 4) .
Thats all.

Thanks

### Re: 11572 - Unique Snowflakes

Posted: Wed Feb 25, 2009 2:47 pm
Thanx Jony vi, at last I got the point and got AC in 1.10 second. This problem drove me crazy. But the logic is too simple.

### Re: 11572 - Unique Snowflakes

Posted: Fri Mar 13, 2009 1:37 am
Be careful!! I used map, and TLE using cin and cout. ACC in 1.120 using scanf and printf.

### Re: 11572 - Unique Snowflakes

Posted: Mon Jun 01, 2009 3:28 pm
the problem can be restated in terms of RMQ (range minima query) as follows:
for each index i let idx be the index of the next occurence of the number a.
If i is the last occurence of the number a, let idx = n (recall that we are using 0-based indexation).
Now, for each i from 0 to n-1 check whether RMQ(i,idx-1) >= idx. If so, update the answer len = max(len,idx-i).
RMQ is over the array idx; idx itself can be built with some balanced BST.
This leads to O(nlogn) solution, too.

### Re: 11572 - Unique Snowflakes

Posted: Tue Jun 09, 2009 5:16 pm
I got Ac with the above approach; however, the above post contains some FIXME's and therefore can't be considered a spoiler.

### Re: 11572 - Unique Snowflakes

Posted: Sat Oct 02, 2010 10:53 pm
Hello,

[EDIT] I checked the timing, and apparently it takes 1.8 seconds to just read in the data, and .15 seconds to do the dividing. That leaves about .05 seconds to combine the left and right in d+c. Something about those times don't seem right, especially because if it really takes 1.8 seconds to read their data into an array, no one would have a time less than 1.8 seconds, right?

I used d+c, but my code gets tle and I'm not sure why (2 seconds seems pretty short though):

Code: Select all

``````import java.util.Scanner;

public class Main {

int[] nums;

public Main() {
Scanner in = new Scanner(System.in);
int numCases = in.nextInt();
for (int i = 0; i < numCases; i++){
int numNums = in.nextInt();
nums=new int[numNums];

for (int j=0; j < numNums; j++){
nums[j]=in.nextInt();
}
System.out.println(longest(0,numNums-1));
}
}
public int longest(int start,int end){
if (start-end==0)
return 1;
else if (start-end==1){
return nums[start]==nums[end]?1:2;
}
else{
int center = (start+end)/2;
int left = longest(start,center);
int right = longest(center+1,end);
int max = Math.max(left, right);

int b = center;
int e = center;

//Go forward across center until uniqueness is broken
forward:
while(e<end){
for (int i = b; i<=e; i++){
if (nums[i]==nums[e+1]){
break forward;
}
}
e++;
}
max = Math.max(max, e-b+1);

//Go backwards across center until the longest unique string goes doesn't span the center
while (e>center && b>start){
for (int i = b; i<=e; i++){
if (nums[i]==nums[b-1]){
e=i-1;
break;
}
}
b--;
max = Math.max(max, e-b+1);
}
return max;
}
}
public static void main(String[] args) {
new Main();
}
}
``````

Thanks,
Eric

### Re: 11572 - Unique Snowflakes

Posted: Thu Jun 02, 2011 7:04 pm
my solution is O(n) + complexity of accessing stl map in each iteration. it took .416 second.

btw its the 600th problem that i solved .

### Re: 11572 - Unique Snowflakes

Posted: Tue Jul 16, 2013 8:21 pm
Here is my wrong code

Code: Select all

``````#include <iostream>
#include <map>
int main()
{
int tc,tsc,s,ps,mxsize,cursize;
std::cin>>tc;
while(tc--)
{
mxsize = cursize = 0;
std::map<int,int> snf;
std::map<int,int>::iterator it;
std::cin>>tsc;
while(tsc>0)
{
std::cin>>s;
it = snf.find(s);
if(it == snf.end())
snf[s] = 0;
else
{
cursize = 1;
snf.clear();
snf[ps] = 0;
it = snf.find(s);
if(it != snf.end())
{
snf.clear();
cursize = 0;
}
snf[s] = 0;
}
cursize++;
if(mxsize<cursize) mxsize = cursize;
ps = s;
}
std::cout<<mxsize<<std::endl;
}
return 0;
}
``````

I tried all the test cases in this forum, yet still got WA

I'm a little suspicious of this input in my program

1 0

output: 0

though.

### Re: 11572 - Unique Snowflakes

Posted: Tue Jul 16, 2013 11:23 pm
Your code doesn't produce any output on the sample input.

For input:

Code: Select all

``````1
1
0``````
Output should be 1

### Re: 11572 - Unique Snowflakes

Posted: Sun Sep 01, 2013 8:42 am
The simplest O(n) algorithm implementation is basically a hashed map.
But it only helps slightly in runtime - I got 0.362s for STL map O(nlogn) while 0.212s for my hash map implementation...
Are there any alternatives that runs in O(n) aside from hash map?

### Re: 11572 - Unique Snowflakes

Posted: Sat Sep 07, 2013 6:12 pm
why I am getting WA any help?

Code: Select all

``````/*
* UniqueSnowflakes.cpp
*
*  Created on: Sep 7, 2013
*      Author: mohamed
*/

#include <map>
#include <stdio.h>
using namespace std;
map<int, int> mac;
int main(int argc, char **argv) {
int t, n, m;
scanf("%d", &t);
while (t--) {
mac.clear();
scanf("%d", &n);
int max = 0, cur = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &m);
if (mac[m] == 0) {
cur++;
mac[m] = i;
if (cur > max)
max = cur;
} else {
cur = i - mac[m];
mac.erase(mac.begin(), mac.find(m));
mac[m] = i;
}
}
printf("%d\n", max);
}
}

``````

### Re: 11572 - Unique Snowflakes

Posted: Tue Sep 10, 2013 1:11 am
Input:

Code: Select all

``````1
5
2
1
2
1
3
``````
Output should be 3.