YouKnowCipher's blog

Calculating Expected Divisions for Integer Reduction with High Precision
By YouKnowCipher, history, 2 hours ago, In English

Problem Statement: Given an integer $$$N > 1$$$, determine the expected number of divisions needed to reduce $$$N$$$ to 1 by repeatedly dividing it by one of its divisors (including $$$N$$$). Output the expected number of steps to reduce it to 1, accurate to at least 5 decimal places. Constraints: There will be $$$T$$$ test cases, where $$$1 < T < 10^4$$$ and $$$1 < N < 10^5$$$.

My Approach: Defining an array $$$\text{dp}$$$ such that $$$\text{dp}[N]$$$ represents the expected number of steps needed to reduce $$$N$$$ to 1. The base case is:

$$$ \text{dp}[1] = 0 $$$

For each integer $$$N > 1$$$, we calculate $$$\text{dp}[N]$$$ using this:

$$$ \text{dp}[N] = \frac{1}{k} \sum_{d \mid N, d > 1} \left( \text{dp}\left[\frac{N}{d}\right] + 1 \right) $$$

where $$$k$$$ is the number of divisors of $$$N$$$ (excluding 1). The term $$$\text{dp}\left[\frac{N}{d}\right] + 1$$$ accounts for the expected steps needed after dividing $$$N$$$ by its divisor $$$d$$$ and includes the division step itself. Then, we iterate through all integers from $$$2$$$ to the maximum $$$N$$$ required, precomputing the values of $$$\text{dp}[N]$$$. This ensures that each test case can be answered in constant time $$$O(1)$$$ by simply returning $$$\text{dp}[N]$$$.

But implementing this approach is not giving AC & I can't find any drawbacks. Can someone help to identify any issue or any new approach? Thanks in advance for you time and effort.

Tags math, dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
112 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use prime factorization

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

    Could you provide a bit more detail?

    → Reply
»
81 minute(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can I see your submission please?

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

    Yeah, sure. The main part:

    const int N = 100000;
vector<double> precompute() {
    vector<double> dp(N + 1, 0.0);
    for (int n = 2; n <= N; n++) {
        int cnt = 0;
        double sum = 0.0;
        for (int d = 2; d * d <= n; d++) {
            if (n % d == 0) {
                sum += dp[n / d] + 1;
                cnt++;
                if (d != n / d) {
                    sum += dp[d] + 1;
                    cnt++;
                }
            }
        }
        if (cnt == 0) {
            dp[n] = 1;
        } else {
            dp[n] = sum / cnt;
        }
    }
    return dp;
}
    → Reply