Let's consider the problem of converting a number to base k. Initially I was confused by this algorithm, but the more I think about it the more it makes sense.

The algorithm is this. For a number n in base 10, if we wish to convert n to base k then we do the following.

digits = []
while n > 0:
    digit = n%k
    digits.append(digit)
    n /= k
n_k = reversed(digits)

where n_k is the number n in base k.

Why does this work? Well the first thing to notice is that for any natural number base k we can write a number n in base 10 in the following way.

n = sum of i from 0 to infinity of c_i*(k^i)

where 0 <= c_i < k. ***

As a concrete example consider writing 11 in base 3. By the above declaration we can write the following.

11 = 1*3^2 + 0*3^1 + 2*3^0

Now why is this useful? Well if you read off the coefficients from left to right of the above expression, that is 11 in base 3!

11_10 = 102_3

where n_k is the number n in base k.

So given this fact, we just need a way to read off the coefficients of each of these terms. Here is an algorithm for doing so.

1. Read off the rightmost coefficient
2. Shift all the terms rightwards while eliminating the rightmost term
3. Go back to step 1

We can accomplish step 1 by doing n % k.

11 % 3 = (1*3^2 + (0*3)^1 + 2*3^0) % 3
       = 0      + 0       + 2

To see why this is the case note that all the terms except the rightmost term have a modulus of zero (because they contain at least one factor of 3). So doing the modulus has the effect of reading off the rightmost coefficient.

Now how do we do step 2? We just do n / k. Let's look and see what that does.

10 / 3 = [1*3^2      +  0*3^1     + 2*3^0] / 3
       = (1*3^2)/3   + (0*3^1)/3  + (2*3^0)/3
       = 1*(3^1)     +  0*3^0     + 0
       = 1*(3^1)     +  0*3^0

Notice the last term zeros out because there is no factor of 3.

So it looks like we've done the main things required to convert to base k. As a last (and small) order of business notice that we've accumulated digits from right to left and hence they are backwards. We only need to reverse them to straighten them out.

*** A proof of this fact is outside the scope of this guide (I'm sure there is a proof out there somewhere). To convince you that this is true, consider that if it was not true then we wouldn't be able to use binary nor octal nor hexadecimal to represent numbers (why?).

For 750B - New Year and North Pole, test case #4 reads as follows:

input

3
20000 South
10 East
20000 North

output

NO

Why is the output NO? My understanding is we start off at the north pole and march 20000 km south to reach the south pole. We then attempt to move 10 km east, but since we're at the south pole, we actually just spin around (?) and move nowhere because every direction is north. We then march 20000 km north and reach the north pole. By this logic, the answer should be YES.

What am I missing? It has to be the 10 East line I'm misinterpreting, right?

Fun fact: from beginning to end this blog post took me 16 months!

This will be a tutorial on simulating recursion with a stack. I developed this tutorial after using this technique to solve 472B - Design Tutorial: Learn from Life.

Consider the following recursive definition of the factorial() function.

def factorial(n):
   return n*factorial(n-1) if n>1 else 1

This definition is compact, concise, and mirrors the definition that appears in math textbooks very closely. In many ways it is the most natural way to define factorial().

However, there is a problem. For very large values of n, you will see that we will get a StackOverflowError.

To understand why this is the case, you must understand that recursion is implemented in Python (and most other languages) as growing and shrinking a stack in memory.

For example, consider the following simulation of the computation of factorial(3).

That is, to compute factorial(3), we need to compute factorial(2) and then multiply the result by 3. Since we have very specific instructions to perform after computing factorial(2) (i.e. multiplying by 3), we need to save these instructions so we can come back to them after computing factorial(2). This is accomplished by saving our local state (e.g. local variables) on a stack and then shifting our focus to factorial(2). We repeat this process until the values of factorial(2) is computed.

To more closely mirror the stack simulation, we can rewrite our definition of factorial() as follows.

Here, it is more clear as to the order of operations. We have distinct regions of code corresponding to first checking for the base case, then making the recursive call if that condition is not met, and instructions after the recursive call (as well as instructions for computing the base case).

If we wish to convert our recursive definition to an iterative one we can do so with the following transformation.

And here is what it looks like.

Note that the RESULT above the table refers to a global variable "outside" of the stack.

How this proceeds is that while there is something on the stack we pop it off and perform the action that's associated with it. The first entry on the stack should be intuitive. Our goal is to compute factorial(3) so we put a call to factorial(3) on the stack.

In the CALL case, we unpack the associated data in that entry (i.e. the function arguments) and execute the body of the function. If we hit the base case we "return" by setting a global variable which can be checked by the "caller". If we hit the recursive case we do something fancier.

In the recursive case we put entries on the stack to simulate recursion. That is, the next time we pop an entry from the stack, we should find a function call. If that is the base case, then the next time we pop from the stack we should get the value from that function call and resume execution. That is exactly what is going on here.

What if we had multiple recursive calls in our function? The only change we would have to make multiple return actions (i.e. RESUME1, RESUME2, ...) for the number of recursive calls in our function.

What about code before checking for the base or recursive case? That code would go right above the case check (in the body of the action == CALL conditional).

I hope you enjoyed it!

This is a post describing my solution for 617B - Chocolate.

For this problem, the key is to view the act of breaking the candy bar as a sequential decision process. In a sequential decision process, we have a number of choices to choose from at each stage. Once we know how many possible choices each stage has, we can apply the rule of product and multiply these numbers to arrive at the total number of possible outcomes.

The candy bar-breaking sequential decision process proceeds as follows:

1. Start at the left side of the candy bar
2. Keep marching until we get between two nuts
3. Make a break somewhere between these two nuts
4. Go back to step 2

In step 3, there are several legal break points. If there are n zeros between the two nuts, then we can make a break so as to give 0 zeros to the left nut and n zeros to the right nut, or we can make a break so as to give 1 zeros to the left nut and n-1 zeros to the right nut, and so on. In total, we have n+1 decisions for this particular break.

To help visualize this process, consider the sequential decision making process described above on the sequence 10101:

We first consider nuts 1 and 2 and see that there is only one zero in between them. Hence we can make a total of 2 different breaks, as pictured by the two branches. After making this first break, we proceed to nuts 2 and 3. Once again, there is only a single zero between these two nuts, hence the number of breaks we can make here is 2. Notice the rightmost column enumerates all possible breaks, which is computed by multiplying these numbers for a total of 2*2 = 4 possible breaks.

One edge case that is useful to consider is when there are leading and/or trailing zeros. Note that for each of these cases there is only one legal break we can make among these regions of zeros. To see why this is the case, consider the case of leading zeros; the only legal break point is before the first zero as any other break would result in a piece of chocolate with zero nuts. The same holds for trailing zeros, except the only legal break is after the last zero. Since the number of possible breaks in both of these cases is 1 and multiplication by 1 has no effect on the final answer, I simply stripped leading and trailing zeros instead of explicitly coding for these special cases.

Every time I use Euclid's algorithm, I have to re-convince myself why it works. This blog post will provide an explanation of Euclid's algorithm so I can refer back to it in the future. Hopefully it will also be useful for others!

Euclid's algorithm can be expressed in just a single line of python (assuming b >= a):

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

The base case of this algorithm is quite reasonable; it says the largest number which divides both any number and 0 is just that number. The recursive step requires a bit more explanation, however. For ease of explanation, consider the following diagram (courtesy of wikipedia):

Say we are interested in computing gcd(BA, DC). One very helpful way to think about recursion is as a black box. What if we had gcd(DC, EA)? Could we use it to compute gcd(BA, DC)?

As an aside, we can think of a number b dividing a as being able to "stack" columns of length b to reach a height of exactly a.

Let n = gcd(DC, EA). What do we know about n? Well, by definition n divides both DC and EA (and is the largest such number that does so). Because n divides DC, we can stack multiple copies of n to get up to a height of exactly DC. n also divides EA, which is exactly how much height remains to reach BA. Hence we can continue the stack to get all the way up to BA. Therefore n dividing DC and EA implies n divides BA!

An explanation for my solution to 466C - Number of Ways. Credit goes to Coding Hangover for the algorithm. This post will detail the approach outlined there, explained with an example.

Problem Statement

Given an array arr, compute the number of ways we can partition arr into three chunks such that the elements in each chunk sum to the same number. For example, the answer for arr = [1 2 3 0 3] is 2 because we can have the following splits:

• [1 2] [3] [0 3]
• [1 2] [3 0] [3]

We will use arr as our running example throughout.

Naive Approach

First, define S = sum(arr). Verify S % 3 == 0. If this is false, then it is impossible to partition arr into three equally sized chunks and the answer is 0.

Else, we continue. Pre-compute array A which is a running sum of arr:

A = [1 3 6 6 9]

Iterate i = 0...n-2 through A until we hit A[i] == S/3. At this point, we have a potential first chunk. We then iterate j = i+1...n-1 through A[i+1:] until we hit A[j] == (2/3)S. This corresponds to a potential middle chunk whose sum is S/3. Note that as long as j < n-1, it is guaranteed that sum(arr[j+1:]) = S/3 because we verified that sum(arr) % 3 == 0 up front. Hence this is a valid partitioning of arr. Repeat this process for each potential first and second chunks.

Unfortunately the runtime for this approach is O(n^2) given the doubly-nested for-loop. Given that n = 5*10^5 in the worst case, in the worst case we will perform (5*10^5)^2 = 25*10^10 operations, which will take approximately 250 seconds. Clearly this is too long. Given the maximum value of n, we need to cut down the runtime to O(n*logn) at worst.

A Better Algorithm

It may be surprising that there is actually a O(n) solution. The intuition is that we will still iterate i = 0...n-2 through A identifying potential first chunks. But instead of having to iterate linearly through A[i+1:] to compute the number of ways A[i+1:] can be split up into 2 chunks each having S/3 elements, we will pre-compute another array which will allow us to compute this value in constant time.

To this end, we pre-compute an array is_suffix where is_suffix[i] = 1 if sum([i:]) == S/3 and 0 otherwise:

is_suffix = [0 0 0 1 1]

Then we compute another array nb_suffix where nb_suffix[i] = sum(is_suffix[i:]). In words, nb_suffix[i] is the number of suffixes contained in arr[i:] that sum to S/3:

nb_suffix = [2 2 2 2 1]

Now we have everything we need. We iterate i = 0...n-2 through A until we hit a potential first chunk. Then the number of ways to split up arr[i+1:] into 2 chunks whose elements each sum to S/3 is simply nb_suffix[i+2]. Why i+2? Because we need a first, second, and third chunk. nb_suffix[i+2] gives us the number of valid last chunks. For each of these last chunks (say it starts at index k), the corresponding middle chunk (which starts at j = i+1 and ends at j = k-1) is guaranteed to sum to S/3 because the first and last chunks sum to (2/3)*S and we verified up front that S % 3 == 0.

This post will be a tutorial on 313B - Ilya and Queries, as well as some general python I/O optimizations that provided me with enough of a speedup to have my solution finish in the allotted time.

Solution

As an example, consider the input string #..###. From it, we create arrays

• S = [ # . . # # # ]
• A = [ 0 1 0 1 1 X ] = [ a_1 a_2 a_3 a_4 a_5 a_6 ]

where

• S is an array encoding the input string.
• A[i] = 1 if S[i] == S[i+1] and 0 otherwise (A[-1] is undefined).

Let f(l, r) be a function where f(l, r) = a_{l} + a_{l+1} + ... + a_{r-1}. Clearly f corresponds to a query in 313B - Ilya and Queries (convince yourself if you don't see it!).

A naive solution is to compute f(l, r) iteratively (i.e. by looping from l to r-1). However, the runtime of this algorithm is O(nm) = O(n^2) as 0 <= m <= n. Hence, in the worst case we will do (10^5)^2 = 10^10 operations as 0 <= n <= 10^5, which is too large a number for the allotted time. Hence we need to do better.

One idea is to pre-compute f(l, r) for 0 <= l < r <= n so we can look up the answer for any (l, r) pair. However, it turns out this table has 10^10 elements in it, so it won't do. But the general idea of pre-computing is good so we explore it further.

It turns out that instead of pre-computing every possible f(l, r) pair, we can pre-compute a smaller number of values which we will then be able to use to very quickly to compute any f(l, r) pair we want. Consider the following function F(r), where F(r) = a_1 + a_2 + ... + a_{r-1}. The key observation is that f(l, r) = F(r) - F(l). To see, this consider f(2, 5):

f(2, 5) =       a_2 + a_3 + a_4 
        = a_1 + a_2 + a_3 + a_4
        - a_1
        = F(5)
        - F(2).

Hence all that remains is to compute F(r) for 0 <= r <= n. Note that this cuts the runtime down by a factor of m to O(n*1) = O(n) as F(l) and F(r) are constant-time lookups.

I/O Optimizations

Even with this optimization, my python solution was still exceeding the time limit. After profiling my code, I discovered I/O was the bottleneck. I replaced

for _ in range(m):
    l, r = [int(num) for num in raw_input().split()]
    print A[r] - A[l]

with

lines = sys.stdin.readlines()
inputs = [[int(num)-1 for num in line.split()] for line in lines]
outputs = [str(SA[r]-SA[l]) for l, r in inputs]
print '\n'.join(outputs)

Eliminating the repeated calls to raw_input() and print gave me a substantial speedup which was fast enough to have my solution finish within the allotted time!

The "minimum" part of this problem was particularly challenging for me. I could see that we need to create m teams as "uniformly" as possible, but I was having a lot of trouble coming up with how to compute that. Hence this post explains the intuition behind distributing n participants into m teams as uniformly as possible.

Note: as a matter of notation, the quantity n / m denotes integer truncating division throughout.

In hindsight, the reason this problem gave me so much trouble is because it demands an understanding of n % m that I did not initially possess. My tried and true understanding of n % m has always been

n = (n/m)*m + n%m.

In english, Equation 1 can be read as "starting with n participants, we can form n / m teams, each having m participants, plus some leftover participants." However, 478B - Random Teams requires a fixed number of teams (i.e. m), so this interpretation will not do. With this in mind and by a twist of perspective, we can rewrite Equation 1 as

n = m*(n/m) + n%m.

It may look like we've accomplished nothing with this rewrite, but we can now read this in a more useful way! Concretely, Equation 2 can be read as "starting with n participants, we can form m teams, each with n / m participants, plus some leftover participants."

As a result, we now have m teams which are uniform as can be (they all have an equal number of participants!). All that remains is to distribute the leftover participants as uniformly as possible into the m teams. It is not hard to see that the way to accomplish this is to add each leftover participant to a different team. As a result of this process, we wind up with

n = (n%m)*(n/m + 1) + (m - n%m)*(n/m).

This can be read as "starting with n participants, we can form m teams. n % m of those teams have n/m + 1 participants in them (because there are n % m leftover participants). m - n%m of them (i.e. the rest) have n / m participants in them."

As an example, consider n = 8 and m = 3. Beginning with Equation 2, applying the procedure which follows, and arriving at Equation 3, we have

8 = (2 + 2 + 2) + 2 
  = (2+1 + 2+1 + 2) + 0
  = 2*(2+1) + 1*2
  = (8%3)*(8/3 + 1) + (3 - 8%3)*(8/3).