Author: Anshul Asawa
Tester: Jatin Yadav
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Basic Math
PROBLEM:
You are given n numbers a_1,a_2, ... a_n and another number x. Let P= p_1,p_2,...p_n be any permutation of 1,2,...n.
Your task is to find the number of distinct values of ((((x\%a_{p_1})\%a_{p_2})\%a_{p_3}...)\%a_{p_n}
EXPLANATION:
We reduce to the following problem: Given an integer v and set S of values in the range [0, N - 1] represented as a bitset. Find the set of values y \% v for all y in S.
It is equivalent to find a set T of non-negative values t = y - k*v , k \geq 0 for y in S and choose the values in the range [0, v - 1] from it.
Say we have found a bitset of values y - k * v, where 0 \leq k \lt 2^r and say this bitset is S_r. Initially, r = 0 and S_0 = S.
Then, we can find the bitset S_{r + 1} = S_r | (S_r >> (2^r * v)). [ We currently had shift as 0*v, 1*v, ... (2^r - 1) * v, and we can add 2^r * v to these to get the shifts 0*v, 1*v, ..., (2^(r+1)-1)*v]
Clearly, S_{log(N/v)} = T, because at r = log(N / v), we would have generated shifts for all possible valid k.
Let Z be the bitset of values 0 \leq p \lt v. Z can be maintained as we iterate on v in decreasing order in O(1) per v.
In the end we replace S by S | (T \& Z) , as we only need to consider values \lt v from the set T.
Time Complexity:
An easy way to explain the complexity is: A >> 2^r * v is done at max N / 2^r times. Summing over r, total number of shifts done \leq N.