How do I bypass a Segmentation fault?

[gabriel11]

Hey guys.

So I've been programming in C++ for a few months now, and I've been enjoying it all the way through. This is my first time using a programming language that is strict with memory, and I'm having a particular issue with the segmentation

Recently I've gotten into competitive programming as a fun little hobby to improve my overall problem solving skills, and I'm currently trying to do this problem: https://codeforces.com/problemset/problem/318/A

The question itself is pretty easy, and everything works until the last test that tries "1000000000000 500000000001"

Which in result, it outputs a segmentation fault. Is there something I'm doing wrong that I can improve on? Thanks!

Here is my program:

#include <iostream>

int main() {

    int n, k, pos=0;
    std::cin >> n;
    std::cin >> k;

    int *arr = new int[n];

    for(int i = 1; i <= n; i++) {
        if(i % 2 != 0) {
            arr[pos] = i;
            pos++;
        }
    }

    for(int i = 1; i < n; i++) {
        if(i % 2 == 0) {
            arr[pos] = i;
            pos++;
        }
    }

    std::cout << arr[k - 1] << std::endl;

    return 0;
}

[mbozzi]

Is there something I'm doing wrong that I can improve on?

The program doesn't account for the limited range of int.

The program also ignores the 256 megabyte memory limit: an array of 1000000000000 four-byte ints is four terabytes. You'll have to come up with an algorithm that doesn't allocate a linear amount of memory.

The "real problem" is that the program doesn't validate user input.
In the wild a program that didn't do that would be considered seriously defective, but this is a competition where security and robustness are deliberately thrown away for speed. YMMV.

[jonnin]

if its tuned for speed, why not i+=2 in the loops... and start them at 2 and 1 respectively? Then you can also remove the ifs -- you know each one will be true

[mbozzi]

I mean "speed of programming". As in, the amount of time it takes to type in the code. I think a lot of these competitions are timed.

[salem c]

> and I'm currently trying to do this problem:
...
> everything works until the last test that tries "1000000000000 500000000001"
A common feature of such programming contests is that the first simple idea that you come up with is likely the wrong one.

When you get "time limit exceeded" or "out of memory", it means you need to re-think your approach.

This is one such case.

Would you solve this problem on paper just by writing out all the numbers up to 10¹², or would you figure out the 1-line math expression that would just tell you the answer?

Work smarter, not harder is where they're tying to get you to go.