Competing tomek-style

By brett1479
TopCoder Members

Introduction: A Recipe for Success
Ever wonder what allows certain TC members to solve 3 hard problems in under an hour, while others struggle to submit a single solution? This question has both fascinated and puzzled me for some time.

Since his first competition 2 years ago, tomek has consistently dominated in the arena. Perhaps most impressive is his stellar tournament record. Seemingly unfazed by the high stakes, tomek always competes at a practically unbeatable level. What allows him to win so frequently under any and all circumstances? What are the secrets behind tomek's skill?

Natural Born Competitor
As early as elementary school tomek was participating in math competitions. These opened the doorway to Polish science camps, and eventually the opportunity to study abroad in England. In high school, at the Polish Olympiad in Informatics, tomek began to show interest in the theory of algorithms. Years later, during ACM challenge training, he was able to hone these skills and help his team win at the World Finals. If it hasn't become clear already, tomek loves to compete. Through this passion, he has had many achievements, and reached a level attained by few.

I have spoken to many people about their careers, academics, hobbies, and lives in general. Frequently their eyes light up while describing the projects they work on, or the goals they have set for themselves. Too often these aspirations are pushed aside and forgotten. Most amazing is to later see someone who conscientiously followed their pursuits, since they typically bear no resemblance to their former self. University Highlights
Discussing university courses, tomek and I agreed that professor quality is frequently more important than subject matter. At the University of Warsaw, Krzysztof Diks and Marcin Kubica were two of his favorite lecturers. When asked which courses he liked best, tomek replied with the following lists:

• Favorite CS Courses: Algorithms, Introduction to Programming in OCAML, and Automata Theory.
• Most Useful Courses: Probability and Statistics (with Calculus), Algorithms, and Discrete Mathematics.
• Favorite Math Courses: Advanced Calculus, Set Theory, and Logic.

Being an educator, I am interested in the educational choices made by the professors at other institutions. As such, I was surprised to learn that all CS majors at Warsaw are required to take separate courses in Set Theory and Logic. These two topics, which have always been personal favorites, are rarely mandatory CS courses.

tomek's Picks
Our school conversation finished with a discussion about great books. tomek said the following resources proved most useful for TopCoder.

• Introduction to Algorithms by Cormen et al. - Assuming you have the mathematical maturity, this text provides an excellent treatise on algorithms. tomek mentioned how this book entertained him during the less eventful nights he spent in England.
• Concrete Mathematics by Knuth et al. - An interesting and sometimes quirky textbook covering the core mathematical prerequisites for Computer Science. This was used in the Discrete course at Warsaw University, and proved both educational and enjoyable.
• Programming Pearls by Jon Bentley - A great book that helps to develop your "approach" to coding. An easy read containing many invaluable coding tips.
• Sphere Online Judge - Great resource for programming practice.

Competition Tips
Preparation only gets you so far. Once the competition begins, your skills are put to the test. Here are some tips from the master competitor:

• Have a strategy planned before the competition. tomek said his ACM team had, down to the minute, a schedule planned for each round. This itinerary even included mandatory breaks for strategic planning.
• Plan out your entire solution before you start typing. If necessary, make notes about all necessary data structures and algorithms on a piece of paper.
  "Generally, I don't want to make decisions during coding. Coding should be quick and one should concentrate on not making mistakes rather than thinking about the solution."
• Proofread your code believing you have an error in it. tomek says this `self-deception' is immensely helpful.
• And last but not least, tomek's step-by-step problem solving guide:
  1. Transform English into math. Resolve problem ambiguities. Verify your understanding by perusing the example cases. Examine the constraints for useful information. Before you can solve the problem, you need to know what is being asked.
  2. Search for an algorithm. For easy tasks, you may recognize the solution immediately. If not, try to decompose the problem into simpler subproblems. If neither of these work, give yourself time to discover the answer while you work on each example case by hand.
  3. Knowing when to move on. Don't lose the competition just because you are angry at one problem. The next problem may be better worth your time.
  4. Sketch it out. Unless the solution is trivial, sketch out the details on paper. Make a note stating the purpose of each data structure. Label what each function does, and what the parameters hold. Write some very terse pseudocode if necessary. The amount of writing varies with ability and experience. Don't start typing until everything is laid out.
     "I learned this at ACM practice - being forced to work on paper with no terminal access, I found I would solve the problems quicker."
  5. Type it in. At this point, the thinking is over. Your mind is free to proofread while you code. Practice is required to make this step automatic. In Chess, if you don't know how the pieces move, you can't even play, let alone strategize. At TC, this means being comfortable with your preferred programming language and the associated libraries. The problems are hard enough without having to fight with the compiler.
  6. It doesn't always work the first time. Sometimes you have a small bug. Other times you need to optimize. Worst case scenario, your solution is fundamentally flawed. It is frequently easier to scrap it and start fresh than patch a broken implementation.
  "At the last TCCC my solution was a bit too slow and I never got it to work but could have easily rewrote it."

Final Remarks
Will carefully following all of the steps listed here make you tomek? Probably not, but they could make you much better. And who knows? Take a little motivation, combine it with some focussed training, and maybe you will make a name for yourself in the arena. People might start asking you for advice on how to improve. Perhaps there will be an article with your name on it.