CF1497E2 Square-free division (hard version)

This is the hard version of the problem. The only difference is that in this version $ 0 \leq k \leq 20 $ . There is an array $ a_1, a_2, \ldots, a_n $ of $ n $ positive integers. You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square. Moreover, it is allowed to do at most $ k $ such operations before the division: choose a number in the array and change its value to any positive integer. What is the minimum number of continuous segments you should use if you will make changes optimally?

N/A

N/A

In the first test case it is possible to change the array this way: $ [\underline{3}, 6, 2, 4, \underline{5}] $ (changed elements are underlined). After that the array does not need to be divided, so the answer is $ 1 $ . In the second test case it is possible to change the array this way: $ [6, 2, \underline{3}, 8, 9, \underline{5}, 3, 6, \underline{10}, \underline{11}, 7] $ . After that such division is optimal: - $ [6, 2, 3] $ - $ [8, 9, 5, 3, 6, 10, 11, 7] $