Facebook Hacker Cup 2011 Round 2 Problem 1 – some discussion

Posted on February 7, 2011. Filed under: Uncategorized | Tags: , , , , , , , , , , , |

(see also the discussion of problem 3)

Facebook’s Hacker Cup online round 2 took place recently. The first problem (‘Scott’s New Trick’) was about counting products of elements of two series which are smaller than a given value L, modulo a given prime number P (see http://www.facebook.com/hackercup and links therein to see the exact problem statement). These two series were defined as linear homogeneous recurrence relations with constant coefficients.

The brute force approach consists of explicitly calculating all products of the two series (which have length M and N respectively), resulting in a complexity of O(M*N). With M and N allowed to go to ten million, M*N can be as high as 1014. Even if one was able to test one pair per processor clock cycle, it would still take 105 seconds (more than a day) with a 1 GHz processor with this approach in the worst case.

As we are performing operations on a finite field GF(P), one could imagine that the series of values starts repeating at some point and thus one would not have to calculate pairs of products of all elements of a series but only look at the elements of one period.

However, each element ai was defined in terms of its two preceding elements ai-1 and ai-2 so there are P*P different states (rather than P) when generating the series and thus the period of the two series is bounded by P2. With a maximum value of 250’000 for P, P2 is 62.5 billions in the worst case, corresponding to 62.5 seconds worth of CPU cycles on a 1 GHz processor. Moreover, the two series a and b need not have the same period and thus one would have to consider the least common multiple in terms of number of pairs of the two periods, which is O(P4) in the worst case and thus not feasible.

A more elegant idea is to just count the number of occurrences of each of the possible P values in each series a and b, test for all possible products of integers ai, bj smaller than P whether they satisfy the condition (to be less than the given number L) and then weight the accepted products with (number of occurrences of ai) * (number of occurrences of bj). Such an approach reduces the complexity from O(N*M) to O(M+N+P2). However, this is still at least at the limit for the calculation of 20 test cases within six minutes if not impossible.

A more efficient solution makes use of discrete logarithms. In other words, we write each integer xi as xi = gyi where yi is called the discrete logarithm of xi with respect to the basis g. g is must be a primitive root modulo P to ensure that for any integer xi ∈ [0..P-1] there is a value yi which satisfies this equation. It takes O(P) time to calculate a map of all xi to their logarithms yi by simply calculating the powers 0..P-1 of g by repeated multiplication. Thus we can reformulate our problem from:

  • find all pairs of elements of the field GF(P) whose product is equal to a given value V

to

  • find all pairs of elements of the field GF(P) whose sum is equal to a given value loggV

where we would vary V from 0 to L-1. Note that taking the logarithm of each element in GF(P) simply corresponds to a reordering of the elements which we have to take into account when considering how often an integer appears in the sequences a and b (see above).

What do we gain from this transformation ? When writing down the transformed task as an equation, we want to calculate:

u_k = \displaystyle\sum_{i=0}^{P-1} w_i \cdot v_{k-i}

where wi and vi are the number of occurrences of element gwi in the series a and gvi in the series b, respectively. uk is thus the sum of the products of all weights (i.e. number of occurrences) associated to pairs whose product is gi + (k-i) = gk. k is the discrete logarithm of V (introduced above) with respect to the base g.

Naturally one would think that one would need to calculate P products for these P equations (k ranges from 0 to P-1), thus still requiring O(P2) operations. However, looking at it a bit more carefully, one realizes that this in fact a discrete (circular) convolution. And for this task, fast convolution algorithms exist which have O(P * log(P)) time complexity. One common approach for fast convolution is to transform the two sequences into Fourier space (using a fast Fourier transform) where the convolution of the series corresponds to the product of the transformed series and transform them back to the original space (using the inverse transform).

Another possibility is to use a Karatsuba like algorithm for convolution which has time complexity O(P1.585). This algorithm is designed to multiply two numbers written as xn * bn+…+x0 * b0 and yn * bn+…+y0 * b0 where the xi and yi are the ‘digits’  and b is the radix. On the other hand, multiplying these two sums is this equivalent to finding the convolution of the series of coefficients x and y.

Advertisements
Read Full Post | Make a Comment ( 3 so far )

Liked it here?
Why not try sites on the blogroll...