Solutions for the problems

[fxthomas]

hi,

Can anyone please help to find the solutions to the problems.
I know it is not fair to ask ,but i would like to know whether my code is
better that the one who won the first place.

just to know whether there is any better apporach than the style in i
used (i.e. algorithms).

or can anyone tell me of book related to algorithms which will be helpful
for me to learn the basic and complex techinques of algorithm solving
like you great guys do here.

It will be of great help to me.

[dawynn]

In general, its pretty easy to tell whether your code is as good as the first place code. In the problem set listing -- click on the percentage inside the parenthesis for the problem in question. This will provide a ranking of everyone who solved the problem sorted by time spent, memory spent, and date submitted. So, if 503 people, including yourself, solved a problem in 0 time, with low memory spent, but you just submitted yours today, you'll be at about 503rd position, but your code is running as fast as efficiently as the person who ranked first.

A couple hints that may help --
1) Classes use memory. Actually, classes horde memory. So with two similar approaches to the same problem written in C++, one using classes, the other not using classes -- the non-OO version will win in the memory-spent division every time. I've never tried Java on this system. But since Java mandates OO, I would expect it to use more memory than necessary for most problems.

2) For certain problems that always list the same values (problems with no input), once the correct values are determined, it is fastest and easiest just to submit a program that lists the appropriate values, without calculating them. Example problems: 138, 291

3) I've never tested, but it would be a fun experiment -- I'm of the belief that it may be more efficient to write a program in C than in C++. I don't know how much -- as long as you don't use the OO functionality in C++, the two may not be much different. Java, with it's mandatory OO, is probably the slowest, most memory-intensive language to use. I don't know how Pascal compares to C / C++.

4) Last, most heavy users of the system try not to post code. So, you'll probably have a hard time convincing the people who write the best code to share. But, if there's a specific problem where your program seems to be running long, you can always post a question on the board and see if anyone has any suggestions for boosting code performance sepcific to that problem.

As far as books go, I use my graduate class textbook. It's not a good "starter" book -- but it does cover a lot. Warning: this book defines the word "tome", weighing in at just over 1000 pages. It's called:
_Introduction_to_Algorithms_ by Cormen, Leiserson, and Rivest.

David

[fxthomas]

hi dawyn,

Thanx a lot for your suggestion.

Will buy the book u have refered.

[pc5971]

That book is the best I could find about Algorithms... It was translated in my own language (romanian) and is so "wonderfull" to have it, and study it . . .

Bye

[Fresh]

Additional to what dawynn said,

...optimized IO by reading/writing large blocks of data in raw format and parsing/printing it on their own...

...if you want fast I/O then forget about cin/scanf. Use at least gets(), it works much faster. And parse input by your own (again, without something like strtok()). I've used read()/write() in my solution...

I'm not 100% understand what they (Stefan & Ivan) said. But, by changing my old code from cin/cout or scanf/printf to fread/fwrite... i can see big different result. For example, problem 10110 - Light, more light. It ran 0:00.710(1252) with 'cin' and 0:00.130(408) with 'scanf' but 0:00.090(64) with 'fread'. All threes used same algo and fwrite for output. Till now, there're 12 authors who did better than me and Ivor - 0:00.010(64) - is the 'craziest'! Could Ivan describe more with his word, 'without something like strtok()' coz i did with strtok().


[cpp]

//part of my 10110 code
char *p, s[MAXSIZE];

fread(s,sizeof(char),sizeof(s),stdin);
p = strtok(s,"\n");
while (p != NULL)
{ ....
....
p = strtok(NULL,"\n");
}

[/cpp]


-novice

[Ivor]

mmm.... sweet.... thanks for the credit

Just one thing to add -- to do it without strtok, use a pointer to the input/output buffer. Pointers are very powerful if you know how to handle them.

Ivor

[Fresh]

Ivor,

I'm tired. The best result i could do is 0:00.060(64) and it still using strtok! I really not understand... doesn't the strtok itself uses a pointer ('char *p')? If u're willing to help me, may i know your mail address? I'll mail u my code.

-novice

[Ivor]

well yes, strtok uses char pointer, but only to get the string address (I think, I haven't been looking at the source code)...
there goes the time:
1) calling a function consumes time (function overhead)
2) strtok will cycle through characters upto whitespace, then you will cycle through the same characters to get the integer out of it... wouldn't it be better to search and get the integer at the same time?

Ivor
P.S. Isn't my mail address available anywhere? stats for example

[Fresh]

I forgot, the mail address . Now my speed is 0:00.050(64), just remove strtok() and follow your second instruction. It satisfied me even it's far slower than yours. But then, i mailed u my code... u might comment something about it espesially in converting a string to number.

-novice