Someone wants to snipe him

Me too.

You guys test interactive problems, eh ? Just submit, prove by AC

Give them a try, interactive problems are fun to solve!

naahh, just had adrenaline rush

well, I used normal dp

dp[x] = min(dp[y] for each y such that y = x / z and z <= k) + 1

you have two things wrong in your code:

• you check only the maximum divisor of only number $$$x$$$ or $$$y$$$, while you have to check both of them, you can fix it by changing these two lines:

            mxm = (pfx.size()>0)?pfx[pfx.size()-1]:mxm ;
            mxm = (pfy.size()>0)?pfy[pfy.size()-1]:mxm ;

into these two lines:

            mxm = max(mxm, (pfx.size()>0)?pfx[pfx.size()-1]:mxm) ;
            mxm = max(mxm, (pfy.size()>0)?pfy[pfy.size()-1]:mxm) ;

• you can't use greedy to find the minimum number of operations, you must use $$$dp$$$ for this

can you explain your dp solution..thnkx

My 321514527 without Sieve of Eratosthenes is currently passing, feel free to hack. (Someone already tried) :)

can we do it with graphs?model nodes as numbers from 1 to max(x,y),and edges if transition is possible.I guess they will be of order zlogz where z=max(x,y) and then run dijkstra?

Can we calculate f greedily instead of dp ? I mean for f(x) does dividing x to its biggest divisor (that is lower than or equal to k) always yield the optimal answer ?

can you please break down how you calculated that N^2/3 time complexity?

Ah okay, got it bruh. The other cases never crossed my mind.

Btw the reason why this problem has an easier solution is because there is a small number of distinct states. For example, consider the bin-packing variation where we take the sum of elements (instead of product). You can encode the state of the problem as a frequency table of the numbers we have (using a hash map, for example). Then the number of distinct states are $$$\prod_i freq_i + 1$$$. As all numbers may be distinct we have up to $$$2 ^ n$$$ states. In the multiplication case we have exact same scenario, but as the product of everyone $$$\leq 10^8$$$ it follows that we can't have a very large value of $$$\prod_i freq_i + 1$$$. In fact, for this particular problem, the elements you want to separate in bins are the prime factors of some number $$$n \leq 10^8$$$, so it follows that the number of distinct states is exactly equal to the number of divisors of $$$n$$$, which is $$$\leq n$$$.

how is it NP hard? i think the time complexity of the dp solution with the states and transition you mentioned is nlogn

thats second time, this is happening with you lol. :P

my solution is kinda different first i do what everybody does ->>>

Say gcd(x, y) = g, Then the problem reduces to finding the same answer for (x/g, y/g), say x1, y1

Additionally, since x1 and y1 are co-prime, we just need to find a way to remove all of x1 by division and multiply all of y1 by multiplication.

So if we define a function, f(x) => minimum moves to make x from 1 through repeated multiplication by a number <=k, we just need to find f(x1) + f(y1)

now calculation of f(x) is different for me ->>>>

first thing to note is that, we can do something greedy here, we can always choose such subsets of prime factors of x which when multiplied is <=k basically over all subsets, choose that subset which gives maximum product less than k. subtract that subset from total prime factors and repeat this process till factors are empty. this process will run atmost 20 times.

but choosing a subset is 2^20, so this will be slow as sum of x can be up to 10^8

but if we choose subsets recursively we can return early and not all 2^20 subsets will be checked,

basically if k is large i.e., big subsets are created then we will repeat the process way less than 20 times and if k is small then we will return early not all 2^20 operations will be done. i don't have proof for this though. it might so happen someone create a test which would TLE idk.

gave the solution above ^^