rezidentura's blog

Need help with a dfs simple problem !!
By rezidentura, history, 19 months ago, In English

This is the problem I want to discuss : 1661B - Получение нуля

I have this answer, It's not mine but I made it cleaner (I think).

The answer

I have two questions and thank you in advance.

1) Why deleting this line : return ans[x]; gives wrong answer.

2) why changing the code into the 2 code below gives wrong answer :

2 code
  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Difficulty of the problem is :

Spoiler
→ Reply
»
19 months ago, # |
  Vote: I like it +1 Vote: I do not like it

demoralizer can you please help with this question, because the answer is yours. Sorry for the pinging.

→ Reply
»
19 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

  1. You are using ans[x] as result for recursive calls. How do you expect this to work fine? Besides, non-void functions without return always results in UB (the only known exception to me is main-function);

  2. Again, dfs function changes ans array, so calling dfs change observable state of program (variable ans). And you pass dfs-call twice in function call. That is classic unspecified behaviour (not UB yet), there is no guarantee, what dfs call to be first.
    Imagine, if last argument invokes before first, then what calls do you have?
    dfs(1) -> dfs(2) -> dfs(3) -> ... -> dfs(32766) -> dfs(32767) -> ?
    At that point ans not changed (ans[0] = 0, ans[1] = ans[2] = ... = ans[32767] = -1). Than dfs((x + 1) % M) would be called (dfs(0)), it returns 0. Then in dfs(32767) call would be happen dfs(32767 * 2 % 32768) = dfs(32766).
    And what next? You'll get infinite cycle dfs(32766) -> dfs(32767) -> dfs(0) -> dfs(32766) -> ... (ans not changed at any point). So you there must get TL (in case if compiler thinks that second argument must be called before first).

P.S. Notice that if you call determinedly dfs(x + 1) before dfs(2 * x), than it always would be TL. Dfs there is not appropriate algorithm, fact that it works in that just due to operations nature. Bfs there is preferable, because bfs would not try to go to vertex that beign explored. Dfs would.

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much.

    For question 1 I meant that isn't if(ans[x] != -1) return ans[x]; enough, or it's necessary to add return ans[x];

    I mean always at some point (ans[x] != -1) will be true? or I'm missing something!

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

      Consider root dfs call. if (ans[x] != -1) returns false, so you do ans[x] = 1 + dfs(2 * x % M) and ans[x] = min(ans[x], 1 + dfs((x + 1) % M)). What value would be return by root dfs call?

      Answer: it is UB, because no one return-statement ever done. So it returns some random.

      → Reply