Google I/O 2011: Programming Well with Others: Social Skills for Geeks

Great show by Brian Fitzpatrick & Ben Collins-Sussman at Google I/O 2011. Interesting answers to everyday Software Engineering :-)

Matrix Exponentiation

Recently I stumbled upon this problem and could not solve it right away. I could immediately grasp the problem asked to solve a linear recurrence. I first thought of a dynamic programming solution but given the constraints of this problem, the technique would not be fast enough. It was later that I found about the "magic" of Matrix Exponentiation. Unfortunately, the online literature on this technique is quite limited. Here I attempt to glue all the pieces together. Please let me know what you think.

BASICS
Before continuing, we must be clear on some points about linear recurrences. First, on the definition. Linear recurrences are recurrence relationships of the form:

                         \(a_n = c_{1}a_{n - 1} + c_{2}a_{n - 2} + \dots + c_{k}a_{n - k} \).

So, given a set of initial terms, further terms can be evaluated by linearly combining previous terms. 

Second, on the representation. Linear recurrences can be represented as vector equations. Take Fibonacci, for instance:

                          \(f(n) = f(n - 1) + f(n -2)\).


This is probably the linear recurrence most known by computer scientists. Its \(f(n + 1)\) term would be equal to \(f(n) + f(n - 1)\).  We can represent this as a vector equation:

                       \( f_{i + 1} = (M)(f_{i}) \).

Here, \(f_{i}\) is a vector that contains the previous terms on which \(f_{i + 1}\) is defined and M is a constant matrix multiplier. Please note M contains the most basic terms (those on which you do not need to use recursion to find). Then:

\( \left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \end{array} \right) \ \left( \begin{array}{c} f(n) \\ f(n - 1) \end{array} \right) = \left( \begin{array}{c} f(n+ 1) \\ f(n) \end{array}\right)   \)


THE TECHNIQUE
Matrix Exponentiation is based, well, on "exponentiating" (raising a matrix to a given power k) in order to find the kth term of a linear recurrence. That is, \( f_{k} = M^{k}x_{0}\).  Roughly, you need to follow these steps in order to solve a linear recurrence problem:

1. Identify the linear recurrence. This is probably the hardest part.
2. Express the linear recurrence as a vector equation of the form \( f_{i + 1} = (M)(f_{i})\).
3. Raise the constant M matrix to the desired k-th power.

I know this is far from obvious. In an attempt to clarify, let's work out an example:

\(F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5\).

\(\left( \begin{array}{c c} 1 & 1 \\ 1 & 0 \end{array} \right)^{4} = \left( \begin{array}{c c} 5 & 3 \\ 3 & 2 \end{array} \right) \)

Here's the calculation in WolframAlpha: http://www.wolframalpha.com/input/?i=%7B%7B1%2C+1%7D%2C+%7B1%2C+0%7D%7D%5E4

The answers are equivalent, \(F(4) = 5\). Try decomposing the recurrence to the finest grain possible and then factorize. You will notice that Matrix Exponentiation does exactly the same, in Matrix terms.

FIGURING M OUT
The recurrence relation may come in different forms. The process however is exactly the same: express it as a vector equation. Identifying the constant matrix M may be the hardest part. In general terms, what you always have to do is find such a square matrix M that, multiplied by the vector \( f_{i}\), produces the vector \(f_{i + 1} \).

For example, if we are given the following recurrence: \(f(n) = af(n - 1) + bf(n - 3)\). Here, \(f(n + 1) = af(n) + bf(n - 2)\). So:

\( \left( \begin{array}{c} f(n + 1) \\ f(n) \\ f(n - 1) \end{array} \right) =
\left( \begin{array}{c c c} a & 0 & b \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{array} \right) \left( \begin{array}{c} f(n) \\ f(n - 1) \\ f(n - 2) \end{array} \right)
\)

SPEED 
How fast is Matrix Exponentiation? If you implement Fast-Exponentiation , then raising a square Matrix of size d to its k-th power is guaranteed \(O(d^3 \log{k})\) worst time. That's pretty damn fast compared to a \(O(k)\) solution if k is very big.

Coding style in Programming Contests

I am relatively new to the world of competitive programming (catharsis: WHAT a PITY I didn't know anything about the IOI and ACM-ICPC during my highschool and undergraduate years). Working my way in, I've been studying the coding style of more experienced coders at sites such as Codeforces and TopCoder. I dare to classify the coding styles as:

• Class "A": Rather beautiful, eyes-safe code
• Class "B": Totally ugly, disgusting-looking

This is an excerpt of a Class-A code:

int current = 0;
int remaining = 0;
int answer = 0;

for (int i = 0; i < count; i++) {
    remaining += fuel[i];
    remaining -= distance[i];
    if (i == next[current])
        current = i;

    answer += distance[i];
    if (remaining < 0) {
        int refills = (-remaining - 1) / fuel[current] + 1;
        answer += refillTime * refills;
        remaining += refills * fuel[current];
    }
}
out.printLine(answer);

And this one from a Class-B code:

int N=size(a);
LL V=0;
REP(i,N) REP(j,i) V+=a[i]*a[j];
REP(i,N) if(a[i]>=3)V+=(a[i]-1)*(a[i]-2)/2;
return 1+V+N;

For the Captains Hindsight : they are not solutions to the same problem. They are however rather different:

• Class-A code has descriptive variable names.
• Class-A code has no literal constants, except for the well-forgiven integer values '0' and'1'.
• Class-A code has well spaced-out constructs. Take a look at the for loop, for example. That's certainly more appealing than for(int i=0;i<count;i++){
• Class-B code defines macros whose functionality is already defined in the language. In the excerpt for Class-B, for instance, "REP" is just a for loop.
• One-liners of Class-B code can have more than one purpose. Line 4, for instance, defines a for-loop, an if-statement along with its body.

To summarize, Class-A code is much more simple to understand. We are not stupid and we can understand Class-B code, of course. But in general it is much more faster to understand Class-A code, that's just how humans are.

So why do people write Class-B code?

I haven't a single sensible answer to this question. People who defend this coding style do it for some reasons they truly believe. The problem I see in their arguments is that most of them can be ruled out ONLY by two factors: the human brain and the editor you use. Here are some common arguments, along with my thoughts:

Programming contests are time-constrained, thus you must type faster, less. 

1. These contests are really time-constrained. 01h:15m to come up with solutions to three problems is certainly not an easy thing. However, people who use this argument typically forget that the code they write is actually the product of a challenging intellectual exercise. You can only type-in your code after having understood the problem and coming up with a reasonable model of the solution inside your brain. Thus, even if you use "REP", for example,  you'd still lose to someone who uses a normal for-loop but that can think much more accurately and faster than you. 
2. You don't have to write long constructs. Mainstream editors/IDEs these days have code auto-complete. You type "for" and it replaces it with a full for-loop template.
3. You can use code snippets. These work in consonance with the auto-replace feature. Type something in and it gets replaced by whatever you want it to. I have a snippet called "lend" that introduces a '\n' character, for instance.

I write code for the computer to comprehend, not humans.

1.  That's not completely true. Yes, the Judge's computer is the ultimate destination of your code, and you will never see that code again (probably). However, your code may contain bugs. Isn't it easier to debug Class-A code? I definitely think so. For the sake of it, imagine you are using a visual debugger, as the ones in MS Visual Studio, Eclipse, IntelliJ. You click on a line you want to pause at to check the state of your program. "REP(i,N) if(a[i]>=3)V+=(a[i]-1)*(a[i]-2)/2;" Where will the pause happen? At the for-loop? At the if's conditional? At the if's body? it's certainly cleaner and confusion-free just to have lines with unique purposes for this matter. 

I've seen [insert high rated coder handle here] using this style, it's gotta be for something.

1. Have you checked out Petr's, Egor's, SnapDragon's code? They are among the tops of the world and they all write Class-A code. I've however seen many lower-rated coders writing Class-B code. There's no relationship between Class-B code and higher-rated coders. 
2. Have you considered they do because they adopted someone else's style? Maybe you're doing the same thing. This is epidemic. I've seen people using Class-B code for open SPOJ problems. What's your argument for this case? Here you are not competing.

By writing this way I make it harder for people to challenge/hack my code.

1. You got me there. That's true. That demotivates me. Is it really worth it, nonetheless?

To summarize, there's not a sensible need for Class-B code. Speed of typing does not translate to submitting a solution faster. Thinking faster and accurately does. If you really want to submit a solution faster, what about working on your logical and mathematical thinking skills?

Codeforces Round #158 - Editorial (Unofficial)

Problem A - Adding Digits

We can solve this problem by construction. Start with the initial integer a. Choose among ['0' .. '9'] a digit that, appending it to the right of a, makes a divisible by b. Then the problem is almost solved. For the next n - 1 operations, we can just right-pad the constructed integer with zeroes, as it doesn't affect divisibility (reason: if a is divisible by b, then (10^k)a is also divisible by b).

In the case that we are unable to choose a satisfying digit, then we cannot come up with an integer satisfying the problem description and we must output -1. The complexity is O(n).

Problem B - Ancient Prophesy

This problem is very easy for coders using Java, Python, C# or any other language that supports Regular Expressions. Let S = {all distinct strings that match to the following regex: [0-9]{2}-[0-9]{2}-[0-9]{4}}. Then the solution is such string s of S that has the maximum occurrences in the prophesy string. The catch is that the only matching strings we are to take into account are those that correspond to dates between 01-01-2013 and 31-12-2015. 

The problem can also be solved by brute force. We just consider all valid dates from 01-01-2013 to 31-12-2015 and pick the one with the highest count within the prophesy string. There are in total 1095c operations.

Problem C - Balls and Boxes

Simulation is a naive way to solve this problem. Starting from box at index x, move from right-to-left (mod n) and take one ball out of the i-th box until B[i] = 0. Now the i-th box was the starting box. Put all the balls back into B[i]. Solved. Not really. As a_initial  can have as many as 10⁹ balls, this will take about 1,000,000,000c operations and will time out.

Given that Vasya runs out of balls at index x, the starting box must be the one with the minimum number of balls to the left of x (mod n). Let's denote by mini the index of the initial box and by tt the amount of balls in B[mini] after the arrangement. We must consider two cases:

1. mini < x. All boxes between mini and x, inclusive, received one ball more than mini. So, deduct tt + 1 from them, and tt from the rest.
2. mini > x. The balls from x + 1 to mini, inclusive, must have tt balls deducted from them. The rest, tt + 1.

Put all the balls you previously deducted and add them to B[mini]. Problem solved. Complexity is O(n).

Problem D - Black and White Tree

Like problem A, this problem can be solved by construction. We must come up with  n - 1 edges, that is, the total number of edges in a tree with n nodes. Let's put all the white and black nodes in queues WQ and BQ, respectively. n - 1 times we will do this:  pop the head of each queue into w and b. We now have two cases to consider:

1. w.sV > b.sV. b will become a child of node w and we subtract b.sV from w.sV. As w.sV is greater than zero, we put w back into WQ.
2. b.sV > w.sV. Similar to the previous case.

After doing this, we have come up with a new edge: an edge connecting w and b. All we're left with is the situation where w.sV == b.sV. We'll take as parent the one whose queue is smaller in size. At the end, every edge with weight 0 can be safely constructed using remaining vertexes whose sV equals 0.

Problem E - Dividing Kingdom

I'll update when I solve it :)

Binary Tales and Compiler Wisdom

From time to time we have all needed to check the parity of an integer. A natural modus operandi is given by primary school math: divide by two and check whether the remainder is zero (even) or one (odd). In C/C++ this would be expressed as:

bool odd = n % 2;

Beyond doubt, this is correct. However, if you remember from your comp-arch class that there's no constant-time division operation implemented in current-day processors, and that instead the functionality is implemented as a sequence of subtraction operations, then you might start thinking the costs involved in the parity-check operation (N/2 operations that yield an O(N) upper bound). 

So, what do we do to speed this up? One thing is to take advantage of the binary representation of integers. Given that the less significant digit of an odd number in binary representation will always be turned on, we could make use of the bitwise AND operator and check N AND 1. Here's an example:

5              0101 &

1              0001

           __________

                 0001

Because (N = 5) AND 1 = 1, N is an odd number. Processors are able to do this operation in O(1). So, by using the bitwise AND, we have reduced the time consumed by a factor of n (thus, O(1)). Here's how this is expressed in C/C++:

bool odd = n & 1;

But the question is, should we really be using this?

I took the time to study the assembly code GCC produced with both versions. Take a look:

n % 2 

n & 1

Huh! Both codes look ridiculously similar. Take a look at line 14 of either. For the first one, the compiler saw my (n % 2) statement and made the optimization for me. For the second one, it didn't have to. In both it applied the andl statement, which is an x86 asm statement that executes a bitwise AND operation. Thank you, compiler!

This was tested with GCC (mingw) in Windows 7, compiling without optimizations. I'm sure most modern compilers have this optimization as well. There's no real implementation need to use the bitwise AND version. It only makes your code look ugly.