11572 - Unique Snowflakes

[kbr_iut]

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.

[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

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

[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

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

[el cheeto]

Be careful!! I used map, and TLE using cin and cout. ACC in 1.120 using scanf and printf.

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

[serur]

I got Ac with the above approach; however, the above post contains some FIXME's and therefore can't be considered a spoiler.

[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

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

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

[brianfry713]

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

For input:

Code: Select all

1
1
0

Output should be 1

[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?

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

[brianfry713]

Input:

Code: Select all

1
5
2
1
2
1
3

Output should be 3.