post

Programmer’s Gags

Here is a collection of funny programmer’s jokes of my choice, from all around the web. Have fun!

Random Number


Password Strength

[Read more…]

post

An Interview with rng_58, Our New SRM Coordinator

The 2011 TopCoder Open is over. Makoto Soejima, with his famous handle rng_58, won the Algorithm Track. He successfully defended his champion title after winning last year’s TCO. An impressive two-streak win!

Who would ever think that the TCO11 Championship Round was his last SRM? Yes, starting from SRM 520, he became a new algorithm coordinator, replacing Ivan Metelsky (mystic_tc).

Of course, this is a very interesting promotion. Unfortunately, this happened so fast that we couldn’t actually know what has happened behind the scene. So, I contacted Makoto and “interviewed” him with some questions. It was actually possible after we prepared SRM 520 together, with me as the writer and Makoto as both the tester and the new coordinator.

Here it goes… [Read more…]

post

Integrating TopCoder Arena in Ubuntu Menu

Are you a regular competitor of TopCoder SRMs? If yes, then probably you have been launching the Arena by (double) clicking a sacred file named ContestAppletProd.jnlp somewhere in your computer. You must have been doing that every time you want to participate in an SRM.

I felt that looking for that file before every SRM is quite tedious, and putting the file in my desktop is not an elegant way. So, I added a launcher to TopCoder Arena in Ubuntu GNOME menu. It is very handy, so I would like to share how to do that. In this tutorial, I am using Ubuntu 11.04 Natty Narwhal.

First things first:

post

Solving Linear Recurrence for Programming Contest – Examples

After grasping the basic method of solving linear recurrence, let’s apply it in real problems.

SPOJ Recursive Sequence

This is a classical problem that is directly solvable using the basic method I explained in the previous post. It is expected that you solve this problem and master the basic method before solving the next problems.

SPOJ Recursive Sequence (Version II)

A slightly harder version of the previous problem. This time, instead of determining a_{n}, we have to determine a_{m} + a_{m+1} + \cdots + a_{n}.

Let’s simplify the problem first, using a well-known technique called partial sum. Define a series S, where S_{i} = a_{1} + a_{2} + \cdots + a_{i}, with S_{0} = 0. Then, the result we are looking for is exactly S_{n} - S_{m-1} (prove that). So, instead of determining (n – m + 1) terms of sequence a, it is sufficient to determine only two terms of series S.

How to compute S? The crucial observation is that S_{i} = S_{i-1} + a_{i}, i.e., S itself is a linear recurrence! So, we can adopt the matrix equation of a to incorporate S. The final matrix equation of would look like this:

\begin{bmatrix}1&1&0&0&\cdots&0\\0&0&1&0&\cdots&0\\0&0&0&1&\cdots&0\\0&0&0&0&\cdots&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&c_{k}&c_{k-1}&c_{k-2}&\cdots&c_{1}\end{bmatrix} \begin{bmatrix}S_{i-1}\\a_{i}\\a_{i+1}\\a_{i+2}\\\vdots\\a_{i+k-1}\end{bmatrix} = \begin{bmatrix}S_{i}\\a_{i+1}\\a_{i+2}\\a_{i+3}\\\vdots\\a_{i+k}\end{bmatrix},

with initial values:

\begin{bmatrix}S_{0} = 0\\b_{1}\\b_{2}\\b_{3}\\\vdots\\b_{k}\end{bmatrix}.

After finding the matrix equation, S_{n} and S_{m-1} can be computed easily: S_{n} is the first row of T^{n}F_{1}, and S_{m-1} is the first row of T^{m-1}F_{1}.

You may also want to solve SPOJ Fibonacci Sum. It uses exactly the same idea. [Read more…]

post

Solving Linear Recurrence for Programming Contest

One of the topics that often arises in programming contests nowadays is about solving linear recurrence. It may come as a classic “find the n-th term of Fibonacci sequence” to more complex and creative forms of problems. Usually, after being simplified, the problem is merely asking you the n-th term of a linear recurrence. It should be able to solve with dynamic programming, however, the problem is that usually n can very large.

Because this topic starts to emerge in contests, I would like to share how I usually solve problems of this topic.

Definition

First, let’s start with a definition. A linear recurrence relation is a function or a sequence such that each term is a linear combination of previous terms. Each term can be described as a function of the previous terms. A famous example is the Fibonacci sequence: f(i) = f(i-1) + f(i-2). Linear means that the previous terms in the definition are only multiplied by a constant (possibly zero) and nothing else. So, this sequence: f(i) = f(i-1) * f(i-2) is not a linear recurrence.

Problem

Now, let’s state the problem formally.

Given f, a function defined as a linear recurrence relation. Compute f(N). N may be very large.

How to Solve

Here is the method I usually use in programming contests. I break down the method into four steps. Fibonacci sequence will be used as an example. [Read more…]

post

Add Epsilon Before Casting Double to Integer!

Problem: Given a real number in exactly two digits after the decimal point, and another integer. Print their product, rounded down to the nearest integer.

You may start to code this way:

double a;
int b;
cin >> a >> b;
int c = a * b;
cout << c << endl;

Do you think this is correct? Well, almost. Now, try this input:

0.94 8700

What will the output be? [Read more…]

post

3 Ways to Define Comparison Functions in C++

One of the reasons that programming in C++ is superior to Pascal is the existence of STL (Standard Template Library) that contains many useful containers and functions.

There are many C++ STL functions that require the underlying parameter to have an ordering, such as sort(). Obviously, you can only sort a collection of objects if you can tell whether an object must come before another, so it is important to learn how to define an ordering in a class.

There are also many C++ STL containers that require the underlying type to have an ordering, such as set<T> and priority_queue<T>.

This post describes how to define an ordering of a class so that it can be used in C++ STL containers or functions that require ordering. As a C++ programmer you definitely need to know these methods. [Read more…]

post

Alex’s Adventures in Numberland

“If there was one book that was going to be compulsory for the nation to read it would be this one”Evan Davis

Recently I bought a very entertaining book, Alex’s Adventures in Numberland (somehow it reminds me of Alice’s adventure). Yep, as the title says, it is mainly about the world of maths. Fortunately, you don’t have to be a real geek to enjoy reading this book — it is aimed for everyone, the language used is not as geeky as the title sounds.

For most people, the world of maths may seem too puzzling and impractical for daily life. Yet Alex Bellos, the author of this book, shows us that there are so many beautiful phenomena in our daily life based on mathematics. He talks about his adventure in meeting many mathematics researchers while traveling around the world.

This book consists of eleven unrelated chapters; you may read them in any order you please. [Read more…]