Competitive Programming

C++ Template

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
#define int long long
#define endl '\n'
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void solve() {
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}

Courage is all you need?

Solving competitive programming problems involve generally a combination of these following aspects:

Observation: Understanding the problem and come up with non-trivial properties. Abductive reasoning is often very helpful.
Technique: Appling known algorithms or data structures to the problem.
Implementation: Writing the solution fast, bug-free and naturally understandable.

Make sure that you understand various aspects of the problem statement and prove your way towards the solution. Don't be afraid of any type of problem or implementation.

List of basic and important techniques

greedy
binary or ternary search
brute force
dfs, bfs, dijkstra
algebra (is this fft?)
string (is this kmp, trie, hashing, suffix, aho-corasik?)
combinatorics (is this dp? is this bitmasking?)
data structures (is this segment tree?)

Upsolving

Colored Balls, 1954 D
Missing Subsequence Sum, 1966 D: Think in terms of binary representation and construct an array very similar to powers of two. Suppose the highest set bit in k is something and we remove the power of two corresponding to that. How do we then adjust so that we can make numbers till k - 1? How can we adjust further so that we can make all other numbers > k?
Folding Strip, 1966 E
Minimizing Sum, 1969 C
Shop Game, 1969 D
Knapsack 1 and 2, Atcoder DP: We can frame the recursion as dp[number of stuff][weight] = corresponding value or dp[number of stuff][value] = weight (initialized infty?) depending on constraints.
Reverse Card, 1972 D
Codeforces Round 944 (Div. 4)
Codeforces Round 943 (Div. 3)

C++ Template

Courage is all you need?

List of basic and important techniques

Upsolving

References