Problem of the Year

A couple of times I’ve been asked what my favorite CS/programming problem was. I didn’t have a solid answer to give. I’ve seen many interesting problems, many difficult ones, and nearly all of them original. But none of them really stood out, until today.

It’s called Joining Points, from the IOI2006. Here you can download the statement, solution and tests. I must admit I didn’t figure it out on my own — I read the solution. And it blew me away!

I was so impressed that after implementing it, I made a visualizer using the GD library. It has been surprisingly easy, despite being the first time I use such a library. You may see the source and the Makefile. Here’s what my solution produces for one of the test cases. Looks pretty astounding, if you ask me!

To install the GD library on a Debian-based system (in case you decide to compile):

sudo aptitude install libgd2-xpm-dev

5 Responses to Problem of the Year

  1. Alex says:

    Just in case, I’d like to mention a graphical library I’ve been using for my needs – CImg, it is cross-platform, and well documented. And for Python, I use PIL.

    I used CImg to implement various algorithms for processing graphical data – edge detection, blur, noise removal, etc.

  2. Constantin says:

    Looks nice, and object-oriented, not like the C-style GD :)

  3. Constantin says:

    OK, I’ve used it now and here’s my informed conclusion: it sucks. The way to define colors is horrible, and I couldn’t find a way to draw “thick” lines, or un-filled rectangles. CImg seems to be focused on mouse / window interaction, which is precisely NOT what a graphics library is supposed to do.
    GD is a bit better, but still nothing compared to the power of Qt. Unfortunately one can’t use Qt solely for graphical purposes…

  4. […] for IOI2007/practice/chip After doing it the first time, I got the hang of it and now I like doing visualizers a […]

  5. […] another visualizer for an IOI problem, flood this time. It’s a bit more complex than the others, since I had quite a hard time debugging this problem Requires […]

%d bloggers like this: