PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Problem Idea: S.Manuj Nanthan
Prepared by: Aryan
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Medium
PREREQUISITES:
PROBLEM:
An array of integers is called good if all its elements are perfect squares.
You are given an array A of N integers. In one move, you can do the following:
- Pick a subset of indices of the array, say \{i_1, i_2, \ldots, i_k\} where 1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq N
- Next, pick an integer X \gt 0
- Finally, multiply the value at each chosen index by X, i.e, set A_{i_j} to A_{i_j} \cdot X for each 1 \leq j \leq k
Find the minimum number of moves required to make the array good.
Note: The value of X is fixed for a given move, but can vary between moves.
EXPLANATION:
A number K can be factorized to be written as K = p_1^{c_1} \cdot p_2^{c_2} \ldots p_r^{c_r}. To make K a perfect square, we need to make each exponent of the primes even. So, if c_i is even, we do not need to multiply K by p_i, however if c_i is odd, we need to multiple K by p_i. Additionally, we can multiply K be even powers of any prime. This means that we can represent the number K by using a vector of length r, where the i^{th} bit is 1 if p_i is needed to be multiplied, otherwise we i^{th} bit is 0.
Let C = max(A_i) over all i.
Using the above method, we can represent all the numbers A_i by using a vector of length K = \frac{C}{\log{C}}, as there are these many primes less than C. To factorize numbers, we can precompute all the primes less than \sqrt{C}, and then use this list to speed-up our process. We have N such vectors. We want to make each vector in some moves. In one move, we choose a vector v of length K, and some indices \{i_1, i_2, \ldots, i_k\} where 1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq N, and take XOR of the respective vectors with the chosen vector v. Our aim is to make all the elements of N vectors 0 in minimum possible number of moves.
The above problem can be solved using the Gaussian Elimination. However, the Time Complexity of the solution will be O(N \cdot K^2) which is very large.
How to solve the problem faster?
- We can observe that we are doing operations over vectors having 0s or 1s. Instead of vectors, we can use bitset to reduce the time complexity by a factor of 64. However, this is still not fast enough.
Note that for each A_i, there can be at most one set bit for primes greater than \sqrt{C}. Observe the Gaussian elimination on these primes. We choose a row in which this bit is set, and use this row to make this bit 0 in all the rows possible, and in the process, modifying the columns representing primes less than \sqrt{C}, by effectively taking XOR.
So, instead of maintaining all \frac{C}{\log{C}} primes, we can maintain bits for only \frac{\sqrt{C}}{\log{C}} primes, and maintaining the remaining prime (if present) individually. We first do the steps of Gaussian Elimination to eliminate those larger primes in the maintained bits for primes, and then using Gaussian Elimination on these bits for primes. This brings down the overall Time Complexity to O\bigg(\frac{N \cdot C}{\log^2{C} \cdot 64}\bigg).
TIME COMPLEXITY:
O\bigg(\frac{N \cdot C}{\log^2{C} \cdot 64}\bigg) for each test case.