## 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)