Using map<int, vector < int >> as a data structure for making several implementation easy

FFT.

Pie for a pie trick.

I like monotonic stack. The idea is pretty simple but you can do a lot of stuff with it

WQS Binary Search

Grundy Numbers with Infinity

My fav is LCA with binary lifting, least fav is probably sqrt decomposition

seg tree best

To be honest, the humble DFS: it's simple, but very flexible and you can do quite a lot of things with it: finding cycles, topological sorting, strong connectivity, finding bridges, tree DP (and a lot of tree calculations in general), Euler tours, some ad-hoc applications etc. etc.

Union find all the way

Vjudgian algorithm with black holes

Matrix Exponentiation

the simple binary search

Optimizing bitset memory usage from O(n^2) to O(n)

Linearity of expectation of a sum of dependent variables; in cp it's mostly used to turn the problem "find the expected number of objects" into the problem "sum the probability that an object appears for each object"

Disjoint Set Data structure.

My favourite technique, the Goemans Williamson MAX-CUT algorithm doesn't come from competitive programming, but from the field of approximation algorithms. It's one of the most elegant algorithms I've come across in computer science, so I'd recommend others to check it out too.

The most interesting and beautiful thing I know is Talia Al Ghul.

whenever I come across a question like "print a permutation which satisfies [some] conditions", I usually generate all of the possible permutations using std::next_permutation(c++) and print the permutations which satisfy the given conditions. I analyse all of the correct permutations and search for patterns.

DSU, seg tree, Fenwick, Dijkstra, DP and binary search maybe.

Binary Search. Simple but Gorgeous

Segment Tree and Hashing

Dynamic Programming.

Mo's algorithm.

I never thought Lexicographically Minimal String Rotation could be solved better than $$$O(n \log n)$$$ — using hashing, but when I tried to do some research and read papers, I then know much more:

/// SPyofgame's Subaru Trick: 21/04/2021 proved O(n)
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/// @brief Find minimal right-rotation operations to make the string minimal lexicographic
/// @param s the input string
int min_cyc(const string &s)
{
    /// Empty String
    if (s.empty()) return 0;

    char mx = *max_element(s.begin(), s.end());
    int n = s.size();

    /// Candidate list
    vector<int> a(n), c(2 * n), f(n);
    for (int i = 0; i < n; ++i) 
        a[i] = c[i] = c[i + n] = i;
    
    /// dth elimination
    for (int d = 1, k = 1; d <= n; d = k + 1)
    {
        /// Minimal character among substrings
        char mn = mx;
        for (int p : a) mn = min(mn, s[c[p + d - 1]]);
        
        /// Longest Duplicated Minimal |d|-length Substring
        vector<int> v;
        for (int p : a) if (mn == s[c[p + d - 1]])
        {
            /// This is not a minimal substring
            if (v.empty() || c[v.back() + f[v.back()]] != p) {
                v.push_back(p);
                f[v.back()] = 0;
            }
            
            /// Merging
            k = max(k, f[v.back()] += d);
        }

        /// Merge the last with the front if possible
        if (c[v.back() + f[v.back()]] == v.front())
            k = max(k, f[v.back()] += f[v.front()]);

        /// Next candidate list
        a.clear();
        for (int p : v) if (f[p] == k) a.push_back(p);

        /// Found the winner
        if (a.size() == 1) break;
    }

    /// Return the winner
    return a.front();
}

int main()
{
    /// Input
    string s;
    cin >> s;

    /// Output
    cout << min_cyc(s);
    return 0;
}

Other than that, I also discover a technique to find a dominant element on $$$[l, r]$$$ in $$$O(\log n)$$$ using a segment tree (yes, it also allow for updates)

(Don't know much but)calculating stuff such as square roots and cube roots using binary search.

Beautiful but not that useful: Turtle and hare It has the O(n) complexity, but uses constant memory

It's definitely parallel binary search, it's really simple yet appears in the hardest problems

I found dp beautiful

Yarin Sieve when the time/memory limit is strict. It is at least 3 times faster than the standard Sieve. Another one is the Fast Inverse Square root algorithm — the code doesn't make sense at first glance. It's still one of the most widely used algorithms in Game development.

I like treap. Treap is a very powerful structure that can do many crazy things.

Also like +-300 dp optimization

This one from Blogewoosh.

Mo‘s!

relatively easy to implement, can support nearly every type of query, can adapt onto trees, supports updates, sqrt(n) time which is ok..., offline...

Using Trie as a replacement for most data structures, like a hashmap with constant lookup time, finding Kth smallest element in Trie, Counting number of elements smaller than some number in Trie.

recursion/ induction/ dp. It's simple to write and it proves itself

Bitset, the niche observation that if $$$N$$$ integers sums up to $$$M$$$, then there must be no more than $$$\sqrt{2M}$$$ distinct value, dynamic segment tree (I swear to god these things always are the unintended solutions somehow, not complaining though since they saved my neck more than I could count).

Oh and there's BFS, DFS, binary search, DSU, stack and deque (daddy Um_nik would be happy)

And there's the magbum onuts square decomposition. God dayum they are just the most satisfying thing to pull off.

Lazy persistent segment tree. Once I implemented in one of the codechef long challenges from 2017's, and I got pretty descent rank and also earned money for being 2'nd in India. I learned the trick during 10 days contest and also implemented one of the most difficult problems in my life.

That was my first earning in my life in software career. :)

Thank you CodeChef_admin . Please bring back those long challenges, those were very good for learning experience for new comers :) .

thinking

Codeforces <3

1. REROOTING TECHNIQUE ON TREE.
2. HASHING.
3. DP.

Binary search

The fact that total number of distinct frequency of element in an array is at most sqrt(n).

vector arr = {1, 2, 3, 2, 1};

set st = set< int >(arr.begin(), arr.end()); // convert a vector into set

arr = vector< int >(st.begin(), st.end()); // convert a set into vector.

XOR Basis

Monotonic queue

string hashing

1. Priority queue
2. Monotonic stack
3. String hashing

PRACTICE

how is no one metion dp:)

I came up with it myself. If you want to take 3 integers as input and sort them. Just do this:

int a, b, c;
cin >> a >> b >> c;
sort(&a, &a+3);

Some compilers do catch these types of memory mishandling. But you can always find one that doesn't.

Stars and bars

Alien trick

suffix automaton

The one I really love is number 2 Here

dsu

segtree