Bitwise 2007

Yesterday while chatting with one of my numerous net-pals I got the information about Bitwise 2007. It is an online programming contest organized by the Computer Science and Engineering Department Society of IIT Kharagpur. It was being held on Feb 11 from 1300 to 0100 (according to Indian time).

I was too late to participate; the registrations had already closed on Feb 10. Nevertheless, I was inquisitive enough and checked out their website. My friend's ID and password opened the door for me. The competition is on a total of 2400 points divided into 10 questions each of different weights. The winner is the team who submits the correct solutions to the problems and gets the highest marks.

The problems given were quite impressive. Some of them were newer versions of some of the classic CS problem. Being a CS student myself, I downloaded them in no time. All of them are available from their site without any registration whatsoever. All the problems were in a story like format with "Santiago" being the protagonist.

The first problem was on devising an algorithm to find the centre of a tree. The organizers also provided a sample test case along with the problems to help participants gauge the success of their algorithms. I found the problem quite interesting and wrote a sample code myself. Although they were not submit-able, I wrote them just for an interesting time pass. Here is the code along with the problem.

The second problem was a variation of the classic denominations of money problem but with a twist on the minimum number of coins that the person has to take per denomination. Everybody studying CS has at one point of time or other solved this problem, but this new added constraint proved too much of a thought process for my brain and I moved on to next problems, in search of greener pastures.

Problem 3 was on job scheduling, with job dependencies and concurrent executions. It reminded me of my graduation classes on PERT and CPM, where we had to draw elaborate diagrams on process dependencies and time taken for various jobs.

Problem 4 was a 2-tier problem with classic problems in both the tiers. The first is the well-known problem of toggling of doors (or light bulbs) by persons each of whom toggles every i-th door. However, there was a minor twist to this problem; the toggles could start from left or from right. The next tier comprised of the classical "Tower of Hanoi" problem with a fourth stick thrown in for added complexity.

The next problem, number 5 was a new one to me and I solved it. Here is the code. This problem mentions a data type "long long int" of which I was completely unaware of before. Later however I crosschecked and found that it is indeed a data type able to store 64-bit int. You can never say that he has completely learnt C.

Problem 6 was a heavyweight problem, i.e. one with high points. Nevertheless, it came across as quite easy to me. Here is the code. Nevertheless, beware that this solution was not a submitted one, and judging by the 400 points associated with this problem, it seems to me that there might be more to this problem than what is apparently visible.

Problem 7 was another well-known one but with a twist. The classic problem was to find the continuous run of numbers with maximum sum within a linear array of numbers containing both +ve and -ve numbers. As usual, here the problem appears with a twist of selecting a run of length ≥L and with highest average value.

I did not find enough time to muse on the rest of the problems (8, 9 and 10). I will come back with them soon. In the meanwhile, if you manage to find a better solution to the problems that I have solved, do post it here. This also applies to the last three problems, which I did not have time to think of.