## 484 - The Department of Redundancy Department

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
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
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
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
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:
Actuallay I Mean That If Input 3 Then counter[3]++;

My Algorithm Below :

int i=0;
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
}

ROCKY

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

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

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:
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
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

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
Contact:
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
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
Contact:
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
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.

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