We present TopCoder which hosts high-quality online programming contests at http://www.topcoder.com/. TopCoder has been hosting programming competitions since 2001

TopCoder hosts high-quality online programming contests at http://www.topcoder.com. TopCoder has been hosting programming competitions since 2001. Each contest consists of four phases:

• Coding phase (75 minutes) - Coders write programs to solve three short problems using C++, Java, C#, or VB.NET. Each problem set consists of an easy, medium, and hard question, the difficulty of which is reflected in each problem's point value. A common point value distribution is 250-500-1000, though this varies; the values of the problems vary from match to match, dependent on the difficulties of each problem. Also, the quicker a coder submits for a given problem, the more points that coder gets.

• Intermission (5 minutes) - After the coding phase ends, there is a short break before the challenge phase begins. This time can be used to think of challenge cases.

• Challenge phase (15 minutes) - Coders can challenge the submitted problems of other participants in their room by constructing test cases in an attempt to generate erroneous output. The challenger receives 50 points for a successful challenge, and loses 25 points for an unsuccessful challenge. If a coder's solution is successfully challenged, that coder receives no points for the problem. Each successful challenge is added to the set of tests to be run during the System-Testing phase.

• System-Testing phase - Each problem that survives through the challenge phase is run on many diverse test cases. Coders are awarded points for problems that pass all test cases, based on the speed and difficulty of problems solved. At the end of the contest, ratings are updated to incorporate each participating coder's performance.

TopCoder hosts weekly online competitions, or Single Round Matches (SRMs). SRMs are sometimes sponsored by outside companies such as Microsoft, VeriSign and award prize money. The TopCoder Collegiate Challenge and the TopCoder Open are the company’s annual flagship events.

The TopCoder organization comprises several groups. Along with powering high visibility programming tournaments, TopCoder also acts as a recruitment center where companies can come and find programmers who are proven to be highly skilled. Additionally, TopCoder Software uses a competitive distributed development methodology for producing commercial grade reusable software components and applications.

TopCoder design and development competitions are week-long competitions. New components are posted every Wednesday, and coders can choose a component from a list of Java and .NET components, and they have a week to design or develop their chosen component. Each week new components are posted. Development components are generally components that have been designed in a previous component design contest.

Coders have since been divided into two divisions, Division I and Division II. Division I consists of all coders with a rating of at least 1200, and Division II consists of all coders with a rating of 1199 or less. Coders are grouped in rooms with other members of their division, in groups of up to 20 coders in such a way that within each division, the average coder ratings in each of the rooms are roughly equal.

The Parts of a TopCoder Problem Statement

Let's look at the composition of a typical TopCoder problem statement. First is the Introduction. Usually, a problem will start off with a high-level description of a situation. This description may be of a real-life situation or it may just be a completely fictional story, serving only to give some sort of context. For many problems the contextual-story itself is not particularly important in understanding the actual problem at hand.

Next comes the Definition section. It gives you the skeleton of the solution you need to write: class name, method name, arguments, and return type, followed by the complete method signature. At the very least, you will need to declare a class with the given name, containing a method which conforms to the given method signature. The syntax given will always be correct for your chosen language.

Sometimes Notes follow the method definition. These tend to be important reminders of things that you should pay attention to but might have missed, or they can be things that are helpful background knowledge that you might not know beforehand. If the notes section appears, you should make sure to read it - usually the information contained within is extremely important.

The Constraints section is arguably the most important. It lists specific constraints on the input variables. This lets you know crucial details such as how much memory to allocate or how efficient your algorithm will have to be.

Finally, a set of Examples is provided. These give sample inputs against which you can test your program. The given parameters will be in the correct order, followed by the expected return value and, optionally, an explanation of the test case.

• Introduction - The problem statement usually begins by motivating the problem. It gives a situation or context for the problem, before diving into the details of the problem. This is usually irrelevant to solving the problem, so ignore it if necessary. The ordering of the rest of this section varies greatly from problem to problem, based on the writing style of the problem author. There will be a description of what you need to do, in high-level terms. Take, for example, UserName (SRM 203, Div 2 easy). What the problem is asking for you to do is to find the first variant of a given username that is not already taken. Note that the problem has not yet said anything about variable names or types, or input formats. There will also be a low-level description of the input. At the bare minimum, the types and variable names of the inputs will be given to you, as well as what they correspond to and what they mean. Sometimes much more information about input formats will be given; this typically occurs in more complicated problems. Sometimes, even more detailed background information needs to be provided. That is also typically given here, or sometimes in the Notes section.

• The Definition - This is a very barebones description of what TopCoder wants you to submit. It gives the class name, the method name to create inside that class, the parameters it should take, the return value, and a method signature. As mentioned before, the basic form of a submitted solution is to create a class containing a method with the required signature. Make sure that the class is declared public if not using C++, and make sure to declare the method public also.

• Notes and Constraints - Notes don't always appear. If they do, READ THEM! Typically they will highlight issues that may have come up during testing, or they may provide background information that you may not have known beforehand. The constraints section gives a list of constraints on the input variables. These include constraints on sizes of strings and arrays, or allowed characters, or values of numbers. These will be checked automatically, so there is no need to worry about writing code to check for these cases. Be careful of the constraints. Sometimes they may rule out certain algorithms, or make it possible for simpler but less efficient algorithms to run in time. There can be a very big difference between an input of 50 numbers and an input of 5, both in terms of solutions that will end up passing, and in terms of ease of coding.

• Examples - These are a list of sample test cases to test your program against. It gives the inputs (in the correct order) and then the expected return value, and sometimes an annotation below, to explain the case further if necessary. It goes without saying that you should test your code against all of the examples, at the very least. There may be tricky cases, large cases, or corner cases that you have not considered when writing the solution; fixing issues before you submit is infinitely preferable to having your solution challenged or having it fail during system testing. The examples are not always comprehensive! Be aware of this. For some problems, passing the examples is almost the same as passing every test case. For others, however, they may intentionally (or not) leave out some test case that you should be aware of. If you are not completely sure that your code is correct, test extensively, and try to come up with your own test cases as well. You may even be able to use them in the challenge phase.

Solving a TopCoder problem

Now we'll walk through a simple problem and dissect it, bit by bit. Have a look at BettingMoney, the SRM 191 Division 2 Easy. First we identify the parts of this problem. In the statement itself, we first have the situation behind the problem - gambling. Then we have a little bit of background information about the betting itself. Then, we have a description of the input - data types, variable names, and what they represent. After this we have the task: to determine what the net gain is for the day and return the amount in cents.

Also note the two explanatory paragraphs at the end; the first provides an example of the input format and types, and the second gives a completely worked example, which should be extremely helpful to your understanding.

The definition section is uninteresting, but it is there for completeness' sake. The notes for this problem are fairly comprehensive. In terms of background information, you might not know that there are 100 cents in a dollar. And in terms of clarification, there is explicit confirmation that the return value may in fact be negative, and that the margin of victory (the variable finalResult) is all that matters when deciding which payoff to make. The constraints are fairly straightforward. The input arrays will contain the same number of elements, between 1 and 50, inclusive. (50 is a long-standing TopCoder tradition for input sizes). finalResult will be between 0 and that same size minus one (which means, if you give it a little thought, that someone will win their bet). Each element of each array will be between 0 and 5000, inclusive. This is most likely to make sure that integer arithmetic will do the job just fine. Finally, there's the examples section. Often, the problem statement section will contain an annotated example case, which will become example case 0. Then there are a couple of other example cases, some with explanation and some without. Also note that one of the examples tests for negative return values, to supplement the notes.

A More Complicated Example

Now have a look at Poetry, the SRM 170 Div 2 Hard. In this case, you may not be able to actually solve this in the time allotted. That's ok - the emphasis should first be on understanding what the problem says, even if you can't code it in time.

The first section tells you immediately what you want to do - you'll be given a poem, and you will have to determine what its rhyme scheme is. The rest of the section clarifies what this actually means, in bottom-up fashion (from simpler concepts to more complicated ones). It defines what a legal word is and how to extract words from a poem, and then it defines what it means when two words rhyme - that their ending patterns are equal. The concept of ending pattern is then defined. After all this, we find out what it means to have two lines of the poem rhyme: their last words have to rhyme. Finally, (whew!) we are told how to actually construct the rhyme scheme and in what format to return it.

This is a problem where a lot of terms need to be defined to get to the heart of things, and so all the definitions deserve at least a couple of read-throughs, especially if you're not sure how they all fit together.

The next section is the problem definition section, just for reference. Then there is a single note that clarifies a point that may have been overlooked when it was stated in the problem statement itself: that blank lines will be labeled with a corresponding space in the rhyme scheme.

The constraints are fairly standard for TopCoder problems: there will be between 1 and 50 lines in the poem, and each line will contain between 0 and 50 characters. The only allowable characters in the poem will be spaces and letters, and there will be only legal words in poem.

Finally, there are a number of examples. Usually, problems which are trickier or which have more complex problem statements will have more examples, to clarify at least some of the finer points of the problem statement. Again, this doesn't mean that passing the example cases given is equivalent to having a completely correct solution, but there is a higher chance that you can catch any bugs or trivial mistakes if there are more examples that you know the answers to.

Try it Yourself

Listed below are a number of additional problems, grouped roughly by difficulty of comprehension. Try them for yourself in the TopCoder Arena Practice Rooms. Even if you can't solve them, at least work on figuring out what the problem wants by breaking it down in this manner.

Mentioned in this writeup:

SRM 203 Div 2 Easy - UserName

SRM 191 Div 2 Easy - BettingMoney

SRM 203 Div 1 Easy - MatchMaking

SRM 170 Div 2 Hard - Poetry

Similar tasks:

SRM 146 Div 2 Easy - Yahtzee

SRM 200 Div 2 Easy - NoOrderOfOperations

SRM 185 Div 2 Easy - PassingGrade

SRM 155 Div 2 Easy - Quipu

SRM 147 Div 2 Easy - Ccipher

SRM 208 Div 1 Easy - TallPeople

SRM 173 Div 1 Easy - WordForm

SRM 162 Div 1 Easy - PaperFold

More challenging tasks:

SRM 197 Div 2 Hard - QuickSums

SRM 158 Div 1 Hard - Jumper

SRM 170 Div 1 Easy - RecurrenceRelation

SRM 177 Div 1 Easy - TickTick

SRM 169 Div 2 Hard - Twain

SRM 155 Div 1 Med - QuipuReader

sum:

0 €

» Library of the Month
» Workshop
» Software Engineering
» Programming Tools
» Interview
» High quality and
secure programming
» Reverse Engineering
» Portable GUI
» Artificial intelligence