collatz

Algoritmul, pas cu pas

Drumul e determinist. Pentru un element, operația e impusă de paritate: par $\to x/2$, impar $\to 2x+2$. Deci de la $x$ există un singur drum către $1$, iar numărul minim de pași e fix lungimea lui — notată $f(x)$. Răspunsul pe un vector $[S, D]$ e $\sum_{x=S}^{D} f(x)$.

Recurența lui $f$. $f(1) = 0,\quad f(x) = 1 + f(x/2)\ (x\text{ par}),\quad f(x) = 2 + f(x+1) = 3 + f\!\left(\tfrac{x+1}{2}\right)\ (x\text{ impar} > 1)$ (un impar devine par cu o operație, apoi se înjumătățește cu a doua).

Suma pe interval. Un vector are până la $10^{16}$ elemente, deci nu pot calcula $f$ pentru fiecare. Folosesc funcția de prefix $P(n) = f(1) + \dots + f(n)$ și răspund cu $P(D) - P(S-1)$.

Sparg $P(n)$ pe pari și impari:

• termenii pari $x \le n$: $\sum (1 + f(x/2)) = \lfloor n/2 \rfloor + P(\lfloor n/2 \rfloor)$;
• termenii impari $x \le n$ (cu $x \ge 3$): cu $x = 2t+1$, $\sum (3 + f(t+1)) = 3T + P(T+1)$, unde $T = \lfloor (n-1)/2 \rfloor$.

Deci: $P(n) = \left\lfloor \tfrac{n}{2} \right\rfloor + P\!\left(\left\lfloor \tfrac{n}{2} \right\rfloor\right) + 3T + P(T+1),\quad P(0) = P(1) = 0$

Ambele apeluri folosesc argumente $\approx n/2$, deci cu memoizare (un map) numărul de valori distincte e mic. Complexitate: $O(\log^2)$ per întrebare.

Soluția în C++

#include <fstream>
#include <map>
using namespace std;

ifstream fin("collatz.in");
ofstream fout("collatz.out");

map<long long, long long> memo;

// P(n) = f(1) + f(2) + ... + f(n)
long long P(long long n) {
    if (n <= 1) return 0; // P(0) = P(1) = 0
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    long long h = n / 2;          // numărul de termeni pari <= n
    long long T = (n - 1) / 2;    // numărul de termeni impari >= 3 (plus 1)
    long long res = h + P(h) + 3 * T + P(T + 1);
    memo[n] = res;
    return res;
}

int main() {
    int T;
    fin >> T;
    while (T--) {
        long long S, D;
        fin >> S >> D;
        fout << P(D) - P(S - 1) << "\n"; // suma f(x) pe [S, D]
    }
    return 0;
}