Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### alwerty's blog

By alwerty, history, 4 weeks ago, ,

I tried all day to solve this problem:

Bring an integer N to 1 doing one of these operations each step: N /= 3; N /= 2; N -= 1;

1 <= N <= 1e9

output = minimum number of steps.

This is the function I wrote:

int solve(int n) {
if (n == 1) return 0;
if (n == 2) return 1;
if (n % 3 == 0) {
if (n % 2 == 0) return solve(n / 3) + 1;
else return  min(solve(n / 3), solve((n - 1) / 2) + 1) + 1;
}
if (n % 2 == 0) {
if ((n - 1) % 3 == 0) return min(solve((n - 1) / 3) + 1, solve(n / 2)) + 1;
else return min(solve((n - 2) / 3) + 2, solve(n / 2)) + 1;
}
if ((n - 1) % 3 == 0) return min(solve((n - 1) / 3), solve((n - 1) / 2)) + 2;
return min(solve((n - 2) / 3) + 1, solve((n - 1) / 2)) + 2 ;
}



I think the complexity of my solution is linear and the answer it gives should be correct but I'm not sure.

Can you help me find the best solution?

•
• +3
•

 » 4 weeks ago, # |   +19 Let's find answer for all n <= 10 ^ 7 = M, it can be done with simple dp. Then how to solve it for n > M? As we know ans[n] = min(ans[n / 2], ans[n / 3], ans[n — 1]) Well, let's run recursion, if n <= M: return dp[n]; else: we use our formulaBut is still does not work fast, because we will find answer for n, n — 1, n — 2, ... M + 1. Notice that there is no point in decreasing n by 1 3 or more times because instead n -> n — 1 -> n — 2 -> (n — 2) / 2 we do n -> n / 2 -> n / 2 — 1, case when we divide n by 3 after several decreasing by 1 is the similarNow let's run our recursion again, but in recursion we will check that we don't substract 1 3 or more times. And this solution should works fast
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yes this is a lot faster than without dp, can you explain briefly the dp algorithm done in linear time?EDIT: Nvm I think I got it, it is really simple indeed
 » 4 weeks ago, # | ← Rev. 3 →   +8 If we let R(N) be the answer for N, then: The time complexity recurrence is \$ and this should be fast enough even without memoization. We can analyze it with the Akra-Bazzi method to find that the actual complexity is O(N0.79).
•  » » 4 weeks ago, # ^ |   0 This is exactly what I did, but I realized it after I coded that mess.