484 - The Department of Redundancy Department

[CDiMa]

This problem can be solved in O(n log n). Or faster if input is nice, but we have no reason to believe input is nice.

Hmmm, I think this problem is easily solved in O(n).
You need a queue and an array sized twice the biggest number in input.
This is the pseudo code of this easy solution

Code: Select all

 loop
	if EOF 
		exit loop
	endif
	read number
	if count of number is zero
		enqueue number
	endif
	increase count of number
end loop
while queue not empty 
	dequeue number
	print number, count of number
end while

With this approach I got a runtime of 0:00.006 with a pure C program.
As you can see it's close enough to those of Scott and Ivor. You can also notice that Scott and Ivor solved this problem in 2002 probably before the upgrade of the OJ.
Before the upgrade the resolution of runtime measurements was 10 or 20 milliseconds and so probably they got 0:00.000 because of this.

I hope this cleared any doubts on the speed of some submissions.

Ciao!!!

Claudio

[dumb dan]

an array sized twice the biggest number in input

This is what I meant by input being nice. There's no mentioning of a limit to the input numbers in the problem description.

I wouldn't want to allocate that array if the biggest number is, say 2^30. I can only assume by your post this wasn't the case for the judge input.

[CDiMa]

an array sized twice the biggest number in input

This is what I meant by input being nice. There's no mentioning of a limit to the input numbers in the problem description.

I wouldn't want to allocate that array if the biggest number is say, 2^30. I can only assume by your post this wasn't the case for the judge input.

I assumed an array size of 1000000 would suffice and it actually worked.
The other working assumption was that there weren't more than 100000 numbers in input.

Ciao!!!

Claudio

[Rocky]

Thanks For Reply.
Actuallay I Mean That If Input 3 Then counter[3]++;

My Algorithm Below :

int i=0;
Read number
if(EOF)
exit;
else
{
input = number;
sort_input= number;
counter[number]++;
i++;

}

sort(sort_input);
remove_duplicate(sort_input);

for(k=0;k<i;k++)
for(l=0;l<i;l++)
{
if(input[k]==sort_input[l])
printf(input[k] count[l]);
sort_input[l] = -1 //for nonchek next time
}


THANK'S IN ADVANCE
ROCKY

[dumb dan]

Your current algorithm is O(n^2).
You can make it O(n) if you just remove dublicates when you read the input instead of later. All you need to do is check if(counter[number]) and just don't put anything into input that already has counter>=1.

If you want to solve problems faster, you need to think more on the time complexity of your code.

[Rocky]

Thank's.
Right You Are My Algorithm Is O(n^2),
I Can Reduce My Time By Remove The Duplicate In Time Of Taking Input.
Actually Time Is One Of The Main Fact.

Thank's Again,
ROCKY

[MD. OMAR FARUQUE]

I solve 484 but not accepted time limit exeed beacause i done it normal logic by for loop.Can anybody give me better solution.

[Rocky]

In Previous Post OMAR Wrote:

I solve 484 but not accepted time limit exeed beacause i done it normal logic by for loop.Can anybody give me better solution

One Previous Post Can Help You.Check It.
http://acm.uva.es/board/viewtopic.php?t ... 98d402a0f3

You May Find Some Hints For This Problem.Hope It Help.

GOOD LUCK
Rocky

[thirddawn]

hum...I think there are no errors over there,But I just get WA = ="

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
long long int first[100000],last[100000],array[100000];
char str[100000];

int main(){
	char *p;
	long long int i,j,l,counter,special,n;
	while(gets(str)){
		p=strtok(str," ");
		n=0;
		while(p!=NULL)
		{
			sscanf(p,"%d",&array[n++]);
			p=strtok(NULL," ");
		}
		i = 1;
		first[0] = array[0];
		counter = 1;
		for (l = 0;l<2000;l++)
			last[l] = 0;
		last[0] = 1;
		while (i < n){
			special = 0;
			for (j = 0; j < counter;j++){
				if (array[i] == first[j]){
					special = 1;
					last[j] = last[j] + 1;
				}
			}
			if (special == 0){
				first[counter] = array[i];
				last[counter] = last[counter] + 1;
				counter = counter + 1;
			}
			i = i + 1;
		}
		for (i = 0; i < counter;i++){
			printf("%lld %lld\n",first[i],last[i]);
		}
	}
	return 0;
}

thanks for assist

[mamun]

You didn't understand the input properly. There is only one input and hence one output. The input continues upto EOF.

[thirddawn]

I change my code to do gets only once,but it's still the same...WA

Sorry...

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>
int first[100000],last[100000],array[100000];
char str[10000000];

int main(){
	char *p;
	int i,j,l,counter,special,n;
	gets(str);
		p=strtok(str," ");
		n=0;
		while(p!=NULL)
		{
			sscanf(p,"%d",&array[n++]);
			p=strtok(NULL," ");
		}
		i = 1;
		first[0] = array[0];
		counter = 1;
		for (l = 0;l<100000;l++)
			last[l] = 0;
		last[0] = 1;
		while (i < n){
			special = 0;
			for (j = 0; j < counter;j++){
				if (array[i] == first[j]){
					special = 1;
					last[j] = last[j] + 1;
				}
			}
			if (special == 0){
				first[counter] = array[i];
				last[counter] = last[counter] + 1;
				counter = counter + 1;
			}
			i = i + 1;
		}
		for (i = 0; i < counter;i++){
			printf("%d %d\n",first[i],last[i]);
		}
	return 0;
}

[mamun]

What's the guarantee that all the numbers are on a single line?
So use a loop to read all the nubers using scanf() and then do the processing and output.

[Schutzstaffel]

I'm getting WA but I tested my code for negative/zero/positive numbers and also with space and newlines.

Code: Select all

code AC :P
}

Any help is appreciated, thank you.

[mamun]

I don't know but the input range as well as total number of integers maybe more than 10000.

[Schutzstaffel]

I changed to 1000000 and got AC, thanks