Pedro Matias

About Archive

HackerRank Week of Code 19 (Part II)

Problem Scalar Products from HackerRank’s Week of Code 19 was quite an interesting one to solve. Despite being labelled “Difficult”, there were more accepted answers than in the previous problem Two Robots, which was supposedly easier to solve.

Problem description

Integer sequence $a$ having length $2n+2$ is defined as follows:

  • $a_0 = 0$
  • $a_1 = C$
  • $a_{i+2} = (a_{i+1} + a_i) % M$, where $0 \le i \lt 2n $

Write a function generator, $gen$, to generate the remaining values for $a_2$ through $a_{2n+1}$. The values returned by $gen$ describe two-dimensional vector $v_1 \dots v_n$, where each sequential pair of values describes the respective $x$ and $y$ coordinates for some some vector $v$ in the form $x_1,y_1,x_2,y_2, \dots, x_n,y_n$. In other words, $v_1=(a_2,a_2),v_2=(a_4,a_5), \dots ,v_n=(a_{2n},a_{2n+1})$.

Let $S$ be the set of scalar products of $v_i$ and $v_j$ for each $1 \le i,j \le n$, where $i \neq j$. Determine the number of different residues (modulus $M$) in $S$ and print the resulting value modulo $M$.

Constraints

  • $1 \le C \le 10^9$
  • $1 \le M \le 10^9$
  • $1 \le n \le 3 \times 10^5$
For more details and input/output samples, check the original problem description.

Solution

First, let’s think of a naive solution to this problem. We have $n$ vectors and we know how to compute scalar products for every pair of vectors. So, we need only to add the results residues to a set (to avoid repeated elements) and output the size of the set modulo $M$. Problem? Kind of, the number of vectors might be as big as $n=3 \times 10^5$, which makes a quadratic solution inefficient.

We know that the number of vector pairs is at least $\Omega(n^2)$. So, how in the universe could we get a solution faster than a quadratic one? We somehow need to take advantage of the structure of the sequence $a$.

Hint: Fibonacci sequence

To avoid spoils and let you think on the problem without accidentally looking through the solution, you need to press the button below to reveal it.

It’s easy to see how the sequence $a$ is an extension of the Fibonacci sequence $F_i=F_{i-1}+F_{i-2}$ (with $F_0=0$ and $F_1=1$):

This is because,

So, we figured out something about the problem, but how can we make use of that? In this case, trying a few examples with pen and paper helps to see the pattern. Let’s write down the Fibonacci sequence:

The parentheses group the sequence elements into the $2$-dimensional vectors that we’ll need. If we take the scalar product of vectors $(1,2)$ and $(3,5)$ we get $13$, which happens to be part of the sequence! We can repeat this process with other vectors to realize that the result of scalar products is given by a deterministic position in the sequence, which can be computed according to the positions of the vectors we are multiplying. More specifically,

Clearly, we can extend the formula to compute elements of $a$ by making the necessary adjustments. Hence, the solution to the problem is given by the number of distinct elements in the sequence

where

Proof sketch of \eqref{rec}

Since all $v_k$ are themselves defined by Fibonacci sequence elements, we want to compute the following expression recursively:

We ended up with a similar expression, but somehow easier one: we moved the terms indexed by $\alpha$ one position to the left in the sequence and, similarly, moved the $\beta$ indexed terms one position to the right, at no cost.

Now, we can take advantage of the base cases of $F$ to simplify the expression. We can repeat the above process until $\alpha=F_0=0$ and when that happens, we have:

Code

The input format is explained here.

#!/usr/bin/env python3

def solve(C, M, n):
    residues = set()

    fib = [0, C % M] + [0] * (2*n + 2*(n-1))
    for i in range(2, len(fib)):
        fib[i] = (fib[i-2] + fib[i-1]) % M

    residues = set()
    for i in range(3, 2*n):
        residues.add( (fib[2*i+1] * C) % M )
    return len(residues) % M

if __name__ == '__main__':
    C, M, n = map(int, input().split())
    print(solve(C, M, n))