Amazing memory optimization trick that will make you LGM in seconds

Правка en1, от mircea_007, 2021-11-25 18:50:27

# Amazing memory optimization trick that will make you LGM in seconds

note: inspired by this

Do you not like it when you get memory limit exeeded? Yeah, i thought so. That is why today i am going to teach you some memory optimization tricks used by all LGMs today. Let's get started!

## 1. Make int's smaller

Did you know an int takes up 4 bytes (THATS 32 bits!!!!). And even worse a long long variable is 64bits!

To save ourselves from this waste of memory we will use a simple trick.

Let's say you know your variable, n has an upper bound, MAX. that means that n / MAX is allways <= 1. And what data type is allways <= 1? Tha'ts right: bool! And when you want to get the value of the variable just multiply back by MAX.

This means that we can compress a whole integer in just 1 bit!!

This will make our program use 32 (or even 64) times less memory.

note: it is not hard to exted this to negative numbers too

## 2. Taking it a step further

That's all great, but what if want to sore an array of size 1 000 000 000 000? No problem! We can treat the array as a very long number. An example is shown below

const int MAX_ELEM = 1000000000;// the maximum value of an element from the array

int n, temp;// n is not compressed for readability, but it is recomended to do so in a contest
bool array;

for( i = 0; i < n; i++ ){
temp = read();// get nummber from input
array /= MAX_ELEM;// make room for this element
array += (temp / MAX_ELEM); // add current element
}


note: we can also extend this to 2d arrays

And that's it!