competitive programming

[Scarlet Firefly]

Hi everyone.

This topic's target audience are our Smogon coders/programmers.

Recently I got coerced into joining a national competitive programming competition (such as ICPC/ACM/IOI). I have also been obligated to win a medal for the school.

here is how the competition grading works:
top 50% = bronze medal
top 25% = silver medal
top 10% = gold medal

so it would seem easy to get a medal; 1 in 2 of the participants get at least a medal. furthermore, lots of the contest participants are feeders who solve 0 questions so they form the bottom 50% and lets other better-but-not-actually-expert coders get medals by solving 1 question.


unfortunately, I am a member of that bottom 50%.

the only material the teacher provided for me to train for the upcoming competition in March is a "Competitive Programming" book that is probably for experts-only: I couldn't understand past the 9th page. attempting to train for the competition in this manner only, is, how I'd crudely make an analogy, "rubbing my dick against sandpaper".


I was wondering if any Smogonites have user-friendly resources or links to help me in learning competitive programming?

for your reference, these two links contain the contest questions for 2013 and 2014:
http://www.comp.nus.edu.sg/~noi/2013/NOI_2013.pdf
http://www.comp.nus.edu.sg/~noi/2014/NOI_2014.pdf

thanks in advance to all of you and also thanks for reading, hugs and kisses <3

PS: apparently there is more pressure to train well for this rather than "pokemon games" such as SPL or WCOP... :S

 

[MJB]

You neglected to mention just how much experience you actually have with programming. Theres a really big difference between never touched a programming language and knowing the difference between and integer and a float.

If you are in the former, then I recommend actually learning how to code to some level first. There are plenty of resources for this, one I have recommended to a few people now is codeacademy.com. Pick either Python or Javascript and you can't get too far wrong. Learn the basics, complete the course if you can.

If you are the latter and no more, then the above is probably still true.

The third option which I am going to assume for the rest of this is that you are familiar with at least 1 programming languages syntax, but aren't fluent in a lot of computer theory.

From my brief skim through the questions, it seems these are fairly 'standard' algorithm based questions. Heuristic searches, graph theory and so forth. So those 2 things would be great places to read up on. If you only need to answer 1 question then I would play the odds and learn 1 area really well and gamble that it comes up, depending on when this competition actually is.

Heuristic algorithms can be categorised by those that do not come to a complete answer, but instead through mass amounts of trial and error in a search space, eventually try and iterate down to an answer that is either correct or very close to correct. This is the method usually taken when an algorithm to find a definitive answer to a problem is far to computationally complex to calculate for large data sizes (translated to english, it would take like 5 years to get to an answer.)

some example of heuristic algorithms include:

random search
hill climb
genetic algorithms


Another good area to look into is graph theory, while these can sometimes be heuristic as well, they aren't always. These are more easily defined in terms of certain problems, what is the shortest path between A and B? cheapest path? path that visits every node or traverses every road etc.

again some example algorithms are:

Primms
Djikstras (spelling?)
A lot of shit by Euler


I think reading up on those would be a good start. I don't have any good sources for where to start, but this is computer science. Everything is on the interweb.

Something to keep in mind with these things is also computational complexity, you need to make sure your program wont take forever on realistic data sizes, so reading up on the basics of the Big O notation might not hurt either.


Hope I helped :)

 

[Relados]

I'm a part of my university's competitive programming team. There's a lot of good resources out there for competitive coding, but it depends on the format of the competition. Here's a link to one competition where it has downloads of the past problem sets used (as well as the test input files and appropriate output files, but you wouldn't normally be viewing those). There's also TopCoder's challenge page. Both of these kinda assume you know quite a bit of programming already, so if you're newer to coding it might be a little too difficult.

 

[Scarlet Firefly]

The third option which I am going to assume for the rest of this is that you are familiar with at least 1 programming languages syntax, but aren't fluent in a lot of computer theory.

From my brief skim through the questions, it seems these are fairly 'standard' algorithm based questions. Heuristic searches, graph theory and so forth. So those 2 things would be great places to read up on. If you only need to answer 1 question then I would play the odds and learn 1 area really well and gamble that it comes up, depending on when this competition actually is.

Heuristic algorithms can be categorised by those that do not come to a complete answer, but instead through mass amounts of trial and error in a search space, eventually try and iterate down to an answer that is either correct or very close to correct. This is the method usually taken when an algorithm to find a definitive answer to a problem is far to computationally complex to calculate for large data sizes (translated to english, it would take like 5 years to get to an answer.)

some example of heuristic algorithms include:

random search
hill climb
genetic algorithms


Another good area to look into is graph theory, while these can sometimes be heuristic as well, they aren't always. These are more easily defined in terms of certain problems, what is the shortest path between A and B? cheapest path? path that visits every node or traverses every road etc.

again some example algorithms are:

Primms
Djikstras (spelling?)
A lot of shit by Euler


I think reading up on those would be a good start. I don't have any good sources for where to start, but this is computer science. Everything is on the interweb.

Something to keep in mind with these things is also computational complexity, you need to make sure your program wont take forever on realistic data sizes, so reading up on the basics of the Big O notation might not hurt either.


Hope I helped :)

Thanks a lot for your suggestions, MJB :)

Yes, I belong in the 3rd category. Just in December I helped out in a research facility to build algorithms in python, so I think my general programming knowledge has improved quite a bit. Unfortunately, the competition is in C/C++ which is no longer my area of expertise. No python, gosh. Also, I have terrible mental scars (I participated in the competition twice before and failed twice before, so this is my 3rd year)

The algorithms that you have suggested are highly relevant to those tested in the competition, I will try to google for tutorial that are user friendly, thanks a lot :D

I'm a part of my university's competitive programming team. There's a lot of good resources out there for competitive coding, but it depends on the format of the competition. Here's a link to one competition where it has downloads of the past problem sets used (as well as the test input files and appropriate output files, but you wouldn't normally be viewing those). There's also TopCoder's challenge page. Both of these kinda assume you know quite a bit of programming already, so if you're newer to coding it might be a little too difficult.

Thanks for your link, Relados! Yes, this is similar to what they will have in the competitive programming environment that I have to solve. It doesn't appear that your university page has model solutions / tutorials though T_T

If you aren't too busy, could I seek tutoring from you on IRC? <3

 

[michael]

maybe have a look at project euler. it's something like 400+ algorithmic problems that you can tackle in your language of choice.