To the top finishers in the III Local Contest in Murcia

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
BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

To the top finishers in the III Local Contest in Murcia

Post by BiK » Mon May 23, 2005 4:42 pm

Hi guys,

I just wondered how you were able to solve all the problems so quickly. Did you use code that was written before or you solved the problems from scratch? Did you know the problems beforehand?

The problems were not that difficult but still what you did was really admirable. The winner solved all problems after only 2h 15m and Per and Luka come closely after using only 2h 45m of the time. Furthermore, Per and Andrey had solved problems after the first 6 and 8 minutes. And I just can't get myself solving a problem in the first half an hour in the contest.

Any tips how to speed up my solving abilities and how to use my time more efficiently would be GREATLY appreciated.

Greetings

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Mon May 23, 2005 8:17 pm

I solved the first problem after 7 minutes (problem A). In this contest I was lucky enough that I saw the solution immediately for the first problem I opened. Then it was a matter of coding, testing and submitting the solution. Another problem that could be solved very quickly was C.

How to speed up solving abilities: Practise a lot! Solve a lot of problems, you'll be faster at thinking and typing. For a huge supply of easier problems, try the practice rooms at Topcoder, and choose the 250 point problems.

Although it was not necessary for the previous contest, having pre-written routines can be handy if you encounter bigint and geometry problems.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon May 23, 2005 11:09 pm

In this contest I wrote all code from scratch. Sometimes I use prewritten code for e.g. bigints.

My strategy in the very beginning of the contest is usually to read the short problems while keeping an eye out for problems where the names and/or images and/or sample IO seem to indicate that the problem's simple. After I've solved a problem (if things go well) or when I get bored of reading (if things go bad), I take a look to see what problems ther people are solving, which usually gives an even better impression of which problems are easy.

In the last contest, the shortest problem was D, and it also turned out to be very simple. Of course, this approach is far from flawless - I didn't read problem C until after I had solved B, and C was even easier than D, but it was long, had a scary name and scary sample I/O.

As for getting faster, I can only second stubbscroll: practice, practice, practice.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK » Tue May 24, 2005 1:27 pm

Thanks guys,

I am still curious for some more info. With regard to speed, I wonder whether I come up with just too long solutions in order to write and debug them in less than half an hour. For example, for the last contest the number of lines for my programs (C++) are as follows:

A - 59 lines
B - 105 lines
C - 30 lines
D - 51 lines
E - n/a
F - 52 lines
G - 81 lines

Here are the (approximate) times that I needed to solve the problems, write and most important DEBUG the programs in the order I was solving them:

1./ D ~ 31 min. including reading of the first 3 problems.
2./ A ~ 40 min. and I missed the case that the answer might be 0 so left the problem and moved on.
3./ C ~ 30 min.
4./ G ~ 40 min.
5./ F ~ 45 min.
6./ B ~ 80 min. which went beyond the end of the contest.

How about you?

What I particularly would like to know is how you debug your programs. I count very much on writing programs that would not need debuging but when it turns out that I have to debug then I'm having hard time, i.e. I lose a lot of time. How many of your programs do you need to debug on average in a contest? And how do you do it? I use g++ and when I have to debug I just use cout statements. I think that's the fastest way. Or am I wrong? Do you use gdb or the debuger of some development environment that you use? What development environment do you use?

I actually find the point in practicing in reducing the time you spend debugging your programs as much as possible. You automate yourself not to do stupid mistakes that later consume valuable time to discover.

Per, you are a top performer in these contests. How much time per week do you devote practicing? Do you just solve problems, do you read books, do you read papers? Do you have someone to guide you? I don't have anyone.

Greets

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue May 24, 2005 4:00 pm

Hello.
I can't understand just what you have written for problem A my code for A is just 13 lines.For D just 30 lines.
Please tell your algo for A,it is interesting for me how it hapens that your code is so long.
Eduard.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Wed May 25, 2005 7:31 am

For debugging, I use print statements, if the answer is wrong, but if you have a segmentation fault, gdb is invaluable!

If your program crashes, compile it with the -g flag, and then do this:

Code: Select all

> gdb a.out
> r < problem.in
-- crash ---
> back
> up
> up
> ...
> p i
> p j
> ...
The "r" command runs your program and feeds it the input file. "back" prints the stack. "up" moves up the stack. You should go up until you reach code that you wrote (it probably crashed inside a library function that you have no control over). "p" prints the value of a variable. For example, if you get a segmentation fault at "arr=8", then you will probably want to print i to see what it is. My favourite mistake is doing this:

Code: Select all

for( int i = n - 1; i >= 0; i++ ) x[i] = y[i] * 6;
gdb will easily find this bug.
If only I had as much free time as I did in college...

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Wed May 25, 2005 9:22 am

Hi!

As for me I NEVER use prewritten code even in Topcoder (I hope, code template doesn't count as prewritten code). Although sometimes it costs me lots of points in Topcoder :-?

And of course we didn't know the problems beforehand 8)
But after 5-year practice 90% of problems seems familiar to you and coding is automatic - like playing the piano your favorite etude :wink:

My lengths and times in AC-order:

A - 40 lines (766 bytes) in 8 minutes (after one wrong submission - 0 case).
D - 61 lines (775 bytes) in 8 minutes.
C - 54 lines (699 bytes) in 11 minutes.
B - 85 lines (1301 bytes) in 22 minutes (after one wrong submission).
F - 62 lines (817 bytes) in 10 minutes.
G - 72 lines (1031 bytes) in 14 minutes.
E - ... lots of lines and minutes. And lots of my stupidity were enough to give up and go playing Starcraft with my friends :lol: They surrounded me and tried to push Reset - they had no team balance without me :)

My only advice to give is practice. IMHO it is the only way to become both fast and accurate while programming.

Cheers,
Andrey.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed May 25, 2005 10:00 am

Per wrote:In this contest I wrote all code from scratch.
Hmm, I realised this is not 100% true. I do use a short template for all my solutions (containing some common #includes, a main method, some debugging macros, etc). When I trained for the ICPC I would type it in at the beginning of each contest, but well, I'm kinda bored of that by now. :)

The code sizes for my solutions, minus the size of my template (i.e. essentially the amount of code actually written for that problem) was:

A: 16 lines / 433 bytes
B: 51 lines / 1072 bytes
C: 15 lines / 301 bytes
D: 25 lines / 551 bytes
E: 81 lines / 1640 bytes
F: 65 lines / 1477 bytes
G: 44 lines / 869 bytes

The time I worked on each problem is essentially the time I solved it minus the time I solved the previous one. :)

I use print statements for almost all my debugging (in a contest, that is). If I have some really nasty runtime error bug I may use gdb, but most of the time I manage to find the bugs quickly enough without it. I usually don't have to spend that much time debugging - one very useful feature of having solved quite a lot of problems is that you make mistakes less often: once you've made (and then been forced to find and correct) the same stupid bug 50 times, you tend to avoid making it again (though of course it happens). I like Andrey's comparison to playing the piano - once you're good enough, it becomes very automatic (in a positive sense).

As for practice, well, I suppose I am retired now, so the UVa contests are my practice, a way to stay in shape, so to speak. When I was more active, I would spend quite a lot of time just solving problems, then realise that I had other stuff I needed to do, then forget about them and continue to solve problems, and so on. :)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed May 25, 2005 6:43 pm

Practice is key. As you practice, you'll get to see shorter way of doing things and maybe faster!

I also recommend a place like Topcoder, where people showcase their code. You can learn a lot from them!

I didn't solve during the contest, but here are my line totals, (I don't do anything to trim them down!) with headers, templates, everything:

A: 30 lines / 527 bytes
C: 25 lines / 413 bytes
D: 36 lines / 696 bytes
F: 23 lines / 369 bytes

(As you can see, I'm nowhere near Per, but I'm getting better! =))

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sat May 28, 2005 12:48 am

I use a base file with quite a lot of #includes, macro's, typedefs, etc. (77 unwrapped lines, 2211 non-space chars). I also have some code for bignums, max-flow, etc. but I didn't use any of that for this contest.

The code sizes for my solutions, minus the size of my template (i.e. essentially the amount of code actually written for that problem) was:

A: 13 unwrapped lines / 241 non-space chars
B: 40 unwrapped lines / 656 non-space chars
C: 12 unwrapped lines / 158 non-space chars
D: 21 unwrapped lines / 323 non-space chars
E: 83 unwrapped lines / 776 non-space chars (including commented out brute force code, used to guess the pattern)
F: 16 unwrapped lines / 195 non-space chars
G: 27 unwrapped lines / 417 non-space chars

But I'm known for my short coding style :)

As others have told, practice is definately the key to get faster. It especially reduces the number of mistakes you make and the time you need to debug.

Erik-Jan Krijgsman

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK » Sat May 28, 2005 4:09 pm

Thank you guys

Post Reply

Return to “Other words”