PROBLEM LINK:
Author: Praveen Dhinwa
Tester: tncks0121
DIFFICULTY:
Easy
PREREQUISITES:
Adhoc
PROBLEM:
You are given a sequence a_1, \ldots a_n. All the values are positive and \leq 1000. For all i > n, a_i is equal to the floor of the mean of previous n elements of the sequence. Given q queries, each containing an index k, find a_k for each query.
EXPLANATION:
The main idea here is that the sequence would become constant after i > 1000 * n.
Proof:
Clearly, if n consecutive values are equal (to t say), then all the following values must also be equal to t.
Divide the sequence into chunks of size n. Say the maximum value in current chunk is m, and the values in the chunk are not equal. Then, each element in the next chunk must be < m, as the sum of n consecutive elements will always be < m n. This means that the maximum of next chunk is < m.
Since the maximum can reduce \leq 1000 times, the sequence must become constant after 1000n.
So, we precompute the first 1000n values in the sequence by maintaining sum of last n values. To answer a query k, we just return a_{\min(1000n, k)}.
AUTHOR’S and TESTER’S codes:
The author’s code can be found here
The tester’s code can be found here