dthreatz's blog

By dthreatz, 10 years ago, In English

I'm getting a "Can't compile file: Compiled file is too large [40555520 bytes], but maximal allowed size is 33554432 bytes [CompileRequest {id='program.cpp', description='', file='program.cpp', resources='', type='cpp.g++11'}]." error when submitting my solution for Facebook Hacker Cup Round 1 problem A. However, the memory limit for this problem in the Gym section is 1024 MB. So, what's happening here?

Not doing anything crazy in my code either:

#include <iostream>
#define N 10000000
using namespace std;

int arr[N + 1] = {1};
void sieve()
{
    for(long i = 2; i <= N; i++){
        if(arr[i] > 0)
            continue;
        arr[i]++;
        for(long j = 2; i*j <= N; j++){
            arr[i*j]++;
        }
    }
}

int main()
{
    int t;
    cin >> t;
    sieve();
    long a, b, k;
    for(int tt = 1; tt <= t; tt++){
        long long ans = 0;
        cin >> a >> b >> k;
        for(long i = a; i <= b; i++){
            if(arr[i] == k)
                ans++;
        }
        cout << "Case #" << tt << ": " << ans << endl;
    }
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C++ compiler allocates memory for static arrays in the image.

So int arr[N + 1] = {1}; increases your *.exe size by 10000000x4 bytes, which is too large. Using vector will solve your problem since it allocates memory in runtime from a heap. Something like this:

vector<int> arr; // it can be a global variable (no memory allocation so far)
void sieve()
{
    arr.resize(N+1); // allocate memory from heap
...
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That does work, but I still think something is not working well with the judge since I'm guessing the memory limit refers to both static and dynamic memory.

    If you look at previous accepted solutions for the same problem in the Gym section, you'll see people allocating even more memory in global arrays, so it seems that the judge's constraints for those problems were changed at some point recently.

    • »
      »
      »
      10 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      It would be nice if you pointed to one of such solutions. Do they use 4-byte or 1-byte ints?

      UPD I'm not a CF admin and I don't know for sure but I can imagine that there are different limits for binary size and dynamic memory.

      • »
        »
        »
        »
        10 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Take for instance this accepted solution

        In case you can't see the code, here's what he's doing:

        const int max_n = 10000010;
        
        long long int count[max_n];
        bool is_prime[max_n];
        

        He's even using 8-byte integers plus another 10 million bytes of just booleans.

        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          By some reason, I'm "not allowed to view the requested page". Are they global arrays or declared within a function?

    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      For int arr[N + 1] = {1}; compiler will generate an initialized array, write it to the output binary (i.e. a.out or whatever.exe). This led to a 40MB a.out.

      Working solution:

      int arr[N+1];
      int main() {
       arr[0] = 1;
      }