algorithms

Programming Contest Tips

programming contest

Recently I participated in a few Programming Contests: Garmin Programming Competition 2014, ACM programming contest at my University and Google Code Jam 2014. I also remember my first contest in algorithms KPI-Open 2011, in Kiev, Ukraine. It was for teams up to 3 people. There was 16 problems to solve during 2 days. We solved one.

In some contests, there is no access to the Internet. It was the case during my first contest (KPI-Open 2011). We were able to use Java, C++ or Pascal. First problem we faced was: “HOW TO READ INPUT FROM CONSOLE IN JAVA?”. None of us remembered. Fortunately, we knew how to do it in C++. Thus we had to use C++ for the first day. We were more proficient in Java though and it slower our development. Before day two, we created check-sheet (we could bring as much printed papers as we wanted) with reading input in Java and some other tricks, which you usually google for. It allowed us to solve one problem. By solving problem I mean, to deliver solution, which pass tests in required amount of time. We solved 7-8 problems (or even more?) during those two days, but only 1 got accepted. It gave us 64 place (among 83 teams).

A few months after that, I participated in ACM programming contest at Kansas State University with one friend of mine. There was a progress: 1 problem solved in 5 hours (1 day). It is better that 1 problem in 2 days 🙂 Last year, I was 1-person team, and I got 3 problems solved (I was somewhere around 6-10 place). This year: I also solved 3 problems, but it gave me 3rd place.

Last year, I was also participating in Google Code Jam. In this contest you just need to deliver solution for given input. You download input file from website and you have some amount of time to upload solution (usually up to 10 minutes). Additionally, in most of problems there is small input set and large input set. The large set has more test cases and/or bigger numbers (e.g. int is not enough to solve it).

The most important thing during the Programming Contests is time. Time, in which you solve the problem.

My general tips (based on competitions I participated in) how to prepare for programming contests:

  • Make preparation before. Do not just walk-in (especially if it is your first contest). Check Programming Contest Year Plan – Yes a year Plan to be a better Programmer.
  • Take Introduction to Algorithms book to the contest.
  • Create (and print if no internet access is allowed) template for standard program. 90% of problems has N test cases. You need to parse it, compute solution and print. My approach is to read all input first and serialize it to e.g. Case class. Then I am looping through all cases and printing output. I prepared a template file, which allows me to save time during the contest.
  • Find out what languages/technologies are allowed during the contest and practice with it before the contest. Programming in Eclipse is different than programming in Visual Studio! Especially debugging.
  • Find out how you need to provide solution (send source code or just solution?) and how to read/write input/output.
  • If possible, find problems from previous editions of particular contest and practice by solving them.
  • Don’t be afraid to write bad code. You don’t need to comply with the best practices. It doesn’t matter, whether your code is not SOLID. Your code is not readable? Who cares? Don’t waste time for refactoring. If you really feel bad with the code your have written – refactor it after the contest. The only thing, which matters is, whether it solve the problem efficiently. Check solutions of the best competitors at Google Code Jam World Finals 2013. Can I write better code? Sure I can. But nobody cares, because they (not me) were the best in last year contest.

Solving algorithmic problems is only part of programmers’ skills toolset. If somebody is not good at it, it does not mean he is a bad programmer. He may be good at something else (e.g. programming embedded devices for aircrafts or designing the rocket system). However, it is good to practice problems solving and writing code. It is like daily workout. The programmer who wrote 1000 programs will be always better than one who wrote only 10. You will definitely become a better programmer with programming challenges.

My code for ACM contests and Google Code Jam is available on github:


Garmin Programming Competition 2014

Yesterday at my university, Garmin was hosting the Programming Competition.

Competition like that is a great opportunity to practice programming, algorithms and problem solving skills.

We could form teams of 1-2 students. My partner was Daniel Wang. We could use following languages: C++, C#, Java and Python. We chose Java. We were using Eclipse IDE and git to share the code.

Organizers prepared very real-life problems.

Competitions had two parts:

  1. Read and perform simple input conversion (1 hour).
  2. Reuse code from Program 1 and do more complicated operations with input (3 hours).

We solved part 1 without any problems. Part 2 required two programs: 2A and 2B. We solved both, but our programs didn’t pass all test cases. In 2A: 3/5 test cases passed, in 2B: 4/5. There were points for correct solution and bonus points (depended on the time when solution was submitted). Additionally, there was a timer showing how many bonus points we could earn sending solution now.

You can find problems description here. Our solutions are available on Bitbucket repository. Be aware that it is bad code, written under time pressure and never refactored. However, efficient enough to pass required time constraints. This is how you write code during programming contests 🙂

After competition we asked organizers about test input sets and they sent it to us.

This is the description of the bug we had and how we fix it (you can skip this part if you don’t want to read the description of problems):

The issue we had, was reading (shift mod 26) straight from the input file. Because e.g. shift = 45 should be effectively shift = 19 (45 mod 26). The program should stop when shift = 0. Then, when original shift was e.g. 52 we had stored shift=0 and we stopped (which was wrong). We thought that we should stop when the ‘effective shift’ is 0. Unfortunately, the test cases were stopping when the ‘original shift’ was 0. Fix was pretty easy (we just store two values: shift and shiftOrig for each cell). It would be very hard to fix this without test cases from organizers 😉 It was like in real-life: small detail caused significant error.

The challenge during programming competitions is that you cannot get all test cases. This time, there were 1 sample input per program. Which make sense, because otherwise everybody could just hardcode expected solution 🙂 What is worse, you cannot see the program output (in case of runtime error). Fortunately, guys form Garmin were nice and when we asked, they were showing us the output (on their machine). It helped us (a lot) in fixing the runtime errors (during the competition).

The next event I am looking forward is Google Code Jam. It starts in April 11, 2014 (Friday). Registration begins in March 11. I really encourage you to sign up. You can learn what various problems you can face and what you should consider during writing your programs. Additionally you can practice, apply your programming skills and compete with the best programmers in the World.