# Debugging
`gen.py:`

from random import randint as rand
n=10
maxv=10
print(n)
print(*(rand(0, maxv) for i in range(n)))

g++ slow.cpp -o slow
g++ fast.cpp -o fast
while true; do
    python3 gen.py > in.txt
    ./slow < in.txt > slow.txt
    ./fast < in.txt > fast.txt
    diff fast.txt slow.txt || exit
done

For interactive problems, write your own runner.

# Contest strategy
### Go to the toilet often

### Sleep well

### Bring candy

### Prove lemmas by submitting (asserts help)

### Have a feeling of the type of insight you're looking/you need

### Never miss the easy problem

### Spend an extra 30 seconds when making a big decision on what to spend time on

### Consider taking a step back if you get stuck

### READ THE STATEMENT CAREFULLY!!!

### Know which problems are impossible so you don't try to solve something impossible

### Don't be afraid to write a brute to search for patterns. Try printing your DP table

# Philosophy
Learn all basic algorithm. Both Kahn's and DFS for toposort. Both Kadane's and map over prefixes for max sum subarray.
They all generalize in different directions.

# VS code
Try CTRL c, v, z. Hopefully you know this.
You can do CTRL+X to cut a line. Useful to delete line.
You can move line using alt + up/down arrow.
Zoom using CTRL + or -

Switch to US layout for extra speed.

# Command line
Learn to use command line.
Up arrow to get to previous command.
Ctrl c to kill currently running program.
Select + right click to copy, right click to paste.
Tab to autocomplete.

Learn basic commands: `cat`, `diff`, `cd`, `mkdir`, `time`, `cp`.

# C++

## Basic template

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1e18;

typedef vector<ll> vi;

#define rep(i,a,b) for (int i = a; i < b; i++)
#define sz(x) ((ll)x.size())
#define all(x) begin(x), end(x)

## emplace_back
Instead of

vector<pair<int,int>> arr;
arr.push_back(make_pair(a,b));

Do

vector<pair<int,int>> arr;
arr.emplace_back(a,b);

For set and other structures it's `emplace`.

## Structured bindings

vector<pair<int,int>> nums = ...;
for (auto [a, b] : nums) {
    ...
}

priority_queue<pair<int,int>> pq;
pq.emplace(...);
while (sz(pq)) {
    auto [d,u] = pq.top();
    ...
}

Works on `tuple` too.

## Fast I/O

cin.tie(0)->sync_with_stdio(0);

NEVER do `cout << x << endl` unless interactive. Instead, do `cout << x <<
"\n";`

## Compile command
`g++ sol.cpp -fsanitize=undefined,address -g -Wall -Wconversion`

Example of why to use -Wall:

i.cpp: In function ‘ll sol(Node*, Node*)’:
i.cpp:51:31: warning: suggest parentheses around comparison in operand of ‘^’ [-Wparentheses]
   51 |     if (a->xorsum ^ b->xorsum == 0) return -1;
      |                     ~~~~~~~~~~^~~~

## Pragmas

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

## Exit hard
`_Exit(0)` if you want to exit without cleaning up memory. Remember to flush. If you don't, your program probably wont output everything and you will get WA.

cout << endl;
_Exit(0);

For example, if you want to use `Node*` together with `-fsanitize=undefined,address`, you probably want to `_Exit(0);` to avoid error messages when the only errors are memory leaks (which we don't care about).

## Big ints (GCC only)

__int128_t x;
__uint128_t u;
long double k = sqrtl(1)+logl(2);
__float128 f;

## Bitset
Goated. Nuff said.

## Variable size bitset

const int MAXLEN = ...;
template <int len = 1>
void solve(int n) {
    if (n > len) {
        solve<std::min(int(len*1.3), MAXLEN)>(n);
        return;
    }
    // solution using bitset<len>
}

## array
Consider using `array<3,int>` if you know the size.

## Advanced: perf
`g++ sol.cpp -O3 -g`
`perf record ./a.out < in.txt`
`perf report -M intel`

# Algorithms

## Binary search over relative error
If you do binary search over floats and answer is $>1$, it's faster to
`mid=sqrt(lo*hi);`
If answer is $<1$, normal is faster.

## Ternary search
instead of

double lo = 0, hi = 1e9;
while (lo+0.00001 < hi) {
    double l = lo + (hi-lo)/3;
    double r = hi - (hi-lo)/3;
    if (f(l)>f(r)) lo = l;
    else hi = r;
}

Do

double lo = 0, hi = 1e9;
rep(i, 70) { // constant iterations
    double l = lo + (hi-lo)/3;
    double r = hi - (hi-lo)/3;
    if (f(l)>f(r)) lo = l;
    else hi = r;
}

## Proper djikstra

vi dist(n, inf);
dist[0]=0;
priority_queue<p2> pq;
pq.emplace(0,0);

while (sz(pq)) {
    auto [d,u]=pq.top();
    pq.pop();
    d=-d;
    if (d>dist[u]) continue;
    for (auto [w, e] : adj[u]) {
        if (d+w<dist[e]) {
            dist[e] = d+w;
            pq.emplace(-(d+w), e);
        }
    }
}

## Random shuffle prefmax
If you randomly shuffle an array and compute the prefix max of it, the number of times it changes is $O(\log(N))$ in expectation.

## Fast set
Design data structure that stores set of numbers:
- Take any element and delete it
- Insert element that doesn't exist

Harder:
- Take any element
- Delete any element

## Lazy increment/reset
Design a data structure that supports:
- Check value of element
- Add constant to all
- Set all elements to some value

Implicit add on keys/values in a set

Special case visited list for DFS is very nice

## Harmonic complexity

for (int l = 1; l < n; l++) {
    for (int i = 0; i < n; i += l) {
        ...
    }
}

Runs in $O(N\log(N))$.

# Number theory
## Primes
Every number has at most $O(\log(N))$ prime divisors. Doing something in $O(2^{unique \space prime \space divisors})$ is approximately $O(\sqrt{N})$.

## Divisors
The number of divisors of a number is approximately $O(N^{\frac{1}{3}})$. Common ICPC strategy is to factor in $O(N^{\frac{1}{4}})$ using KACTL pollard-rho, then generate all divisors.

## Partitions
Let $P(x)$ be the number of unordered sets of integers with sum $x$.
| $x$ | $P(x)$ |
|---|---|
| 7 | 15 |
| 8 | 22 |
| 9 | 30 |
| 20 | 627 |
| 50 | $2 \cdot 10^5$ |
| 100 | $2 \cdot 10^8$ |

# Cheese
## Factor

import subprocess
n = 10
print(subprocess.run("factor", input=str(n).encode(), capture_output=True).stdout.decode())

## Keep subtask solutions
If you have solved $N \leq 1000$, keep it when going for bigger $N$. Sometimes, judges forget to embed special cases into bigger testcases.

if (n <= 1000)
{
    ...
    return 0;
}

## Extracting info
Suppose you want to find out how your algorithm fails in more detail. Then you can add lots of `asserts` and submit again. 1 bit / submission

## Run until out of time

auto start = chrono::high_resolution_clock::now();
rep(i,n)
{
    int elapsed_millis = chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count();

    // break early if we run out of time 
    if (elapsed_millis>980) break;
    // try candidate i
    ...
}

# More reading
https://codeforces.com/blog/entry/100910

# Hard part
# Algorithms
## Coordinate compression
If you have $N=10^5$ number $\in [0, 10^9]$, but only their relative order matters, you can sort them and reassign them a number in $[0,N)$.

## Sweepline
Sort by one dimension, have data structure over other. 2D rectangle sum queries is this with segtree.

## Red rule/blue rule
Red rule/blue rule MST.
Red rule: take any cycle. The heaviest edge can never be part of the MST.
Blue rule: take any cut (partition of vertices into disjoint sets). Take the lightest edge between them. This is guaranteed to be in the MST.

## Faster persistent/sparse segtrees
Instead of

struct Node {
    Node *l=0,*r=0;
    ...
    void update() {
        ... new Node(...);
    }
}

Do

struct Node {
    int l=-1, r=-1;
}
Node nodes[int(2e7)];

void update(int x, int l, int r, ...) {
    ...
}

Also, don't store `l` and `r` in the node.

## Max is invertible (sometimes)
Suppose you have $N$ points $(x,y)$ with goodness $w$. If you get queries "best point with $x \in [a,b]$ and $y \neq v$", instead of 2D segtree, have 1D segtree that stores best and second best. Generalizes to li chao tree, centroid decomp etc, saving a logfactor.

## Circular -> flat
Suppose you have an array $x$ which is circular. Sometimes, it's easier to work on $x+x$. Be careful that you don't do anything invalid.

## Everything but an interval
This trick works for all data structures with insert in non-amortized $O(T(N))$ times. $O(N\log(N)T(N))$.

void rec(int l, int r, structure& s) {
    if (l==r) {
        ...
        return;
    }
    int mid = (l+r)/2;
    rep(i,mid,r+1) s.add(i);
    rec(l, mid, s);
    rep(i,mid,r+1) s.undo();
    
    rep(i,l,mid+1) s.add(i);
    rec(mid+1, r, s);
    rep(i,l,mid+1) s.undo();
}

## Offline dynamic Connectivity

## Constructive -> interactive
Imagine you are given lots of information and need to construct object with those properties. Thinking of it as an interactive problem instead might help.

## Find configuration, rank swaps
Suppose you have lots of choices that are semi-independent. Make choices towards one extreme, put all exchanges in priority queue.