Amazing memory optimization trick that will make you LGM in seconds

Revision en1, by 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;

n = read();// read n using your favorite method
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!

Please give your feedback in the comment section.


  Rev. Lang. By When Δ Comment
en1 English mircea_007 2021-11-25 18:50:27 1890 Initial revision (published)