484 - The Department of Redundancy Department

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

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

dumb dan wrote: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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan »

CDiMa wrote: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.
Last edited by dumb dan on Fri May 20, 2005 4:32 pm, edited 1 time in total.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

dumb dan wrote:
CDiMa wrote: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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by 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
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by 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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Reply On 484

Post by 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
New poster
Posts: 2
Joined: Tue May 31, 2005 7:55 am
Location: CHITTAGONG

484-help me

Post by 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.
Be active

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by 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
New poster
Posts: 9
Joined: Sat Oct 15, 2005 4:41 am

484 Unknow reason WA

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

thirddawn
New poster
Posts: 9
Joined: Sat Oct 15, 2005 4:41 am

Post by 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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by 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
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by 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.
Last edited by Schutzstaffel on Tue Jan 10, 2006 2:35 pm, edited 1 time in total.
Image

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

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

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel »

I changed to 1000000 and got AC, thanks :P
Image

Post Reply

Return to “Volume 4 (400-499)”