15
$\begingroup$

Competitive programming is mainly about problem-solving skills. Students are given a problem and they have to write a short program to solve it. The students are given a problem for which they have to solve within the stipulated time. Efficiency or maintainability or portability of the code is not graded; however, the is a fixed amount of time given for each program to run.

Here is an example problem: https://www.codechef.com/LTIME49/problems/SHDWCMP

This kind of programming does not require a thorough knowledge of the language (for example, in C++, you'd never need to use classes or templates or anything as such) but it requires the student to be able to find ways to convert a word problem into a coding problem.

  1. How do you go about training a student for competitive programming?

  2. Teaching the language is not very hard but how do you improve someone's problem-solving ability?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ You may want first to fix what kind of problems do you want them to solve ? Raw Algorithm ? Software design ? Low level problem ? (Performance problems, IO Management, Cache, Memory, Floating precision limits, ...). To be honest, unless you're with very beginners, I disapprouve the fact to have your students write the first solution to the problem they think about, because it often miss edges cases, low level related problems, code written badly and not maintenable,... everything we hate to see as professionals even if "it works" $\endgroup$
    – Walfrat
    Commented Jun 30, 2017 at 11:04
  • $\begingroup$ @Walfrat: The type of problems used in competitive programming are mostly about algorithm (pick a solution with the time/space complexity that can pass the size of the test case), and some knowledge of the library offered by the language is sometimes needed (time complexity of the built-in data structure). The problems are also usually designed with edge cases or two, so it's a nice way to train them to think through them before coding. On the other hand, competitive programming places less emphasis on writing maintainable/portable code - which should be taught in a different class. $\endgroup$
    – nhahtdh
    Commented Jun 30, 2017 at 14:48
  • $\begingroup$ @nhahtdh Then our author should add that : Training students to resolve problems in a Time Frame with the best time/space complexity compromise. Note that sometimes, just translate a given algorithm to C++ solution is not so obvious (dijikstra, handle nodes already visited for instances) $\endgroup$
    – Walfrat
    Commented Jun 30, 2017 at 15:01
  • $\begingroup$ Please feel free to continue your discussion of competitive programming skills in chat. $\endgroup$
    – thesecretmaster ♦
    Commented Jul 1, 2017 at 14:55

9 Answers 9

Reset to default
8
$\begingroup$

Learning and teaching competitive programming depends a lot on what level the students already have. The first step is getting to know basic features of a programming language, preferably C, C++ or Pascal, since some contests require to use one of these. Out of these, C++ is used most.

These basic features include at least: variables, strings, input and output, if and else, while, for, basic manipulation of arrays. In fact, this is usually enough to (theoretically) be able to solve every problem. Of course, built-in sorting functions and things like inteprenting characters as numbers are useful as well. As you say, this is mostly just knowing, and less insight.

Improve someone's problem-solving ability is in the beginning mainly practising, for the problems you don't really need any textbook algorithm or other, more complicated techniques. Besides explaining solutions to problems that the student can't solve but already tried sufficiently hard, there is not very much to teach. The "tried sufficiently hard" is important: you learn this problem-solving ability the best when doing this.

After that, on a higher level (e.g. National Final Round, or even the IOI), the students need some standard textbook algorithms (e.g. Dijkstra's algorithm) and other techniques, and you can teach this. You can find all the topics you might want to teach in the IOI syllabus.

Improve this answer
$\endgroup$
7
$\begingroup$

I'll answer the second part before the first one:

I'd recommend Project Euler. Many problems, at varying difficulties. Just starting to solve them, from the start, and sticking to it. The variation in the problems gives students a very handy skill set for solving problems.

As for the competitive programming, Project Euler is arguably still useful here. But I think it would be even better to form a few groups of students (2-3 students per group). Ask each group to write a program\algorithm that would complete some task (such as pathfinding or something similar) and the algorithm that completes the task in the best way (you can decide how to define "best", but I'd go for minimal complexity and execution time) wins. This teaches them teamwork as well.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I'm not a big fan of Project Euler. A lot of the problems are maths problems, not algorithm problems, they both require and provide little insight into computer science. (Unless the insight you want to convey is that domain knowledge often beats programming knowledge.) $\endgroup$
    – Jörg W Mittag
    Commented Jun 30, 2017 at 10:17
  • $\begingroup$ @JörgWMittag The idea is giving them problem solving skills. $\endgroup$
    – ItamarG3
    Commented Jun 30, 2017 at 10:24
  • 1
    $\begingroup$ @JörgWMittag I very much disagree with you about Project Euler. I once had (but now can't find) a list of p.e. problems broken down by CS principle. They really are fairly brilliant problems. However, if you want something less math focused, you may enjoy Programming Praxis. $\endgroup$
    – Ben I. ♦
    Commented Jun 30, 2017 at 12:21
5
$\begingroup$

You need to help your students develop algorithmic thinking, I would think. As wythagoras mentions, there isn't really an easy way to teach this—like many skills, it is best developed by practising, doing lots of different problems across a broad range of topics.

I've mentioned Codewars in a previous answer, and there are various other 'online judges' available in the awesome-algorithms list.

If you want to teach some of the most common algorithms that can just be 'slotted in' to a problem, there are some resources available under the 'Websites' section. This is the bit where you can help—teaching sorting algorithms through 'human sorting' is entertaining and does help to introduce and reinforce the algorithms.

Ultimately, you can't teach problem-solving in the same way as just teaching a specific topic, but you can facilitate it through adapting your lessons to require some problem-solving rather than just telling your students what they need to learn directly. Giving them the resources to practise writing algorithms from a text-based 'design brief' is probably the best you can do here, so I highly recommend it for your problem.

Improve this answer
$\endgroup$
3
$\begingroup$

Having coached several teams that have been beaten soundly by Steve Skiena's teams, I will recommend his book on Amazon. The Table of Contents includes:

  • Data Structures
  • Sorting
  • Combinatorics
  • Number Theory
  • Graph Algorithms

None of these chapters will turn a beginner into an expert, but with a bit of prerequisite knowledge, it can help bridge the gap between "good student in class" and "good programming contestant".

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Adding an abridged table-of-contents of Skiena's book to your answer would make it better. As it is, only those that already know the book or follow the link to browse its contents will understand what it is all about: providing a basic set of tools and discussing the main problem types found in ICPC-lilke programming contests $\endgroup$
    – tucuxi
    Commented Jun 30, 2017 at 13:47
  • $\begingroup$ Thank you! I'm still learning what makes answers valuable. $\endgroup$
    – Chris M.
    Commented Jun 30, 2017 at 14:56
  • $\begingroup$ Please also summarize the content of those chapters. The goal is for this answer to be useful even without the link. $\endgroup$
    – thesecretmaster ♦
    Commented Jun 30, 2017 at 15:01
3
$\begingroup$

When I participated in the ACM International Collegiate Programming Contest back in college, our preparation involved a LOT of practice. We poured through the ACM-ICPC archives and worked on doing the old problems. Our adviser went over a few key algorithms and concepts that we'd almost certainly run into (searches, sorts, etc).

I would highly suggest looking at the ACM-ICPC Live Archive for an insane amount of sample programming problems.

Improve this answer
$\endgroup$
2
$\begingroup$

It takes theory and practice. Theory involves learning algorithms, programming concepts, and when/why/how to use them. It's important to have lots of practice. This is easier when it's fun, for example:

  • Robocode - think BattleBots, but in Java
  • Google Code Jam - many archived problems, some easy, some hard
  • King of the Hill - this is a game I developed where students battle to insert many records into a simple MySQL table. The student with the most records at the end wins. This is probably the most fun learning activity I have ever presented.
Improve this answer
$\endgroup$
1
  • $\begingroup$ Those three are very different to each other. Robocode is great for AI-like courses, Code Jam is much more algorithms oriented, and as for KoTH - I assume that whoever writes a tight insert-loop soonest wins? $\endgroup$
    – tucuxi
    Commented Jul 1, 2017 at 17:07
2
$\begingroup$

Websites such as https://www.codeeval.com and https://coderbyte.com are great for students to practise this type of competitive programming activity.

In order to prepare them for that type of competitive challenge it can be good fun to create opportunities for competition and collaboration early on when you're introducing new programming concepts.

For example:

  1. Split students into groups
  2. Give all students some code that is deliberately incomplete or broken.
  3. Award points to the first person who fixes the errors or completes the challenge
  4. Once someone in the team has finished, their job is to support the other students without touching their mouse or keyboard. Award points to the first whole team to complete the challenge.

You can get a fast-paced, fun lesson where there's enough challenge to get the brightest students being competitive with enough support for those who take more time to understand and complete the work.

Improve this answer
$\endgroup$
2
$\begingroup$

I think you should develop your practice plans based on the competition that you're preparing for. I'm a high school teacher that has brought teams of students to Lockheed Martin's Code Quest for the past several years. Many of the problems can be solved by students towards the end of their year in AP CS. The additional training my students need is with File I/O.

The best way to do that? A quick chalk-talk on I/O and then practice old Code Quest problems. Project Euler problems are excellent challenging programming problems, but they won't prepare my students nearly as well as old Code Quest problems.

Take a look at what contest your students are competing in and work old problems (often readily available on the contest's website). Simulating the experiences that your students will encounter at competition is their best practice.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Those are great resources. It's always a pleasure to welcome a teacher to our little community. Welcome to Computer Science Educators! I hope we hear more from you in the future. $\endgroup$
    – Ben I. ♦
    Commented Jul 6, 2017 at 22:03
1
$\begingroup$

I can recommend giving your students some tasks from Codility, like this one on Iterations or these ones on Sorting. There are several different tasks sorted by topics and a PDF with explanation provided for each topic. Another benefit of those is that your students will have an opportunity to practice for job interview tasks they will face in the future.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.