Page 5 of 7
Posted: Fri May 20, 2005 11:07 am
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
Posted: Fri May 20, 2005 11:57 am
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.
Posted: Fri May 20, 2005 12:57 pm
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
Posted: Mon May 23, 2005 11:37 am
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
Posted: Mon May 23, 2005 4:52 pm
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.
Reply On 484
Posted: Thu May 26, 2005 7:29 am
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
484-help me
Posted: Tue May 31, 2005 8:50 am
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.
Posted: Tue May 31, 2005 12:12 pm
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
484 Unknow reason WA
Posted: Tue Dec 27, 2005 7:20 am
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
Posted: Tue Dec 27, 2005 9:00 am
by mamun
You didn't understand the input properly. There is only one input and hence one output. The input continues upto EOF.
Posted: Tue Dec 27, 2005 11:31 am
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;
}
Posted: Tue Dec 27, 2005 11:39 am
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.
Posted: Tue Jan 10, 2006 2:50 am
by Schutzstaffel
I'm getting WA but I tested my code for negative/zero/positive numbers and also with space and newlines.
Any help is appreciated, thank you.
Posted: Tue Jan 10, 2006 7:37 am
by mamun
I don't know but the input range as well as total number of integers maybe more than 10000.
Posted: Tue Jan 10, 2006 2:35 pm
by Schutzstaffel
I changed to 1000000 and got AC, thanks
