Frustration during college: solving programming contest problems

During first year in college, I was picked to be part of a team to join a programming competition.

During the competition our team was able to solve only one problem because the problems were hard. They were very much harder that what we were used to solving at school. The judges (or maybe one of the judges) accepted our answer as correct even though our solution did not pass all their test cases. It only passed the sample test case given on the problem. The formatting of our output was even wrong.

Of course the judges did not tell us that our solution did not pass all the test cases but I'm sure it did not. Maybe they accepted our solution so we will not be frustrated and will still join the programming competition the next year.

That experience made me very interested in finding out how to solve those kinds of programming problems.

During my search, I found out that I need knowledge on data structures, algorithms and discrete mathematics, among others, to be able to solve those problems.

Algorithms was hard

So I started reading a book on algorithms in the library. I was able to finish only a few pages.

It was hard, especially when no one is guiding you. And I don’t have a strong background in mathematics.

My algorithms and discrete math classes in college were also of no help because we were still solving simple problems in those classes. (If you want to have an idea on why these classes didn't help, you can read this.) But I am still thankful for the experiences of joining a programming contest because it exposed me to the hard kind of problems that computer science attempts to solve (it's okay with me for now even if I do not know how to solve them).

I was able to join two more programming contests after the first one, but still the problems that our team was able to solve are the simple ones -- the kind of problems called "ad hoc" like the "3n + 1 problem".

Focused on Business Applications

During my later years in college, I decided that I will concentrate on studying how to create business applications rather than solving algorithmic problems because I was thinking that I will not be solving algorithmic problems with the kind of job that I am expecting to have in the future.

Now that I already have a job, I have come to enjoy John Sonmez's blog. In one of his blog posts I read that solving programming contest problems can help enhance problem solving skills.

John Sonmez's blog rekindled my desire to solve algorithmic problems

So I started solving some algorithmic problems again using the UVA Online judge. I was able to solve some "ad hoc" problems and problems that require knowledge on some basic data structures like the stack and queue. (See my User Statistics here)

Recently, reading John Sonmez's blog lead me to the article "Solving Problems, Breaking it down" where I discovered Codility.com.

I am able to solve the first 3 problems in Codility Lessons.

Codility: FrogJmp problem

I followed his advice on solving the problem manually and creating a set of test cases.

This is the screenshot of my manual solution and test cases for the problem "FrogJmp".

My solution to "FrogJmp" can be viewed in https://codility.com/demo/results/trainingTRB9A9-Z7Z/

Codility: TapeEquilibrium problem

"TapeEquilibrium" is actually the first problem I solved on Codility. ("FrogJmp" is the second and "PermMissingElem" the last)

First attempt: https://codility.com/demo/results/training2FDSGB-ZK7/

• Score: 50%
• some incorrect answers and time complexity is O(n^2)

Second attempt: https://codility.com/demo/results/training59H87G-5EE/

• Score: 66%
• correct answers but time complexity is still O(n^2)

Third attempt: https://codility.com/demo/results/trainingX95N7D-W2Z/

• Score: 100%
• time complexity is now O(2n) or O(n); we don't have to compute sum over and over again

Here is the screenshot of my manual solution. Notice that I did not create test cases. That is the reason why on my first attempt I got some incorrect answers.

  

Codility: PermMissingElem problem

First attempt: https://codility.com/demo/results/trainingNH78M7-968/

• Used C

Second attempt: https://codility.com/demo/results/trainingSK8DBT-TK6/

• Used C# instead of C because I thought that the cause of the error is the small size of int in C… but I still get the same results -- wrong answer

Third attempt: https://codility.com/demo/results/training54MQEW-G3C/

• I gave up with my previous method. Here, I created another array with the size of (A.Length + 2).

Some lessons learned

1. Be sure to create test cases when solving programming problems

2. Write your solution on paper first

I hope my knowledge on data structures, algorithms, and discrete mathematics will increase so that I can be able to solve the harder algorithmic problems.

Happy coding!

PS: Please pardon my English.