Top 5 Optimizations, Tips, and Tricks LGMs Don't Want YOU To Know About !

Правка en3, от dutinmeow, 2021-08-30 01:04:45

Hello all!

If you're like me and want to become good at coding, but don't want to put in the effort, just follow this simple guide. Guaranteed LGM within 3 weeks or your money back!

### 1. Time Travel

Have you heard of using "vectorization" or "pragmas" to allow brute force solutions to pass (from for example, here)? There's no need to include this rather confusing block of code in your template: there's a much simpler and more effective method

#include <iostream>
#include <chrono>

int main()
{
using namespace std::chrono_literals;

}


Sleeping/stalling for a negative amount of time tricks the system into giving you extra time for your submission. Simply using this in front of all your code makes any solution pass (albeit, in a long time).

### 2. Better Hash

Current top-rated LGM Benq recommends using the following hash function combined with gp_hash_table to optimize unordered_map and avoid hacks and anti-hash bases.

struct chash {
const uint64_t C = ll(2e18*PI)+71;
const int RANDOM = rng();
ll operator()(ll x) const {
return __builtin_bswap64((x^RANDOM)*C);
}
};


However, a little trick that LGMs don't tell you is that there's an even faster hash function that works in O(1) for all inputs, including strings.

struct fhash {
ll operator() (ll x) const { return 7; }
};


This statement is intuitive to understand and code, and works extremely efficiently. To confirm this, I tested it against a set of identical strings of 10^5 characters; This hash function performed significantly better than the chash and the default one used by std::unordered_map.

### 3. Get Rid of Constant Factors!

Does your program have the correct complexity, but fail because of constant factors? Try this hack out! Everyone knows that the constant factor of a program is directly proportional to the number of semicolons in it. Thus, it follows that putting everything in one line will save you massively on unnecessary constant factors. Note that this also means using for loops is slow, because that takes two semicolons; replace this with a while loop instead.

For instance, the following code is an unoptimized way to multiply two numbers:

int multiply(int a, int b) {
int res = 0;
for (int i = 0; i < b; i++)
res += a;
return res;
}


However, this program can be substantially sped up using optimization tactics. Note that in general you should prioritize getting rid of semicolons, but removing lines and characters also improves run time because the compiler does not have to read over as many characters to check it. A general rule of thumb is that if your program is readable, it's not optimized enough.

int multiply(int a,int b){int res=0;while(true){res += a,b--;if(b==0)return res;}}


### 4. O(1) Optimization

Many people already use this trick for memory management; however, I haven't seen anybody use it for runtime yet. Take the following code to retrieve a number n.

int get(int n) {
int res = 0;
for (int i = 0; i < n; i++)
res++;
return res;
}



Anybody can tell you that this runs in O(n). But making a couple of changes will make this run in O(1). Assume that the problem contraints tell you that n <= 10^9.

int get(int a) {
int res = 0;
for (int i = 0; i <= 1000000000; i++) {
res++;
if (i >= a)
break;
}
return res;
}


Now it runs in O(1). You can apply this anywhere, even for quadratic, cubic, and exponential solutions. (for example, all-pairs shortest paths in O(1)).

### 5. Antihack Trick

None of the tricks mentioned above will work if you get hacked (although this is virtually impossible). A simple trick is to create an extremely long template with confusing aliases so that no one can possibly read your code and thus can't hack you! Example: Literally any one of Benq's submissions

Now, I hear you say, "But isn't this purposefully obfuscating code?". It's not, as long as its legitimately "part of your template". After all, who doesn't need to define custom istream/ostream operators for every stl data structure to save them a couple seconds when debugging? And obviously a template for taking the bitwise AND of two multisets is essential for any serious competitive programmer. And of course, make sure to define any common data structure with some random name no sane person could understand. This ensures that you, and only you, can read the code (as a side note, did you know c++ places no limit on variable name sizes?).

I hope you will use incorporate simple hacks and tricks in your coding skillset. I think most coders will benefit from this article, and I will be expecting to see more LGMs on the leaderboard soon!

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en3 dutinmeow 2021-08-30 01:04:45 0 (published)
en2 dutinmeow 2021-07-27 02:59:28 1 (saved to drafts)
en1 dutinmeow 2021-04-27 06:17:18 5118 Initial revision (published)