How can I fix problem with excessive memory?

Question

I'm trying to debug my code but I don't know what to do. I did a research about my error (SIGABRT) but still I don't know what to do. I added delete [] tab but it didn't fix the problem. Of course SIGABRT appears only on SPOJ. On compillator on pc everything works fine.

There is my problem: https://www.spoj.com/problems/MATNUM/

There is my code:

#include <iostream>
#include <string>

int main()
{
    int p0{}, p1{}, q{}, T{}, z{1};
    long long int n{}, summary{};
    std::cin >> T;
    for(int i = 1; i<=T; i++)
    {
        std::cin >> p0 >> p1 >> q >> n;
        long long int* tab = new long long int[n];
        tab[0] = p0;
        tab[1] = p1;
        for(int y = 2; y<=(n-1); y++) 
            tab[y] = ((4*tab[y-1]+tab[y-2])%q);
        for(int x = (n-1); x>=0; x--)
        {
            summary = summary + (tab[x]*z);
            z*=10;
        }
        if((summary%q)==0)
            std::cout << "YES\n";
        else
            std::cout << "NO\n";
        delete [] tab;
        summary = 0;
        z = 1;
    }
    return 0;
}

Answer 1

Come up with a better algorithm and start over

The problem description says that N (your n) may be as large as 10^18. So you have no hope of being able to allocate any array of size N, or anywhere close; as it stands you would need 8 petabytes of memory.

Also, you have no hope of being able to iterate any loop N times, or anywhere close; it will take years to run.

(And you certainly cannot store a number with 10^18 digits in a long long int, as you are trying to do.)

So brute force is no good here. The idea of the challenge must be to come up with an algorithm that is much less than O(N) and doesn't require you to actually compute all the digits of the number. I don't immediately see how one would do that (and I wouldn't tell you if I did), but I suspect that divisibility tests may be the key.

Answer 2

Your computation of tab has to be readjusted. You need a counter for how many digits you have generated. Then, you generate enough numbers in tab just to be greater than Q. Then, you divide. Take the remainder. Generate more digits till it is greater than Q. Rinse and repeat.

However, even if you do this you will run out of time. You see that Q is less than 10. So you need to implement divisibility test. For that you need to compute last few digits(not when Q is 7). That should do the trick.

Compute repeating sequence

You see that the variable p0, p1 can have values between 0-8 as Q<10. So there can be at most 81 combination as Q is fixed. After that the sequence will repeat. So the whole problem is about finding this sequence.

Following code can give you sequence.

#include <iostream>

using namespace std;

void compute_sequence(int p0, int p1, int q,  unsigned long long n) {
  int a[9][9];
  int b[81];
  int counter = 0;
  int p2;
  int quotient, remainder;
  
  b[0] = p0;
  b[1] = p1;

  // we set values to -1 so that we will know if it has been already computed
  // we will use this array to store the key value pair
  for(int i=0; i<9; i++) {
    for(int j=0; j<9; j++) {
        a[i][j] = -1;
    }
  }

  // we will use this array to store the sequence
  for(int i=0; i<81; i++) {
    b[i] = -1;
  }
  
  for(int i=2; i<n; i++) {
    p2 = (4*p1 + p0)%q;
    counter++;
    if(a[p0][p1] != -1) {
      a[p0][p1] = p2;
      b[i] = p2;
    } else {
      // we have found the repeating sequence
      quotient = (n - 2)/counter;
      remainder = (n - 2)%counter;
      break;
    }
  }
  
}

int main()
{
  int p0, p1, q, T, z{1}, tab[3];
  unsigned long long n;
  std::cin >> T;
  for(int i = 1; i<=T; i++)
  {
    std::cin >> p0 >> p1 >> q >> n;
    compute_sequence(p0, p1, q, n);
  }
}

Once you have this sequence you can find sum of digits and last few digits pretty fast. So I will leave the final solution to be found.

Note: I have not compiled or ran this code but that is the general idea.