2025 USA-NA-AIO Round 1, Problem 1, Part 9

AI Olympiads 2025 USA-NA-AIO Round 1
1

Part 9 (15 points, coding task)

Define a class called My_Fib.

  • Attributes:

    • Q: This attribute is matrix \mathbf{Q} computed above. It is a numpy array with shape (2,2).

    • lambdas: This attribute is a numpy array with shape (2,) that includes two eigenvalues computed above.

  • Method __init__:

    • All atttribute values shall be initialized when an object in this class is constructed.

  • Method compute_fib:

    • This method computes the sequence values on designated indices.

    • You must use the spectral decomposition result to write this method.

    • You are not allowed to use any loop.

    • Inputs:

      • f0: The value of F_0

      • f1: The value of F_1

      • indices: a list/tuple/range object that includes indices with which the sequence values shall be computed.

      For instance, if indices takes the value [3, 5, 9], we need to compute F_3, F_5, F_9.

      In our test cases, you are guaranteed that len(indices) is at least 1. You do not need to worry about the size of the test cases or whether the sequence values are too big (that is, on your side, you do not need to worry about those corner cases).

    • Outputs:

      • Return a numpy array fib_values with shape (len(indices),) and datatype int32.

      • fib_values[i] takes the value of F_{indices[i]}.

      For instance, if indices takes the value [3, 5, 9], then fib_values has shape (3,). The values of fib_values[0], fib_values[1], fib_values[2] are F_3, F_5, F_9, respectively.

    • Inside this method:

      • Print fib_values.

  • Method plot_fib:

    • This method plots indices vs. sequence values on those indices.

    • Inputs: The same as the method compute_fib(f0, f1, indices).

    • Outputs: None.

    • In your plot,

      • All data points with input indices are with marker x.

      • The linestyle is --.

      • The color is red.

      • The x-lable is: n.

      • The y-label is: F_n.

      • The title is: Fibounacci sequence.

2 
### WRITE YOUR SOLUTION HERE ###

class My_Fib:
    def __init__(self):
        self.lambdas = np.array([(1 + 5**.5)/2, (1 - 5**.5)/2])
        self.Q = np.stack([self.lambdas / np.sqrt(1 + self.lambdas**2), np.ones(2) / np.sqrt(1 + self.lambdas**2)])

    def compute_fib(self, f0, f1, indices):
        fib_values = (np.power(self.lambdas, np.array(indices)[:, np.newaxis]) / np.sqrt(1 + self.lambdas**2)) \
                         @ (self.Q.T @ np.array([f1, f0]))

        fib_values = fib_values.astype(np.int32)
        print(fib_values)
        return fib_values

    def plot_fib(self, f0, f1, indices):
        fib_values = self.compute_fib(f0, f1, indices)
        plt.plot(indices, fib_values, marker = "x", linestyle = "--", color = "red")
        plt.xlabel('$n$')
        plt.ylabel('$F_n$')
        plt.title('Fibounacci sequence')

""" END OF THIS PART """