SquareFreeSet
TCO 2018 Fun 2B · 2018-04-20 · by lg5293
Problem Statement
Andrew has an array of positive integers. You are given the array in the
Andrew calls an array of positive integers square-free if it has the following property: for each pair of distinct indices i, j the product x[i] * x[j] is not a perfect square.
For example, {4, 5, 6} is a square-free array because the numbers 4*5, 4*6, and 5*6 are not perfect squares. (Note that an individual element of the array, such as 4 in our example, may be a perfect square.)
The array {2, 47, 50} is not square-free because 2*50 = 100 is a perfect square.
The array {5, 7} is square-free but the array {5, 7, 7} is not square-free because 7*7 = 49 is a perfect square.
Andrew would like to change x into a square-free array. He can pay 1 to increase or decrease any single element of x by 1. He can modify the same element multiple times, the only restriction is that at the end all elements of x must still be positive integers.
Find and return the minimum total cost of changing x into a square-free array.
Notes
- An integer is called a perfect square if it can be written as k*k for some integer k.
Constraints
- x will have between 1 and 100 elements, inclusive.
- Each element of x will be between 1 and 10^6, inclusive.
{1,2,1,2}
Returns: 5
One optimal solution is to change this array into {3,2,1,5}. This costs 5, as we have to increment element 0 twice and element 3 three times. The array {3,2,1,5} is square-free. The six possible pairwise products are 3*2=6, 3*1=3, 3*5=15, 2*1=2, 2*5=10, and 1*5=5. The values 6, 3, 15, 2, 10, and 5 are not perfect squares.
{7,7,7}
Returns: 2
One optimal solution is to change this array into {6,7,8}.
{4,5,6,47}
Returns: 0
This is a square-free array, no changes necessary.
{1,10,1,1,1,1,10}
Returns: 13
{4,5,6,7,8,9,10,11,12,13,14,15,16,17,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 443
Submissions are judged against all 166 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SquareFreeSet with a public method int findCost(vector<int> x) · 166 test cases · 2 s / 256 MB per case