Mars_Coder's blog

got MLE but can't still configure what's wrong with this program!
By Mars_Coder, history, 11 months 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

»
11 months ago, # |
  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
  • »
    »
    11 months ago, # ^ |
      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
    • »
      »
      »
      11 months ago, # ^ |
      ← 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
      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            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
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply