Page 2 of 3

Re: 11572 - Unique Snowflakes

Posted: Tue Feb 24, 2009 6:02 pm
by kbr_iut
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
by sapnil
>> 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
by kbr_iut
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
by sapnil

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
by kbr_iut
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
by el cheeto
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
by serur
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
by serur
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
by lorderico
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
by Shafaet_du
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 :P.

Re: 11572 - Unique Snowflakes

Posted: Tue Jul 16, 2013 8:21 pm
by Faithkeeper_Rangwan
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
by brianfry713
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
by Hikari9
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
by sh3ban
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
by brianfry713
Input:

Code: Select all

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