Sunday, October 11, 2015

Frustration during college: solving programming contest problems

UPDATE [April 1, 2016]: seems like I am ranting in this blog post :) I'm so sorry for that.
Now, I would like to be part of the solution of the "not yet very good*" IT education problem in the my area in the Philippines (Kidapawan, North Cotabato), especially in the software development part of IT. I already sent my resignation letter for my current job and I am planning to finish my college degree. I am hoping that I will become an IT instructor someday for a few years... so that I can help the next generation of programmers in my area to know how software development should be done in the real world.

* I'm not claiming that I am better than my college instructors but I will try my best to become better than them. I believe they will not be insulted if I try to do my best to be better than them because I believe that it should be an honor for a teacher if his/her student become better than him/her. (And I also expect that my future student swill someday become better than me.)

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)
[I would just like to inform the reader that the college I went to was just a small college (or colleges, because I transferred to another college after three semesters). So what is written in the news might not apply to big colleges and universities in the Philippines]

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

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

Codility: TapeEquilibrium problem

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

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

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

  • 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

  • Used C

  • 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

  • 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.