Topics for IOI/ICPC training

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Topics for IOI/ICPC training

Post by Pier » Wed May 03, 2006 6:24 am

Hi!

Which are good topics when training for IOI and ICPC? What topics might differ when training for each one? What "strategy" might differ when training for each one?

Also, any good problem(s) for divide-and-conquer? (that don't use a common algorithm, such as binary search or convex hull finding)


Thanks!
There are 10 kind of people on this world: those who understand binary and those who don't!

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Wed May 03, 2006 11:37 pm

For the ICPC one should put more focus into textbook algorithms. At the IOI there is an unspoken notion that the competition problems shouldn't depend on the knowledge given in university-level textbooks on algorithms. At the ICPC (depending on the region) one may encounter problems that require the knowledge of such algorithms, and in some regions go even far beyond this level.

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Thu May 04, 2006 6:34 am

Hi!

Thanks for your answer. I participed in some ICPC regionals, but as me and my coach were new at this, we learned as we went. Now I'm a coach (along with my former coach) of the OMI (Mexico Informatics Olympiad) at my state. My coach still trains teams for the ICPC (and I might join him). As what we teach is what we know, we might be skipping important topics.

For the ICPC it seems you have to know something about everything, but some topics might be more important than others. For the IOI, it seems that strong math background and good programming skills is enough at first, and that DP and Graph problems are common.

What I'm currently doing is a guide with problems and explanations of important algorithms and algorithm design techniques. Any suggestions? How important are advanced data structres? (I'm not including them)
There are 10 kind of people on this world: those who understand binary and those who don't!

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Thu May 04, 2006 2:41 pm

If you haven't seen (and solved through) the USACO training gate (at http://train.usaco.org/usacogate ), you most definitely should.
Their summary of the required IOI knowledge is pretty much accurate.

Post Reply

Return to “Algorithms”