------------------------------------------------------------------------------ ASM Programming Suggestions by Shane Brinkman-Davis (brinkmas@colorado.edu) Updated on 11/4/2003 ------------------------------------------------------------------------------ Before the Contest ------------------ 1) Bring books to the contest. You are allowed to bring any printed materials. So, DO! The books that are most useful are language and library references (C/C++ for most people), math books (ones with equations like geometric, vector and trig stuff are a good idea), and algorithms books. Also, there is often a problem that requires calculating with big numbers (100 decimal digits or more). It is a good idea to solve +/-/*/div/mod for large numbers and bring the solution with you. Lastly, bring snacks and drinks so you can keep your body in a productive mode throughout the contest (be nice to the computers). You should also bring scratch paper (graph paper is also a good idea), writing tools and highlighters. 2) Learn how to do I/O better than you know how to tie your shoe! I strongly suggest if you are using C -OR- C++ to use these functions for I/O (#include stdio.h and stdlib.h): Input: fgets (and then sscanf sometimes) fscanf feof (to detect the end of the file) Output: fprintf Every problem I have ever seen can be done easily with these three functions. Typically you will only use fgets OR fscanf for a problem. Mixing them can cause subtle errors. If you need both, I suggest fgetsing a line in and then using sscanf on the string. Look these functions up and become fluent with them. Know how they respond to the end of the file. WARNING: DO NOT MIX C++ and C-style IO! You will run into more subtle problems because they use different buffers. (Above is C-style, if you didn't know.) Starting the Contest -------------------- 1) Scan all of the problems before you start. 2) Start with the problem you can get done quickest. Since the score for each finished problem is the time from the beginning of the contest to the problem's completion (plus 20 for each wrong submissions), spending an extra 10 minuets on the first problem adds 10 minutes to every other problem you finish. Remember, the easiest problems can be anywhere in the problem set. 3) As you start that first problem, make a template file with the basic I/O, headers and a shell 'main'. You can then copy this for every problem - speeding you up. During the Contest ------------------ 1) Read the problem slowly and carefully. Note and HIGHLIGHT the key facts and boundary conditions. 2) Test your solution against the sample input and come up with new tests to test ALL boundary conditions you found in 1). If n can go from 0 to 10000, the judges will certainly test 0 and 10000 and lots in between. The judges will NEVER give your program invalid input. So, don't spend time testing for it and giving errors; you won't need it and it will slow you down. Just remember, the judges will try the nastiest VALID cases they can to see if your code works for all valid input. 3) Just like when you are taking a test, if you are stumped on one, problem, don't hesitate to switch to another one. Don't get stuck on one problem for too long; if you feel you aren't making progress, try another one. One year when our team went to internationals, two of them spent the entire 5 hours on one problem. They kept saying they were soooooo close, just one more try. They never got it. 4) Always do a detailed verification that your output exactly matches the problem's description. Check spacing, alignment, formatting, spelling, as well as correctness. Assume the judges are doing a case-sensitive, byte-for-byte comparison (unless they say otherwise)! 5) Wrong submissions are costly and experience has shown that many are due to rushing a submission. Always go through the following checklist immediately before you submit: a) Is the source-code filename correct? b) Is its output exactly right? c) Have you tested the all sample input with THIS submission? d) Have you tested the all boundary conditions with THIS submission? e) Is the input coming from the right place? output going to the right place? Teamwork -------- Teamwork. At the regionals, you work in teams of 3 to solve the problems. The difficulty is that you only get one computer (and you cannot bring your own to the contest). So, sharing the keyboard becomes a major issue. Practice solving problems on paper so that when you get the keyboard all you have to do is type it up. Also practice debugging on paper so that you can find your bugs while someone else types up another problem (you are allowed you print out your code during the contest). A general rule of thumb is that if you can't find the bug in 5 minutes at the keyboard, give up the keyboard to someone else (if someone is ready). Share problems. In general, one person works on one problem. However, if your solution didn't work, let someone else either read your code or implement their own solution. There is no pride within the group -- the only thing that matters is getting the problems done. Programming Skill and the ACM Contests -------------------------------------- All my suggestions above are things you guys can use for the next contest. Once you've perfected the techniques above (easier said than done), then you can start worrying about improving your programing to do better on the contest. The single most important programming skill for the ACM contest (beyond those mentioned above) is your knowledge of Algorithms. Most any problem can be solve with the careful application of but a handful of the appropriate algorithms. If you don't know the appropriate algorithms, you will spend a great deal more time re-inventing the wheel - if you're lucky. If you're unlucky it is a tricky algorithm that you won't even be able to solve during the contest. When studying algorithms, you are focusing on how to minimize the time or space needed to solve a problem. In the ACM contest you have to "unlearn what you have learned". Usually time and space are not an issue. What matters is how quickly you can implement a solution. There are two things that effect this: 1) How many lines of code (characters) it takes to implement an algorithm 2) How complicated / how well you understand the algorithm. Clearly a longer algorithm will take more time to type up (#1) during the contest, so a shorter one may be preferred. However, you want to make sure you use algorithms that you feel very comfortable with and are simple. You have to not only solve the problems, but solve them "correctly", so your code can't have bugs. The more complicated the algorithm (or the less you understand it), the more likely you'll introduce bugs that you cannot find or fix (#2). At first this will feel very awkward to you. A good example is sorting. We all know that QuickSort or HeapSort (or some variant / combination of those) is the best way to sort things. However, in a programming contest, the best way to sort things is usually Insertion or Bubble sort! Those slow, O(n^2) solutions are prefect for the contest because they are EASY to code and debug... And they are always "fast enough" for the contest. (NOTE - of course you can use standard library functions like "qsort", but make sure you are very comfortable with them! Bubble sort often is faster to code CORRECTLY than a call to qsort.) Good Programming Gone Bad ------------------------- You are starting to see how good programming for the contest starts to diverge from good programming in the real world. "Sloppy" solutions, as long as they are "correct" and not "too slow" are often better than nice "clean" solutions. In addition to inefficient, but easy to code, algorithms, some "bad" programming techniques that are "good" for the ACM contest: 1) Don't check for out-of-bounds input. This is TERRIBLE coding in the real world, but in the Contest you are only wasting your time. The judges will NEVER give you illegal input (unless the program explicitly specifies how you are to handle it - and then it isn't really "illegal" any more anyway) 2) Don't worry about good "object oriented design". If you are a C++ programmer, you learn to think in terms of well designed object structures. This is great for real-world coding, but here its almost always a waste of time. For most problems you won't create a single "class", though you may use many of the standard library classes. 3) If you DO create a Class - make everything PUBLIC. Again, bad programming 101: In the real-world, you should make as much PRIVATE as possible, but this slows you down, causes you to write accessor functions and other things. For rapid prototyping, what you are doing during the contest, make everything public. (NOTE: if you use the "struct" keyword rather than the "class" keyword, everything is automatically public - one less thing to type). 4) Don't worry about good "functional decomposition". In the real world there are many good rules of thumb for how to break your task down into a good set of functions: "Make sure the function embodies just one concept describable by its function-name", "Try to keep functions smaller than your screen-size", "don't copy code, make a function instead", etc... Well, for the ACM contest, forget about them! If it gets the job done, go ahead and write long, multi-task functions with lots of copy-pasted code. 5) Use globals. Real-world - avoid globals like the plague. ACM contest? Use them whenever it makes your task easier. 6) Never EVER write comments! Okay, you can if you must, but basically, why bother? 7) Reserve arrays WAY BIGGER than you need them to be (say 10x bigger). This avoids many pesky off-by one / accessing beyond the bound of the array errors. You start to get the idea. All your schooling is trying to teach you to "think ahead" to problems you'll encounter down the line. Code defensively. Make your code readable, clearly formatted and well commented. In the ACM contest you have exactly 3 priorities. Here they are, most important at the top: 1) Correctness 2) How fast you can code it. 3) and rarely: How fast it runs. Coding Efficient Solutions -------------------------- As mentioned above, usually the efficiency of your solution is irrelevant. The rules usually say "make sure your program runs in a couple of seconds". On todays machines, any data the Judge is likely to give you can be processes near instantly with even the slowest algorithms. However, there are a few problems where the judges intentionally test your understanding of algorithm efficiency. In these problems there is usually an "obvious" solution with is Exponential (O(a^n)) in its timebound. In these situations, when the judge gives you and input of, say, 50 lines, your program may not finish before the end of the century. In these cases, there is usually an "efficient" algorithm that runs "instantly". It may be a little tricky, but it usually isn't any longer. A good example of this is calculating Fibonacci numbers. The Fib sequence starts off with 1, 1. Each new number in the Fib sequence is just the sum of the last two: 1, 1, 2, 3, 5, 8, 13, 21, etc... Since the nth number is defined recursively in terms of the preceding two, it is easy to write a recursive solution to this problem: int fib(int n) {if (n<2) return 1; return fib(n-1)+fib(n-2);} However, each larger 'n' for this alg takes about twice as long as the previous one to computer. So, but the time you get up to, say, 30, we are already talking billions of computations. 40, trillions, 50, quadrillions. The "efficient" way to solve this problem is to start out at the first fib number and run a while loop to get to the one you want: int fib(int n) { int fib1=1; //the number 1 back in the fib sequence int fib2=1; //the number 2 back on the fib sequence for (int i=0;i