🔒 Locked

Programming competitions?

Started by Aquila Sep 15, 2007 at 9:27 AM 4 replies 1.1k views

Original Post

Sep 15, 2007 at 9:27 AM

Pretty much, does anyone around here go in for that sort of stuff, and what would you recommend to get better at them? I recently got involved in first a small national competition, which sort of flowed into the South Pacific ACM Regionals [we did awfully badly xD]. I'm 3/4 through my first year in a CS degree; have been learning C# ["learnt" Java (over a couple of days; really just the SLIGHTLY different syntax, and the mildly different libraries) for ACM though]. Other than just straight practice - I'm planning to go hard on the past questions sets and sites like topcoder once my university workload eases a bit - I've heard people mention things like "oh you should learn about graph theory" and a whole lot of random things like that. So yeah.... any hints, suggestions, etc? What sort of things I should actually learn that I won't get from just practice? Any strategy hints for the actual competitions? We just sort of floated around the computer, for the first while all just working on one question, eventually splitting up into 2:1 groups, 2 people coding with one pseudo-coding another question on paper. Hints for the actual code? Do you consider it necessary to have halfway-decent variable names; I usually wind up with code looking like this: String[] qwe = qw.split(" "); int asd = qwe[0]; [You should notice why I chose those 3-letter combos pretty easily if you're on QWERTY ^_^;;] Since I know pretty well what my code is doing, it never occurred to me to have proper names. I know someone who competed in the smaller competition who actually commented his competition code; I'm pretty sure that's pointless! But yeah, basically, anything you can throw at me. I won't have another chance at all this for another year, but plan to practice well in that time. I might as well chuck in a random opinion question -- do people have preferences for languages used for progcomps? I guess it's mainly C++ vs Java here. I haven't tried C++, but Java seems nice to code in, though I have no basis for comparison so yeah.

ToohrVyk

Sep 15, 2007 at 9:41 AM

Concerning the variable naming issue: it's very likely that you will have to debug your program, so variable names which are even remotely relevant (str, num, id, found, target, foobar_max, lst, candidates) are good choices, and they don't take that much longer to get right. Especially in a competition like the ACM-ICPC where you'll spend more time trying to find an algorithm than you will spend actually coding it.

I personally use O'Caml for progcomps wherever applicable. Failing that, I use C++ due to my greater knowledge of the standard library (even though that library is often slower than the Java one—one of the main reasons my participation in Southwestern Europe ACP-ICPC qualifiers two years ago ended up a dud).

My advice? Know your standard library by heart. Know how to accomplish your average general-purpose algorithms (finding a maximum, partitioning a container, sorting a sequence, etc) in minimum coding time and debugging time. Have people solve things on paper, one each, and the person who gets done the fastest goes and types it, then submits it, and gets back to work. You have to distinguish between implementation (simple to get, difficult to code without error), algorithm (simple to code once you get the correct idea) and optimization (it's fairly obvious to understand and write, but it takes effort to optimize) and adopt the correct strategy (careful coding, careful paper work, easily refactored code) depending on which you are facing.

Antheus

Sep 15, 2007 at 9:55 AM

Quote:
I guess it's mainly C++ vs Java here. I haven't tried C++, but Java seems nice to code in, though I have no basis for comparison so yeah.

Many of these competitions use a random subset of the languages. Not V1.0 or something like that. They just say what goes and what doesn't. Very annoying.

I remember in one competition I found myself unable to code in Java, since everything I considered to be the very syntax of Java (class, for example) didn't work.

After reading through documentation, it turns out they used a custom compiler, which didn't support classes. The mind boggles...

TopCoder is... About speed. I'm not sure if things have changed, but it used to be that people would abuse the data entry form and ability to add your own code to copy-paste complete frameworks for problems (trees, graphs, I/O, algorithms) and would use those to win simply due to time saved. TopCoder is also frequently criticized for being too speed-driven, with complete disregard to anything CS-related. once again, this might have change.

ACM is team-based, and requires teamwork. Problems there tend to be quite reasonable, and often deceptive with regard to difficulty.

But, almost all of these competitions are math-based. A mathematician will almost certainly do way better than a software engineer.

d000hg

Sep 15, 2007 at 2:40 PM

TopCoder's pretty good. Speed's important to understand the problem, but the coding of your solution isn't so critical. If you do all the problems correctly, you'll do really well, even if you're not the fastest.
Stupid variable names and so on aren't helpful, although a few macros if you use C++ can be if you use STL a lot.
Some people have some prewritten stuff, but the top guys don't do any of this stuff. They're just geniuses.

I recommend the site.

iMalc

Sep 15, 2007 at 7:48 PM

Some firends once asked me to join their team for a programming competitions where you have 3 people in your team and one computer. I accepted, but found during the competition, that I would have done much better entering solo. Spent ages trying to fix up one of the other guys buggy solutions instead of just writing it from scratch myself.

They are definitely very enjoyable though.

Jaiminho

Sep 15, 2007 at 10:48 PM

Quote:
Original post by Aquila
I've heard people mention things like "oh you should learn about graph theory" and a whole lot of random things like that.

You do have to learn it.

Anyways, Java makes you spend lots of time on some stuff that won't regard simply your code. C and C++ are more straight to the point coding languages for this kind of this, but C++ has the advantage of STL. Plus, code execution time counts points on some competitions, so you'd better use a high performance language like those 2.

Basically, you must pratice a lot and learn some techniques as dynamic programming and anything related to graphs. Check acm.uva.es for a bunch of problems for you to work on.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.