got MLE but can't still configure what's wrong with this program!

Блог пользователя Mars_Coder

Автор Mars_Coder, история, 11 месяцев назад, По-английски

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.

mle, dfs and similar

-5

Mars_Coder
11 месяцев назад
8

Комментарии (8)

Написать комментарий?

balalaika

11 месяцев назад, # |

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

→ Ответить

Mars_Coder

11 месяцев назад, # ^ |

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.

→ Ответить

balalaika

11 месяцев назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Mars_Coder

11 месяцев назад, # ^ |

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

→ Ответить

balalaika

11 месяцев назад, # ^ |

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.

→ Ответить

Leone_kyoya

11 месяцев назад, # |

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.

→ Ответить

Mars_Coder

11 месяцев назад, # ^ |

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

→ Ответить

Leone_kyoya

11 месяцев назад, # ^ |

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

→ Ответить