mircea_007's blog

By mircea_007, history, 6 days 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.

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

»
6 days ago, # |
  Vote: I like it +74 Vote: I do not like it

The only thing that can make you LGM in seconds is new year Magic which is just month away.

»
5 days ago, # |
  Vote: I like it +17 Vote: I do not like it

that will make you LGM in seconds

So basically you are guiding others to treasure you cannot possess ? :p

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If I hadn't read the title, I would have upvoted =))

»
5 days ago, # |
  Vote: I like it -10 Vote: I do not like it

WTF, my second account got LGM just after 1 second of reading this post!