July 11, 2008

Programming Challenges: Australian Voting

Filed under: Blog — krkhan @ 10:44 am

PC/UVa IDs: 110108/10142, Popularity: B, Success rate: low, Level: 1

I had 28 (that’s twenty-eight) “Time Limit Exceeded” tries on this problem. I was looking everywhere for a loop that would drag, for every possible input that would cause breakdown and I couldn’t find any such thing. So much so, that I considered labeling this post as Australian Nightmare. The issue, once I found it, had nothing to do with Australia and all to do with the string and istringstream objects being significantly heavy to be constructed/destructed on each iteration of the loop on lines #138-153.

The book recommends further reading on voting systems and has linked to some mathematical theorem that proves that no voting system can ever be perfect. Considering the democratic results around the world in recent elections, yeah, what an absolute shocker.

Tags: , , , , , , , , , , ,

July 2, 2008

Programming Challenges: Check the Check

Filed under: Blog — krkhan @ 7:55 pm

PC/UVa IDs: 110107/10196, Popularity: B, Success rate: average, Level: 1

I had two approaches in mind for checking the check before solving this problem:

  • return a flag value from the move-generation functions as soon as opponent’s king is encountered in a reachable square.
  • Generate all reachable squares for a side first, and then check whether opponent’s king is positioned on one.

I opted for the latter because even though it was more performance-intensive, it made my move-generation functions more generic and appropriate for extensibility.

Tags: , , , , , , , , , , , , , , , , ,

July 1, 2008

Programming Challenges: Interpreter

Filed under: Blog — krkhan @ 8:38 am

PC/UVa IDs: 110106/10033, Popularity: B, Success rate: low, Level: 2

Nothing extraordinarily interesting here — typical straight-outta-the-book exercise.

Tags: , , , , , , , , ,

Programming Challenges: Graphical Editor

Filed under: Blog — krkhan @ 1:31 am

PC/UVa IDs: 110105/10267, Popularity: B, Success rate: low, Level: 1

Few notes:

  • In the problem input, pixels are specified as [column# row#], whereas two-dimensional vectors (or arrays) are referenced using [row# column#] format.
  • The program would be doomed to infinite recursion if the condition on line #51 is omitted.


Tags: , , , , , , , , , ,

June 30, 2008

Programming Challenges: LCD Display

Filed under: Blog — krkhan @ 8:35 am

PC/UVa IDs: 110104/706, Popularity: A, Success rate: average, Level: 1

Two-dimensional vectors again, with an array of function pointers to construct the digits’ appearance.

Tags: , , , , , , ,

Programming Challenges: The Trip

Filed under: Blog — krkhan @ 8:31 am

PC/UVa IDs: 110103/10137, Popularity: B, Success rate: average, Level: 1

I have more wrong submissions for this problem than any other one until now. The reason? I was oblivious to the fact that the default rules for type-conversion between double and long in C++ include floor()ing positive values and ceil()ing negative ones.

Tags: , , , , ,

Programming Challenges: Minesweeper

Filed under: Blog — krkhan @ 8:12 am

PC/UVa IDs: 110102/10189, Popularity: A, Success rate: high, Level: 1

Hello two-dimensional vectors.

Tags: , , , , ,

Programming Challenges: The 3n+1 problem

Filed under: Blog — krkhan @ 8:08 am

PC/UVa IDs: 110101/100, Popularity: A, Success rate: low, Level: 1

The Collatz problem. More of an introductory “hello world” for the algorithmic programming than a “challenge”. But still:

Tags: , , ,

Programming Challenges

Filed under: Blog — krkhan @ 7:58 am

There are few better ways of spending your vacations than trying to solve a series of programming problems, especially when you’re trying to learn something new related to those problems.

And this is where Programming Challenges pops in the picture. It is a combination of book containing about one hundred selected problems from various international competitions of the past. There are two online judges for checking solutions, the book’s own website and another site called UVa Online Judge. I will be constantly keep posting code on my blog as I keep solving problems according to the book’s chronological order.

P.S. Since I wanted to practice STL, please bare with its bloated usage that you’re bound to find in my solutions.

Tags: , , , ,