JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
1.1. Using Pre-written Code | Reply
This is a rewrite of this recipe, with most comments incorporated. I chose not to add code examples, since they will duplicate most of the code in Chapter 2.

Problem

Sometimes you know exactly what algorithm you should use because you've already faced it a couple of times. Unfortunately, you tend to forget some implementation details, or you simply don't have enough time to code it from the scratch during the competition time frame.

Solution

Have this algorithm pre-written!

You can use pre-written code - libraries that contain implementations of poplar algorithms, helper classes, common macros and constants etc. - basically anything you think might be useful during the contest.

There are three levels of pre-written code:
- low-level: macros and abbreviations (for C++ users) and constants.
- medium-level: simple frequently used algorithms.
- high-level: complicated algorithms which are rare and hard to implement.
Low and medium-level pieces of code save small amounts of time often, while high-level algorithms save significant time seldom.

Discussion

First of all, note that using pre-written code should be totally a competitor's decision. Some people totally reject it or limit it to certain levels for the following drawbacks:
- You can't use home-made code during on-site portion of TC tournaments, and you have only about half an hour to type any code you'll use in coding phase. If you rely too much on your libraries during on-line matches, you might get slow without them. People who follow this style (mostly high-rated members) use only low-level pre-written code which is easy to learn by heart and reproduce any time.
- If you're looking to improve your skills, not only fasten your performance in a particular match, using library doesn't teach you, while inventing and coding algorithm from the scratch will involuntary make you understand it better. People who prefer this style tend to use high-level code with algorithms which are too time-consuming to implement during the match.

If you're not convinced and decide to use pre-written code anyways, there are two extremely important things about it you must know before even starting to write it:
- All code you submit must be written solely by you. Ne exceptions for code you've written in co-authorship, borrowed from an article in educational content, a recipe in this book or from someone who allowed you to use his code. This rule has been questioned multiple times, and TopCoder takes it really serious - and has means of finding out. Just don't use the code you haven't written, ok? You can learn from any source you wish (including this book) but make sure that you don't copy the code.
- There shouldn't be large pieces of unused library code in your solution. Excessive / Extra Code Rule states that your solution can contain at most 300 (non-whitespace) characters or 30% of code which are not used in the actual solution. If your (otherwise correct) solution violates this rule, you'll receive only 20% of this problem's point value. This rule is not precise: automated checks for unused code can be imprecise sometimes, so TopCoder reserves to itself the final decision on each case. However, better safe than sorry - make sure you don't include your whole library in the submission. You also shouldn't comment out large pieces of your code, as all comments are marked as excessive by default.

A few less important but quite useful things you want to take into account while preparing your library:
- You should be able to find the piece of code you need very quickly, so organize your library appropriately. You might separate it into several themed files, or use certain keywords and search for them.
- Try to use classes where it's possible. For example, graph algorithms are easier to use as methods of class Graph which also provides methods for adding vertices and edges. This way you don't use global variables, and you can easily have several graphs simultaneously. The same applies to matrices processing, geometry routines etc.
- Don't make your classes universal. Using one Graph class which implements a lot of unrelated graph algorithms is the easiest way to violate Excessive Code Rule. You'd have to remove unused algorithms,
which takes precious time (unless you've implemented automated removal of unused code). The rule of thumb is: one algorithm in one class.
- Test your pre-written code thoroughly. You have plenty of time to test it when you write it. The last place to look for a bug during the contest is your pre-written code, so be sure it's 100% correct.

Now, let's have a closer look at what you might want to include in your library.

1. Low-level code
Usage of macros and abbreviations is covered in another recipe. Constants can be related to:
- scalar values: a large number used as infinity, a small number used as precision of floating-point values,
- commonly-used arrays: tables of directions used when dealing with grids.

2. Medium-level code
This one usually contains technical pieces of code which don't require special thought but take time to type:

- parsing and formatting routines: most useful to C++ users, but for people who use other languages it might make sense to have non-trivial cases of usage pre-typed.
- minor math routines: calculating binomial coefficients, calculating greatest common divisor, extended Euclid algorithm, Eratosthenes sieve, primality testing, bit counting etc.
- minor geometry routines: classes for processing points, lines, segments etc.

Note that simple algorithms which vary a lot from problem to problem (like BFS, DFS, Floyd-Warshall, recursion and DP) usually aren't worth to be pre-written, since it takes much longer to adapt generic implementation to specific problem than to write them from the scratch in terms of the problem.

3. High-level code
This one involves massive and/or complicated codes and takes a lot of time to prepare and test but can come really handy if you recognize the time to use it and use it fast. It's worth mentioning that problems which are easily done using a single high-level pre-written algorithm are considered unfair and avoided by some problem writers. If you take part in competitions other than TopCoder, high-level algorithms will be used more often, so your library of them will be more helpful.

- math routines: arbitrary precision arithmetics (for non-Java users), vulgar (non-decimal) fractions, matrix operations etc.
- geometry routines: calculating polygon area, checking whether the point is inside of the polygon, finding convex hull etc.
- graph algorithms: maximum flow, min-cost maximum flow, maximum bipartite matching etc.
- data structures: trees, tries (prefix trees), binary indexed tree, segment tree etc.

See also
Basically most of topics of this book's Chapter 2 can produce some kind of pre-written code. Most examples of high-level pre-written code are out of the scope of this book; to learn more about them, you can refer to these books:
...
Re: 1.1. Using Pre-written Code (response to post by Nickolas) | Reply
Oh, I have been tormented with one question about unused code rule for a long time. If I output some stuff into standard error stream during debugging my code, then just comment it out and submit the solution, would these comments be counted as "unused code" or as "comments directly relevant to the code"? In other words, can I violate any rules by submitting a code with a big part of it commented out?

Another point is just sarcastic. How it can be proven that somebody's code is not copied? It seems like the penalty for violating this rule is only remorse.

P.S. Shouldn't answers for these questions be included into this recipe?
Re: 1.1. Using Pre-written Code (response to post by Ferlon) | Reply
Just questions. Will be adding them to the recipe.

For the first one, commenting out big parts of code should fail your solution, but commenting out small pieces like debug output shouldn't - that's the part which is reserved for admins' decision. I think this originated from anti-obfuscation rules, so if your comments look like they affect the functioning and like they were done like that intentionally, they shouldn't be ok.

For the second ones, well, <act mysteriously>there are ways to find out such cases</act mysteriously> but TopCoder prefers that they are not discussed, so we won't :-)
Re: 1.1. Using Pre-written Code (response to post by Ferlon) | Reply
For the automatic UCR checker all comments are treated the same. So if more than 30% of your code is commented out or not called then you will get a warning during submission. You can try this yourself. This flags your submission for the admins to analyze carefully. It is up to the admins to decide what your intentions were, obfuscation or not.
Re: 1.1. Using Pre-written Code (response to post by dimkadimon) | Reply
Well, I always delete debugging part of my code before submitting, not just comment it out. I see it's a strategy that doesn't worth to be changed.

And about the rule disabling copied code... OK, I understand what juridical purposes this rule is imposed for ;) And maybe for people from civilized countries discussing this is too cynical.
Re: 1.1. Using Pre-written Code (response to post by Ferlon) | Reply
"people from civilized countries" LOL
Re: 1.1. Using Pre-written Code (response to post by Nickolas) | Reply
Some coders use an automated anti-UCR solution which automatically adds pieces of the library which are used by the part of program written during contest. This allows one not worry about UCR at all, and additionally, allows shorter compile time, because only #includes which are actually used are mentioned. I think the recipe should at least mention such a possibility.
Re: 1.1. Using Pre-written Code (response to post by Eryx) | Reply
I would be happy to add this note, but I know too little about this solution - could you explain more?
RSS