Microsecond Running Times!

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm

Microsecond Running Times!

Post by Carthage » Thu Oct 30, 2003 6:28 pm

Hello, I'm new here and I was just browsing through some of the problems. I cam across a ranklist for problem 100 (3n + 1 problem) and found that those that were on the top ten had running times as low as 0.002 secs using only 64k of memory! How the hell did they do that??

My best program for the said problem, which was written in C++, finished in 0.237 seconds using as much as 5MB of memory. I used computation memorization so as to reduce redundant computation of cycle lengths. In my opinion, or at least to the best of my knowledge, this is the fastest algorithm that I know.

I think 0.002 or lesser secs using as much as 64k of memory is darn impossible unless you program in assembly or shift bits. Could anyone give me an idea as to how those people achieved such running times????

Tnx!
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Oct 31, 2003 8:53 am

Try to change input and output from C++ to C .... I heard many times, that IO functions in C++ are slower than the same from C ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Fri Oct 31, 2003 9:43 am

You can avoid using printf and scanf too by writing them yourself.
I hear some of the gurus here use their own-written floating point input & output functions, which are much faster than the formatted scanf() and printf().

Great, huh? ;)
JongMan @ Yonsei

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Fri Oct 31, 2003 10:14 am

Actually not only the gurus, a lot of people do.
I usualy use putchar() instead of printf() for int, long, short. But I guess puts() or write() would be faster.
But if you really want to optimize you source, better optimize you inputs. scanf is really slow, it handle spaces, new lines can scan intergers, floating points numbers, strings etc... Better use getchar(), read(), fread(), gets().
I also heard that cin and cout are faster than scanf() and printf(). I don't know well C++ though.

But although you can have good times this way, It won't subsitute a good algorithm.
Not AC yet Image AC at last Image

Farid Ahmadov
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

Post by Farid Ahmadov » Fri Oct 31, 2003 12:42 pm

cin and cout are very slow, as slow as pascal's read write. scanf and printf are the bests I think.
Bye.
_____________
NO sigNature

Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm

Post by Carthage » Fri Oct 31, 2003 6:56 pm

Hi, I've just solved 101. Before that, it took about 10 tries before it got accepted. I was so sure of my code it baffled me as to how it could get WA. I used this...
[cpp]const int MAX = 80;

// Utility function to read from stdin.
bool readLine(char *stream)
{
if(stream == NULL)
throw "Valid stream required.";

fflush(stdin);
int count = 0;
char c;

for(; (c = getchar()) != '\n'; count++)
stream[count] = c;

if(count == 0)
return false;

stream[count] = '\0';
return true;
}[/cpp]

to read off the standard input. I changed it to a standard scanf() and the program got accepted right away. Anyone care to tell me why???
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Fri Oct 31, 2003 7:21 pm

Your function seems ok to me. Your mistake should be somewhere else.
If you use scanf to get the numbers, then do not forget to put a getchar(); after.
Not AC yet Image AC at last Image

Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm

Post by Carthage » Fri Oct 31, 2003 7:29 pm

bery olivier wrote:Your function seems ok to me. Your mistake should be somewhere else.
If you use scanf to get the numbers, then do not forget to put a getchar(); after.
I thought I was flushing out the standard input stream if the input comes from a file, so I removed fflush(), then recompiled my program, but now it bombs out after inputting a number! So I guess fflush() was useful after all.

Well, since it returns a string, I have to strtok(), then atoi() the tokens to convert them to integers, and it worked just fine, but still WA. So I scrapped all that and the previously mentioned function for a scanf(), but I don't like using scanf() mainly because it doesn't accept anything after whitespace, like gets(), but gets() crashes my prog with an invalid memory reference. I already new'd the char pointer with an appropriate size.
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm

Post by Carthage » Fri Oct 31, 2003 7:42 pm

BTW, I sent a WA 107. Although I don't think that my algorithm is right, what intrigued me was that according to the results, my program ran in 0.534 seconds using as much as 64k of memory. 64k is impossible considering that I used a really big lookup table that takes about a megabyte of memory.

So a revelation came upon me: if a program runs fast enough (give or take 0.500 seconds or less), then the OJ won't be able to detect the exact amount of memory the program used, even if the program used about 8MB of memory. It'll just display 64k!
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm

Post by Maarten » Sat Nov 01, 2003 12:38 am

Carthage wrote:My ideas on solving programming problems are 90% common sense and practicality, 8% pure knowledge, and 1% extreme Math.
What's the last 1% ?

Carthage
New poster
Posts: 12
Joined: Wed Oct 29, 2003 8:05 pm

Post by Carthage » Sun Nov 02, 2003 6:23 pm

Maarten wrote: What's the last 1% ?
Oops. Forgot it. :) Probably should be with the majority...
My ideas on solving programming problems are 91% common sense, practicality and luck, 8% pure knowledge, and 1% extreme Math.

Post Reply

Return to “Other words”