Blog entries - Codeforces

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

#	User	Contrib.
1	cry	168
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	159
5	atcoder_official	156
6	djm03178	153
6	adamant	153
8	luogu_official	149
9	awoo	148
10	TheScrasse	146

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;
}

Full text and comments »

rezidentura's blog