Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

369Hz's blog

got MLE but can't still configure what's wrong with this program!
By 369Hz, history, 3 years ago, In English

Problem link: 1661B - Получение нуля 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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +9 Vote: I do not like it 
      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?

      1. x = 19, produces two inner calls (dfs(38) and dfs(20))
      2. Assume, that first call would be first (it is not standardized btw)
      3. dfs(38) produces another two inner calls (dfs(76) and dfs(39))
      4. And so on... dfs(76) produces dfs(152) and dfs(77)
      5. ...
      6. And now you on x = 16384. This will produce dfs(0) and dfs(16385)
      7. dfs(0) indeed returns 0, but dfs(16385)? Moving on
      8. dfs(16385) produces dfs(2) and dfs(16386)
      9. dfs(2) produces dfs(4) and dfs(3)
      10. ....
      11. And you at some point will come to x = 16384
      12. Repeat infinitely steps 6-11.

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

      → Reply
      • »
        »
        »
        »
        3 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          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.

          → Reply