Gọi hàm next(film_id, shift)b là hàm trả về bộ phim thứ shift sau film_id.
Dễ dàng có được next(film_id, 1) với mỗi film_id.
Dễ dàng tính được next(film_id, 2^p) với mỗi F và p.
Công thức truy hồi:
next(film_id, 2^p) = next( next(film_id, 2^p-1), 2^p-1)
Let next(F, n) be the n-th movie after some film F. We are given next(F, 1) for each F. Is is possible to easily calculate next(F, 2p) for each F and p as
next(F, 2p) = next(next(F, 2p−1), 2p−1).
From the binary representation of M we can easily calculate next(F, M) using pre-calculated shifts for powers of 2. The overall time complexity is O(N log M + K log M). By carefully ordering the operations, the model solution does not need to keep the entire precomputed table in memory, but only for adjacent powers of 2. The memory complexity is O(N + M).