mircea_007's blog

By mircea_007, history, 2 months ago, In English

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.

Read more »

 
 
 
 
  • Vote: I like it
  • -26
  • Vote: I do not like it