SPOJ ASCDFIB – Ascending Fibonacci Numbers

forthright48 on November 22, 2018

SPOJ ASCDFIB – Ascending Fibonacci Numbers is one of the earliest problems I created. This problem was used in one of the internal contests of Daffodil University. I was aiming for an easy, but a tricky problem and thus the following problem was created.

Problem

Read the complete description of the problem from SPOJ ASCDFIB – Ascending Fibonacci Numbers.

Before you continue reading the rest of the post, please try to solve the problem on your own.

Problem Summary

  • Given $A \leq 10^5$ and $B \leq 10^6$
  • Print from $fib(A)$ to $fib(A+B)$ in ascending order.
  • $fib(n)$ is $n_{th}$ fibonacci number mod $10^5$.
  • If there are more than $100$ terms in output, we need to print just the first $100$.
  • There are $100$ test cases.

Solution

  1. First calculate value of $fib(A)$ using $O(A)$ loop.
  2. Next, using a $O(B)$ loop, generate all terms from $fib(A)$ to $fib(A+B)$ and store them in an array $V$.
  3. Sort the array $V$ and print the first $100$ terms.

Simple right? But there is a catch. What is the complexity of the third step?

If you use normal built-in sort function, then the complexity of the third step will be $O(B \times logB)$. And this is too slow for the current problem since there are $100$ test cases.

Notice that all the value in the array $V$ is smaller than $10^5$ since we are using the mod value. As such, we can use counting sort to sort the array in $O(B)$ complexity. And this is the trick to solving the problem.

If you don’t know how counting sort works, watch the following video:

Using counting sort, our overall complexity for the solution becomes $O(B)$, which is fast enough to get AC.

Conclusion

When creating this problem, I was hoping that people won’t be aware of $O(N)$ sorting algorithms. And for those who know the counting sort algorithm, I was hoping they won’t remember about it since it’s not very usual to have a problem that revolves around counting sort. Well, I hope the same for my readers :p

Let me know what you thought about the problem. Did you get TLE?

Reference

  1. Problem Link: SPOJ ASCDFIB – Ascending Fibonacci Numbers
  2. Counting Sort Video: Counting Sort | GeeksforGeeks
Post Views: 201