Memory Limit Exceeded when input numbers are big

Question

I wrote a program for problem 318A on CodeForces. It seems to work fine for small numbers as input (when n = 7 and k = 1, or when n = 8 and k = 4, etc..). However, if n and k are large numbers (for example, n = 1000000000000 and k = 500000000001), then I get a MEMORY_LIMIT_EXCEEDED error.

I'm not sure how to fix this. I tried to turn the variables from int to long long int, but that didn't work. I think the problem is that the loop can't cope with large numbers.

This was my submission:

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int>v,v2;
    int n,k;

    cin >> n >> k;

    for (int i=1; i<=n;i+=2){
        v.push_back(i);
        v2.push_back(i+1);
    }

    v.insert(v.end(),v2.begin(),v2.end());


    cout << v[k-1];
}

This is a mathematics "trick" question. There is no need to store anything in vectors. — PaulMcKenzie, Jul 16 '20 at 22:46
Please read: [Why should I not #include ?](https://stackoverflow.com/q/31816095/2752075) and [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/2752075). — HolyBlackCat, Jul 16 '20 at 22:49
Think about how much memory you would need for `1000000000000` — drescherjm, Jul 16 '20 at 22:49
*which seems to work fine for small numbers as input* -- Questions on websites like the one you linked to are designed so that naive solutions only work for small numbers, and will fail for larger input. It's your job to research on finding another method, algorithm, data structure, etc. — PaulMcKenzie, Jul 16 '20 at 22:51

score 0 · Accepted Answer · edited Jul 16 '20 at 23:23

This is a problem that can be easier if you attack it from a mathematician's point of view. For a number n take a note at this:

If you try with some cases you will come to realize there is a pattern.

If n is in the form 2m+1 then there will be (n+1)/2 non-even numbers that will start the sequence. Then there will be n - (n+1)/2 even numbers. If k is in [1, (n+1)/2] then calculate 2(k-1) + 1. Else if k is in [(n+1)/2 + 1, n] then calculate 2(k - (n+1)/2).

If n is in the form 2m then there will be n/2 non-even numbers that will start the sequence. You can construct form here.

Here is my code:

#include<iostream>

int main(void){
  long long int n, k;
  std::cin>>n>>k;

  long long int p;
  if (n % 2 == 0) {
    p = n/2;
  } else {
    p = (n+1)/2;
  }

  if (k <= p) {
    std::cout << 2*(k-1) + 1; 
  } else {
    std::cout << 2*(k-p);
  }
}

Memory Limit Exceeded when input numbers are big

1 Answers1