How to avoid SEGMENTATION ERROR for the code below?

Question

I'm getting Segmentation error for the code below. This is a solution to the SPOJ problem "Coins".

I went through How to avoid SIGSEGV? and I made sure not to use uninitialized pointers, not to access out of memory etc (given n &leq; 10⁹).

I know that an array a[1000000000] would lead to stack overflow, so I used std::map. Will a std::map ever lead to a stack overflow? What is wrong with my code?

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>

using namespace std;

map<unsigned long long int, unsigned long long int> a;

unsigned long long int dp(unsigned long long int n)
{   
   if (a.find(n) == a.end())
      a[n] = dp(n/2) + dp(n/3) + dp(n/4);

   return a[n];
}

int main()
{
    for (unsigned long long int i = 1; i <= 24; i++) {
        a[i] = i;
        if (i == 12 || i == 24)
           a[i] = i + 1;
    }

    unsigned long long int n = 0;
    cin >> n;

    while (!feof(stdin)) {
        printf("%llu\n", dp(n));
        cin >> n;
    }
}

@Michelle sure it is. Look at the for loop at the beginning of `main()` — NathanOliver, Jun 02 '15 at 17:59
If you are going to have 10^9 long long's then that is going to take up more than 7GB of memory. How much memory do you have? — NathanOliver, Jun 02 '15 at 18:01
[`while(!feof(stdin))`](http://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-considered-wrong). — πάντα ῥεῖ, Jun 02 '15 at 18:02
Why do you need to store values in a container? You can input one line, calculate the result, then read in the next line. — Thomas Matthews, Jun 02 '15 at 18:07
@ThomasMatthews: The result of one line depends on the result of a previous line. Read the definition of `dp`: it's recursive. — Lightness Races in Orbit, Jun 02 '15 at 18:08
Provide sample input, please. Ideally abstract away the `cin` calls entirely, taking data from a `stringstream` instead. Then this'll be a good question & I'll be able to just reproduce this and troubleshoot it within seconds. — Lightness Races in Orbit, Jun 02 '15 at 18:09
@LightnessRacesinOrbit: Thanks for formatting my question... — rsd_unleashed, Jun 02 '15 at 18:15
sample test cases Input: 12 1 24 10000 1000000000 Output: 13 1 25 16609 4186477065 — rsd_unleashed, Jun 02 '15 at 18:16
@rsd_unleashed: That output works fine, on at least one machine: http://coliru.stacked-crooked.com/a/dd7dea2ed4a35420 — Lightness Races in Orbit, Jun 02 '15 at 18:17
@LightnessRacesinOrbit : That's the main problem....Even Ideone accepted the code...However spoj compiler says SIGSEGV..... http://www.spoj.com/problems/COINS/ — rsd_unleashed, Jun 02 '15 at 18:20
@NathanOliver:Not actually,spoj compiler shows memory usage of 11M.However the limit is 1500M — rsd_unleashed, Jun 02 '15 at 18:25
_"Each testcase is a single line" "For each test case output a single line"_ You got the assignment wrong anyway :P — Lightness Races in Orbit, Jun 02 '15 at 18:35
Three things: If you use a global array there will be no problems with stack overflow. The maximum result, 4186477065, fits in 32 bits. You don't need to store all the results. — molbdnilo, Jun 02 '15 at 19:27

iskhakovt · Accepted Answer · 2015-06-02T23:24:43.053

1

You get SIGSEGV on dp(0) call. It causes an infinite recursion.

By the way, your solution is wrong, for example the answer for 24 is not 25. Try to avoid magic constants, it is just enough to set a[0] = 0 and make a more accurate dp function:

uint32_t dp(uint32_t n) {
    if (a.find(n) == a.end())
        a[n] = max(n, dp(n / 2) + dp(n / 3) + dp(n / 4));

    return a[n];
}

As can be seen above, 32-bit type is enough to store any possible answer.

edited Jun 02 '15 at 23:24

answered Jun 02 '15 at 23:13

iskhakovt

458
4
13

Thanks a ton.....AC..... Want to upvote your ans....But new to stackoverflow...Don't have enough reputation :) – rsd_unleashed Jun 03 '15 at 09:17

How to avoid SEGMENTATION ERROR for the code below?

1 Answers1