mircea_007's blog

By mircea_007, history, 23 months ago, In English

The case for brainfuck

Brainfuck is a widely known programming language but it lacks recognition from the competitive programming comunity. I am here to fix that.

Advantages

Brainfuck has many advantages over c++:

  1. Builtin fast i/o.
  2. Builtin O(1) time complexity (there is a finite number of states so you can either end up in a cycle or finish execution).
  3. Builtin O(1) space complexity (memory is limited to 30 000 bytes).
  4. Only 8 commands (no room for human error).
  5. You now have the power to understand any Benq source (really)
  6. Immune to hacks (except from 3000+ rated users who learn brainfuck before they can walk).

How to use

You might notice that there is no brainfuck option when choosing a language for your source code. This is no problem! You can use this C++ interpreter for brainfuck. This resource also contais a few classic examples (dfs, bfs, djikstra, Roy-Floyd etc.).

Conclusion

I thank you all for reading. Upvote for more quality content.

Full text and comments »

  • Vote: I like it
  • +146
  • Vote: I do not like it

By mircea_007, history, 2 years 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.

Full text and comments »

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