Microsecond Running Times!

Carthage · 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!

Dominik Michniewski · 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

Whinii F. · 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?

bery olivier · 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.

Farid Ahmadov · 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.

Carthage · 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???

bery olivier · 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.

Carthage · 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.

Carthage · 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!

Maarten · 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 · 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...