109 on 500

Not bad, but Roshan didn't qualify in the first 50 to get to the next round. But a score of 109 in 500 across India is awesome! Shows that he's still the BEST programmer around town. Three Cheers for Roshan.

The questions are:
(as written by Roshan in the email)

1) There's a binary counter, which is mechanical. It's made up of n
bits, which it uses to store a number. Every time a bit changes, it
wears down a little. The counter counts from one number to another,
and you have to tell how many units of wear it undergoes (i.e. how
many bits change in total, throughout all the increments). I did this
one in about five minutes.

2) There's an 11x11 chessboard, which has some number of given rooks
and bishops, placed at given positions. The pieces move in their
normal ways. You have to return how many squares are controlled by the
pieces. A square is said to be controlled by a piece if that piece
could go there in the next move. You have to keep track of the fact
that pieces can't move through others. Did this one too, but was a
little delayed by a stupid mistake I made (comparing Strings using the
== operator rather than the .equals() method in Java) My Java
programming skills are getting rusty, haven't coded in quite a while.
I could have opted for C++, but I'm not quite familiar enough with the
Standard Template Library.

3) You are given an array of arbitrary numbers. You are allowed to
change some of the numbers to other arbitrary numbers. You have to
find the minimum number of changes that can be made to turn the array
into an arithmetic progression. This one was tricky. Took some time
getting my head around it, before settling on a quasi-brute-force
solution. My first try worked for all test cases except one. I
immediately figured out the problem, and was about 5 seconds short of
submitting my fixed code when time ran out.

posted by Shashank Shekhar @ 6:52 PM