Need help with a dfs simple problem !!

#	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	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

This is the problem I want to discuss : 1661B - Getting Zero

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

The answer

#include <bits/stdc++.h>
using namespace std;

int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M = 32768;
    vector<int> ans(M, -1);
    ans[0] = 0;

    function<int(int)> dfs = [&](int x) {
        if(ans[x] != -1) return ans[x];
        ans[x] = 1 + dfs(2 * x % M);
        ans[x] = min(ans[x], 1 + dfs((x + 1) % M));
        return ans[x];
    };
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dfs(n) << "\n";
    }
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int M = 32768;
    vector<int> ans(M, -1);
    ans[0] = 0;

    function<int(int)> dfs = [&](int x) {
        if(ans[x] != -1) return ans[x];

        ans[x] = min(1 + dfs(2 * x % M), 1 + dfs((x + 1) % M));
        
        return ans[x];
    };
 
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        cout << dfs(n) << "\n";
    }
    return 0;
}

Comments (5)

Show archived | Write comment?

rezidentura

2 years ago, # |

Difficulty of the problem is :

Spoiler

→ Reply

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

balalaika

← Rev. 2 →

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);
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.

2 years ago, # ^ |

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!

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.

rezidentura's blog