Блог пользователя dthreatz

Getting "Compiled file is too large" error in Facebook Hackercup Round 1 problem
Автор dthreatz, 10 лет назад, По-английски

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;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится

      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;
}
      → Ответить