PROBLEM LINK:
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
Given an array B of length N. Find an array A of length N such that the number of distinct elements A_i\mod B_i\ \forall i\in \{1,2,\dots,N\} is maximised.
EXPLANATION:
Observation: If A_i\ge B_i in the final array A, we can replace A_i with A_i\mod B_i without changing the score.
Therefore, we can only consider A_i\in \{0,1,\dots,B_i-1\} for all valid i. Then, the problem is reduced to finding an array A such that 0\le A_i<B_i and the number of distinct elements in A is maximised.
Intuition for the solution
Consider an example B=[1,7,2, 3, 2].
The set of possible values for each A_i is as follows:
- A_1=\{0\}
- A_2=\{0,1,2,3,4,5,6\}
- A_3=\{0,1\}
- A_4=\{0,1,2\}
- A_5=\{0,1\}
You want to select exactly one element from each set, such that the number of distinct elements is maximised. This can be remodelled equivalently as a simpler version of this classical problem (solution can be found here), which motivates the greedy solution!
We proceed greedily.
Generate the permutation array C of length N such that, B_{C_i}\le B_{C_{i+1}} for all valid i. This can be accomplished easily using a sorting algorithm.
Iterate over this array C; let the current index be i.
- If cnt < B_{C_i}, set A_{C_i} to cnt and increase cnt by 1.
- Else, we may set A_{C_i} to any valid value, since it doesn’t contribute to the total score. The value of cnt is not updated in this case.
It is trivial to deduce that, the number of distinct elements in A at the end is equal to the final value of cnt.
The proof of optimality is similar to the proof linked in the spoiler above, and is left to the reader as an exercise.
TIME COMPLEXITY:
Generating the array C takes O(N\log N) with sorting. Since we iterate once over C to compute the answer, the total time complexity is thus
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters