11572 - Unique Snowflakes

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11572 - Unique Snowflakes

Post by kbr_iut » 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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11572 - Unique Snowflakes

Post by sapnil » 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
"Dream Is The Key To Success"

@@@ Jony @@@

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11572 - Unique Snowflakes

Post by kbr_iut » 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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11572 - Unique Snowflakes

Post by sapnil » 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
"Dream Is The Key To Success"

@@@ Jony @@@

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11572 - Unique Snowflakes

Post by kbr_iut » 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.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Re: 11572 - Unique Snowflakes

Post by el cheeto » 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.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11572 - Unique Snowflakes

Post by serur » 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.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Re: 11572 - Unique Snowflakes

Post by serur » 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.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

lorderico
New poster
Posts: 6
Joined: Sat Oct 02, 2010 10:47 pm

Re: 11572 - Unique Snowflakes

Post by lorderico » 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

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11572 - Unique Snowflakes

Post by Shafaet_du » 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 :P.

Faithkeeper_Rangwan
New poster
Posts: 12
Joined: Sun Jul 07, 2013 7:32 pm

Re: 11572 - Unique Snowflakes

Post by Faithkeeper_Rangwan » 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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11572 - Unique Snowflakes

Post by brianfry713 » 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
Check input and AC output for thousands of problems on uDebug!

Hikari9
New poster
Posts: 20
Joined: Tue Jan 22, 2013 4:39 pm

Re: 11572 - Unique Snowflakes

Post by Hikari9 » 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?

sh3ban
New poster
Posts: 1
Joined: Sat Sep 07, 2013 6:09 pm

Re: 11572 - Unique Snowflakes

Post by sh3ban » 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);
	}
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11572 - Unique Snowflakes

Post by brianfry713 » Tue Sep 10, 2013 1:11 am

Input:

Code: Select all

1
5
2
1
2
1
3
Output should be 3.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 115 (11500-11599)”