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.

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 144 |

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.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 07:37:51 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I don't see how you dfs must ends, for me it is infinite recursion at first glance

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.

You have test input

Why don't we try it?

`x = 19`

, produces two inner calls (`dfs(38)`

and`dfs(20)`

)`dfs(38)`

produces another two inner calls (`dfs(76)`

and`dfs(39)`

)`dfs(76)`

produces`dfs(152)`

and`dfs(77)`

`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)`

`x = 16384`

See problem? If not, then your inner dfs calls never terminates.

That's too deep! Thanks. But how can I handle this case?

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.

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.

What's the logic in checking only values in the range [n, n + 15]?

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