CODEWITHSUNDEEP
recursionsegmentation-fault
Siddharth Saurav
Siddharth Saurav

Reputation: 11

Segmentation fault for big input (recursive function)

`#include <bits/stdc++.h> using namespace std; #define ll long long

    ll solve(ll a, ll b, ll i){
        //base case
        if (a == 0) return i;
        if (b > a) return i+1;

        //recursive case
        if (b == 1) {
            return solve(a,b+1,i+1);
        }
        ll n = solve(a, b+1, i+1);
        ll m = solve(a/b, b, i+1);
        return min(n,m);
    }

int main(){
int t;  
cin >> t;
while(t--){
ll a, b;
cin >> a >> b;
cout << solve(a, b, 0)<< endl;

} }`

Basically question is from codeforces (1485A). The problem is that when I give some big input like 50000000 a and 5 for b, this gives me segmentation fault error while the code works fine for smaller inputs. Please help me solve it.

Upvotes: 0

Views: 85

Answers (1)

David Schwartz
David Schwartz

Reputation: 182763

Using recursion is a terrible choice. And you need to make all obvious algorithmic optimizations.

The key insight is that for any path that divides before increasing b, there is a path that is as good or better that does not divide before increasing b. Why divide by a smaller number when you can divide by a bigger one if you're going to use the steps to increase the number anyway?

With that insight, and removing recursion, the problem is trivial to solve:

#include <iostream>

unsigned long long divisions(unsigned long long a, unsigned long long b)
{
    // figure out how many divide operations we need
    int ops = 0;
    while (a > 0)
    {
        a/=b;
        ops++;
    }
    return ops;
}

unsigned long long ops(unsigned long long a, unsigned long long b)
{
    // figure out how many divides we need with the smallest possible b
    unsigned long long min_ops = (b == 1) ? (1 + divisions(a, b+1)) : divisions(a, b);

    // try every sensible larger b to see if it takes fewer operations
    for (unsigned long long num_inc = 1; num_inc <= min_ops; ++num_inc)
    {
        unsigned long long ops = num_inc + divisions (a, b + num_inc);
        if (ops < min_ops)
            min_ops = ops;
    }
    return min_ops;
}

int main(void)
{
    int t;
    std::cin >> t;
    while (t--)
    {
       unsigned long long a, b;
       std::cin >> a >> b;
       std::cout << ops(a, b) << std::endl;
    }
}

Again, the lesson is that you must make algorithmic optimizations before you start coding. No amount of great coding will make a terrible algorithm work well.

By the way, there was a huge hint on the problem page. Something in the problem tags gives the key optimization away.

Upvotes: 0

Related Questions