Hello codeforces. I am trying to upsolve the problems of qualification day2 of ECPC and i need some help on this problem.
The solution that i implemented was a dp solution where dp[i] is the answer for i. so before run any testcase i calculate the dp from 1 to 1e6, and to do this i cal min(dp[i-1]+1, dp[i/j]+j) where j is every divisor of i.
I tried different codes to make this fast and the fasted code that came in my mind was by generate all the prime divisors of i and then calculate the all the divisors of each i from its prime divisors.
But even this code take around more than 3 seconds on my machine. Can anyone please help me with this problem? I want to know if my idea was right and if so will this solution pass in the contest? unfortunately they don't write the time for each test case
Your idea is good, and DP formula is correct. For simplicity, let $$$N = 1e6$$$, then your algo complexity is somewhere $$$N + N/2 + N/3 + ... + N/N = O(NlogN)$$$, which is pretty good.
The problem is that you also used that much
push_backoperations, which is kind of expensive (even if you only work on primes). You can run the same DP without using any push backs whatsoever like this:Should run way faster for the same time complexity. Note that I don't need to use only primes for divide operation, since they only yield worse answers, so the DP wouldn't catch that answer anyway.