### Re: 11572 - Unique Snowflakes

Posted:

**Tue Feb 24, 2009 6:02 pm**sapnil wrote:Output is:4Code: Select all

`1 6 1 2 3 2 4 5`

i dont have any idea to pass the TL.

can u pliz share ur method.

The Online Judge board

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

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

Page **2** of **3**

Posted: **Tue Feb 24, 2009 6:02 pm**

sapnil wrote:Output is:4Code: Select all

`1 6 1 2 3 2 4 5`

i dont have any idea to pass the TL.

can u pliz share ur method.

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

>>try map initilize for each test case,not for each repeated data.

>> hope it helps.

Thanks

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.

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.

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

Thats all.

Thanks

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.

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.

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.

for each index i let idx

If i is the last occurence of the number a

Now, for each i from 0 to n-1 check whether RMQ(i,idx

RMQ is over the array idx; idx itself can be built with some balanced BST.

This leads to O(nlogn) solution, too.

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.

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

Thanks,

Eric

[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

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 .

btw its the 600th problem that i solved .

Posted: **Tue Jul 16, 2013 8:21 pm**

Here is my wrong code

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.

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.

Posted: **Tue Jul 16, 2013 11:23 pm**

Your code doesn't produce any output on the sample input.

For input:Output should be 1

For input:

Code: Select all

```
1
1
0
```

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?

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?

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

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

Input:Output should be 3.

Code: Select all

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