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 | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 160 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 151 |
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.
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)
anddfs(20)
)dfs(38)
produces another two inner calls (dfs(76)
anddfs(39)
)dfs(76)
producesdfs(152)
anddfs(77)
x = 16384
. This will producedfs(0)
anddfs(16385)
dfs(0)
indeed returns 0, butdfs(16385)
? Moving ondfs(16385)
producesdfs(2)
anddfs(16386)
dfs(2)
producesdfs(4)
anddfs(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.