### Mars_Coder's blog

By Mars_Coder, history, 4 months ago,

Problem link: 1661B - Getting Zero submission: 208009051 I tried to solve this problem using the dfs algorithm. But I can't still configure what is causing the MLE verdict. Help if someone can.

• -5

 » 4 months ago, # |   0 I don't see how you dfs must ends, for me it is infinite recursion at first glance
•  » » 4 months ago, # ^ |   0 At a particular position, any number will be divisible by 32768(2^15) and have a value equal to zero. As the value is not equal to -1, that will end the recursive call.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   +9 int dfs(int x){ if(ans[x] != -1) return ans[x]; return ans[x] = min(1 + dfs((2 * x) % md), 1 + dfs((1 + x) % md)); } You have test input 4 19 32764 10240 49 Why don't we try it? x = 19, produces two inner calls (dfs(38) and dfs(20)) Assume, that first call would be first (it is not standardized btw) dfs(38) produces another two inner calls (dfs(76) and dfs(39)) And so on... dfs(76) produces dfs(152) and dfs(77) ... And now you on x = 16384. This will produce dfs(0) and dfs(16385) dfs(0) indeed returns 0, but dfs(16385)? Moving on dfs(16385) produces dfs(2) and dfs(16386) dfs(2) produces dfs(4) and dfs(3) .... And you at some point will come to x = 16384 Repeat infinitely steps 6-11. See problem? If not, then your inner dfs calls never terminates.
•  » » » » 4 months ago, # ^ |   0 That's too deep! Thanks. But how can I handle this case?
•  » » » » » 4 months ago, # ^ |   0 I don't think that dfs approach works here (at least I don't know any proof for it). I'd do just simple bfs from zero to all values by reversed operations.
 » 4 months ago, # |   0 See as per me the max ans can be till 15 only as if you multiply any number by 2, 15 times it will definitely be a multiple of a given number. Now the thing which remains is adding 1. Always the adding part is to be done before starting to multiply the number by 2. I am not sure about the proof. Let's say you multiply y with 2 and add 1, 2 times to reach another number x. This takes us 3 steps, but if you add 1 to y and then multiply with 2, then it will take 2 steps. So it is always optimal to first add and then multiply. So check for all number from [n,n+15] by multiplying with 2 and taking the minimum cost. 189273995 You can check my submission.
•  » » 4 months ago, # ^ |   0 What's the logic in checking only values in the range [n, n + 15]?
•  » » » 4 months ago, # ^ |   0 as the answer will always be less than or equal to 15 so adding 1, 16 times (i.e n+16) will never lead to the optimal solution. Here n refers to the number for which we are trying to find the number of operations i.e. element of the array