### ChitreshApte's blog

By ChitreshApte, history, 11 days ago,

We start with 0 and we have to reach n

We can perform 3 operations:

1. Multiply the current number by 2 (cost p)

2. Multiply the current number by 3 (cost q)

3. Increase/Decrease the current number by 1 (cost r)

Find the min-cost to reach from 0 to n

Constraints:
10 testcases
1 <= n <= 10^18
1 <= p,q,r <= 10^9


Example:

n,p,q,r = 11,1,2,8

Order: +1, *3, *2, *2, -1 = 8 + 2 + 1 + 1 + 8 = 20

• +17

 » 11 days ago, # | ← Rev. 2 →   0 Maybe generate all natural x and y such that $2^x 3^y \leq n$. There exist only $O(log^2(n))$ such pairs. Get the minimum cost seeing the solution generated by each pair.UPD: Not always the optimal strategy. By seeing the editorial provided in the comments below, it seems we should start backwards and either decrease until zero or decrease until find a multiple of 2 or 3 of the form $k \ floor(\frac{n}{k})$ or $k \ ceil(\frac{n}{k})$. So the solution is always of the form $\sum c_i + \sum 2^{a_j} 3^{b_j}$.
•  » » 11 days ago, # ^ |   0 The first step makes sense. How to implement the second as we can have many possibilities.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 For each pair x, y you can write $n = 2^x 3^y + z$. The associated cost is $px + qy + rz$.
 » 11 days ago, # | ← Rev. 3 →   -9 I was mistaken I didn't see the contraints
 » 11 days ago, # |   -26 I guess you can simply use recursion. Just keeping check of the usage of +1/-1 will not give TLE. Something like this: def cost(curr): if curr == 0: return 0 if curr%2!=0 and curr%3!=0: return cost(curr - 1) + r ans1,ans2 = 10**18,10**18 if curr%2==0: ans1 = cost(curr//2) + p if curr%3==0: ans2 = cost(curr//3) + q return min(ans1,ans2) n = 10**18 p = 1 q = 2 r = 8 print(min(cost(n),cost(n+1)+r)) 
•  » » 11 days ago, # ^ | ← Rev. 4 →   0 Intput -2 100 100 1Correct output - 2Your output — 101I can think of one improvement in your code $cost(n/2)+min(p,(n/2)*r)$ similarly for 3 case.
•  » » » 11 days ago, # ^ |   -19 def cost(curr): if curr == 0: return 0 if curr%2!=0 and curr%3!=0: return cost(curr - 1) + r ans1,ans2 = 10**18,10**18 if curr%2==0: ans1 = min( cost(curr//2) + p , cost(curr//2) + r*curr//2 ) if curr%3==0: ans2 = min( cost(curr//3) + q , cost(curr//3) + 2*r*curr//3 ) return min(ans1,ans2) n = 102 p = 100 q = 100 r = 1 print(min(cost(n),cost(n+1)+r)) Yeah I think this will work. Didn't consider the case when r < p,q. Also I suppose memoization can help improve the efficiency.
•  » » » » 11 days ago, # ^ |   +8 Now your code reports 20 for this testcase: n = 61 p = 2 q = 1000000 r = 1 While a lower cost 15 is possible by running 61 to 0 via doing +1 +1 +1 /2 /2 /2 /2 -1 -1 -1 -1 operations.
•  » » » » » 11 days ago, # ^ |   +19 In fact it can be done with cost 14: $0 \to 1 \to 2 \to 3 \to 4 \to 8 \to 16 \to 32 \to 31 \to 62 \to 61$.
•  » » » » » » 11 days ago, # ^ |   0 You are right. But being pedantic, I didn't claim that 15 was the minimal possible cost. Just that the last rakeshpanda's solution wasn't good enough and I successfully "hacked" it.
•  » » » » » 11 days ago, # ^ |   -10 Yeah this solution is horribly wrong. Don't think we can use recursion to solve this problem.
•  » » 11 days ago, # ^ |   +21 Your code never uses the "decrease by 1" operation?
•  » » » 11 days ago, # ^ | ← Rev. 3 →   -10 Yeah you are correct. I didn't think of many test cases and also used a wrong assumption.
 » 11 days ago, # |   +9 This problem was asked in previous Atcoder round. i am sharing the link below Problem Link : Pay to WinEditorial : this
•  » » 11 days ago, # ^ |   0 Thanks a lot