Presets for NOI series Algorithm Contests

Posted on 2021-10-23 Edited on 2022-04-15

Presets for NOI series Algorithm Contests

System Settings

1
2
3

gsettings set org.gnome.desktop.interface cursor-blink false
gsettings set org.gnome.desktop.wm.preferences focus-mode mouse
xset r rate 300 50  # X11 repeat rate

Editor Configuration

GNOME Terminal

Change color schemes to Tango dark.

Vim

in ~/.vimrc

syntax on
set expandtab softtabstop=2 shiftwidth=2
set ai cindent copyindent
set mouse=a
"set number relativenumber
autocmd BufWritePost *.cpp :!g++ -DMISAKA %:p -o %:p:r
autocmd BufNewFile *.cpp 0r ~/cpp.cpp
nmap S :s//g<left><left>
inoremap ' ''<left>
inoremap " ""<left>
inoremap { {}<left>
inoremap ( ()<left>
inoremap [ []<left>
inoremap { {}<left>
inoremap {<CR> {<CR>}<ESC>O
inoremap "" "
inoremap '' '
inoremap [[ [
inoremap (( (
inoremap {{ {

Code::Blocks IDE Configuration (Debugging)

Reminder: debugging with Code::Blocks requires pasting original code to main.cpp then paste the modified version back, be careful!

Create a new project
choose Console application
specify folder name (must done)
copy code to main.cpp to start debugging;

Code Snippets/Templates

C++ main solution file

in ~/cpp.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int, int> pii;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i < (k); ++i)
#define ROF(i, j, k) for (int i = ((k) - 1); i >= j; --i)
template<typename T>
inline void chkmin(T &a, const T b) {
  a = min(a, b);
}
template<typename T>
inline void chkmax(T &a, const T b) {
  a = max(a, b);
}

const int N = ;

inline void solve() {

}

int main() {
#ifndef MISAKA
  freopen(".in", "r", stdin);
  freopen(".out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
#endif
  solve();
  return 0;
}
/* Checklist:
 * - data type
 * - overflow
 * - typo/logic
 * - special cases
 * - cleanup (multi-test)
 * - bounds
 * - memory usage
 * - file IO
 */

C++ generator

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int, int> pii;
#define mkp make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i < (k); ++i)
#define ROF(i, j, k) for (int i = ((k) - 1); i >= j; --i)
template<typename T>
inline void chkmin(T &a, const T b) {
  a = min(a, b);
}
template<typename T>
inline void chkmax(T &a, const T b) {
  a = max(a, b);
}

typedef uniform_int_distribution<int> ui;
mt19937 gen;

const int N = ;

int main() {
  gen = mt19937(chrono::steady_clock().now().time_since_epoch().count());

  return 0;
}

checker script (random test cases batching)

Reminder: compile solution code without local flag.

one-liner validator script

for ((i=0; i < 10000; ++i)) {
    echo "#$i"; ./gen > ex.in 2> ex.ans; ./ex;
    diff ex.out ex.ans || break;
}

one-liner stress test script

1
2
3

for ((i=0;i<10000;++i)) {
    echo "#$i"; ./gen > ex.in; time ./ex
}

other linux utilities

generate strings from `/dev/urandom`.

1	tr -dc "[a-z]" < /dev/urandom \| head -c 1000

Reminders

Checklist

data type
overflow
typo/logic
special cases
cleanup (multi-test)
bounds
memory usage
file IO

Coding (Vim)

Since it's auto compile, never blindly :wq out of vim. Instead, see the compiler logs.
backup source file before massive modifications.
use vim with a calm mind to prevent disasters.

Update

#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void O(const T &x) { cout << x << '\n'; }
template <typename T, typename... W> inline void O(const T &x, const W &...b) {
  cout << x << ' ';
  O(b...);
}
#ifndef MISAKA
#define err(...)
#else
#define err(...) fprintf(stderr, __VA_ARGS__)
#endif
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef long double dbl;
typedef pair<int, int> pii;
typedef uniform_int_distribution<int> r32;
typedef uniform_int_distribution<i64> r64;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define shuf(L, R) shuffle((L), (R), rng)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define FOR(i, j, k) for (int i = (j); i <= (k); ++i)
#define ROF(i, j, k) for (int i = (k); i >= (j); --i)
template <typename T> inline void ckmin(T &a, const T &b) { a = min(a, b); }
template <typename T> inline void ckmax(T &a, const T &b) { a = max(a, b); }
//#define IOFILE "filename"
//#define MULTI
const int N = 0;

inline void sol() {
  //
}

int main() {
#ifndef MISAKA
#ifdef IOFILE
  freopen(IOFILE ".in", "r", stdin);
  freopen(IOFILE ".out", "w", stdout);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
#endif
#ifdef MULTI
  int T;
  cin >> T;
  while (T--)
#endif
    sol();
  return 0;
}

syntax on
set expandtab softtabstop=2 shiftwidth=2
set ai cindent copyindent
set mouse=a
"set number relativenumber
autocmd BufWritePost *.cpp :!g++ -Wall -Wextra -Wconversion -fsanitize=undefined -g -DMISAKA %:p -o %:p:r
autocmd BufNewFile *.cpp 0r ~/misaka-cp/template/contest.cpp
nmap S :s//g<left><left>
inoremap ' ''<left>
inoremap " ""<left>
inoremap { {}<left>
inoremap ( ()<left>
inoremap [ []<left>
inoremap { {}<left>
inoremap {<CR> {<CR>}<ESC>O
inoremap "" "
inoremap '' '
inoremap [[ [
inoremap (( (
inoremap {{ {

" extra
map <F5> :!xclip -selection c -o\|%:p:r<CR>
map <silent> <F6> :w !xclip -selection c<CR><CR>

AGC002

Posted on 2021-10-13 Edited on 2022-02-24 In AGC Series

AtCoder Grand Contest 002 - AtCoder

D - Stamp Rally

通过BFS形态的整体二分，实现数据结构中只用维护加边操作。\(O(n\log n *DSU)\)

F - Leftmost Ball

不妨规定颜色出现顺序为\(1\rightarrow n\)省去容斥的麻烦。

将问题转化为拓扑序计数进行DP。

AGC001

Posted on 2021-10-09 Edited on 2022-02-24 In AGC Series

AtCoder Grand Contest 001

Problem E

由于每个\((i, j)\)对答案的贡献是\(a_i+b_i+a_j+b_j\choose a_i\),立即考虑单调路径模型。

发现贡献可以看作\((-a_i, -b_i) \rightarrow(a_j, b_j)\)。

由于值域只有\(2e4\), 直接对所有从第三象限到第一象限的路径DP即可。

F - Wide Swap

通过计算pos数组，操作被转化为\(swap(pos_i, pos_{i+1})\)仅当\(|pos_i-pos_{i+1}|\ge K\)，要求\(1,2,\ldots,n\)贪心地在pos最前。

显然，\(|pos_i-pos_j|\lt K\)的\((i, j)\)顺序不变。对所有这样的\((i,j)\)从i向j连边，形成DAG。

答案即是字典序最小的拓扑排序。

考虑贪心地对没有出边的最大的点赋予更大的序号，这样的\(i\)满足\(P_i=\underset{i-K+1\le j\le i+K-1} {\operatorname{argmax}} P_j\)。

priority_queue + 线段树RMQ。\(O(n\log n)\)

Codeforces Round #747 (Div. 2)

Posted on 2021-10-09 Edited on 2022-02-24 In CodeForces

Codeforces Round #747 (Div. 2)

F - Ideal Farm

let \(s_i=\sum_{k\le i}a_i\)

The Farm is ideal only if there exist \(s_i=s_j+k\).

let \(t_i=s_i+k\), \(t_0=k\)

The Farm is ideal only if for all possible \(\{a_n\}\), a \(s_i\) coincides with \(t_j\).

Since \(s_i,t_i \in[1, s + k]\), we can calculate the maximum possible \(n\).

AtCoder Beginner Contest 221

Posted on 2021-10-07 Edited on 2022-02-24 In AtCoder rounds

AtCoder Beginner Contest 221

H - Count Multiset

差分数列计数+前缀和优化

差分前：

\[ f_{n,k}\leftarrow f_{n-ci,k-i} \]

差分后：

\[ g_{k,s}\leftarrow_{i\lt m} g_{k-i,s-kj} \]

Generating Functions and Combinatorics Classes

Posted on 2021-09-28 Edited on 2022-02-24

Generating Functions and Combinatorics Classes

GF for counting

Posted on 2021-09-28 Edited on 2022-02-24 In Notes

Dependencies

\[ \log(1+z)=\sum_{k\ge1}\frac1k(-1)^{k-1}z^k \]

\[ \exp(z)=\sum_{k\ge0}\frac{z^k}{k!} \]

Lagrange Inversion

given polynomial \(h\) where \(h_0=0\) and \(h_1\not=0\), find \(y\) which \(z=h(y(z))\) holds.

Let \(\phi(y)=y/h(y)\).

Formally, When

\[ y(z)=z\,\phi(y) \]

We have

\[ y_n=\frac1n[u^{n-1}]\phi(u)^{n} \]

\[ [z^n]y(z)^k=\frac k n[u^{n-k}]\phi(u)^n \]

\[ [z^n]H(y(z))=\frac1n[u^n](H^{'}(u)\ \phi(u)^n) \]

Tip: When The Tree equations are too intense to solve try Lagrange Inversion!

OGF

Basic Constructions

\(B=SEQ(A)\)

\[ B(z)=\frac{1}{1-A(z)} \]

\(B=PSET(A)\)

\[ B(z)=\exp(\sum_{k\ge1}\frac{(-1)^{k-1}}{k}A(z^k)) \]

\(B=MSET(A)\)

\[ B(z)=\exp(\sum_{k\ge1}\frac{1}{k}A(z^k)) \]

\(B=CYC(A)\)

\[ B(z)=\sum_{k\ge1}\frac{\varphi(k)}{k}\log(\frac{1}{1-A(z^k)}) \]

Note:

Those equations handle the empty object implicitly, thus:

For general constructions, \(A_0=0\) holds.
For size-restricted constructions \(A_0=1\) holds.

Polya Theorem

Cycle Index

\[ Z(G;x_1,x_2, \dots, x_m)=\frac1{|G|}\sum_{g\in G}x_1^{j_1(g)}x_2^{j_2(g)}\cdots x_m^{j_m(g)} \]

OGF over Groups

\(B=A^M/G\)

\[ B(z)=Z(G;A(z),A(z^2),\dots,A(z^m)) \]

Memorize

Cycle \(Z=\frac1 m\sum_{d|m}\varphi(d)x_d^{n/d}\)
Mirror \(Z=\frac1 2x_1^{2v}+\frac12x_2^v\) or \(Z=\frac12x_1^{2v+1}+\frac12x_1x_2^v\)
All Permutations \(Z=\sum(z^{j_1}z^{j_2}\cdots z^{j_m})/(j_1!j_2!\cdots j_m!1^{j_1}2^{j_2}\cdots m^{j_m})\)

\(PSET_k,MSET_k\)的计算

需要枚举拆分数，套用cycle index

注意，PSET构造时对\(F(z)\)符号取负即可

Additional Useless formula

\[ MSET_k(F) = [u^k]\exp(\sum_{k\ge1}\frac{u^k}kF(z^k)) \]

\[ PSET_k(F) = [u^k]\exp(\sum_{k\ge1}\frac{u^k}k(-1)^{k-1}F(z^k)) \]

\[ CYC_k(F)=[u^k]\sum_{k\ge1}\frac{\varphi(k)}k\log(\frac1{1-u^kF(z^k)}) \]

EGF

\(B=SEQ(A)\)

\[ B(z)=\frac1{1-A(z)} \]

\(B=SET(A)\)

\[ B(z)=\exp(A(z)) \]

*objects are distinguishable through labels anyway.

\(B=CYC(A)\)

\[ B(z)=\log(\frac1{1-A(z)}) \]

*same here.

\(B=SET_k(A)\)

\[ B(z)=\frac1{k!}A(z)^k \]

Additional constructions

\(graph\,F\rightarrow connected\ graph\,G\) (applying inverse operation of exp/polya exp)

\(MSET(G)=F\)

\[ G(z)=\log(F(z)) \]

AtCoder Beginner Contest 217

Posted on 2021-09-05 Edited on 2022-02-24 In AtCoder rounds

AtCoder Beginner Contest 217

Easiest ABC ever!

H - Snuketoon

考虑维护最小伤害的函数\(f_n(x)\)

\[ f_i(x) = \underset{x-\Delta t \leq x_0 \leq x + \Delta t} {\min} f_{i-1}(x_0) + g_i(x) \]

该函数为分段一次函数，且满足凸性，用multiset或者堆维护分段斜率即可。

Deltix Round, Summer 2021 (Div.1 + Div.2)

Posted on 2021-08-30 Edited on 2022-02-24 In CodeForces

Deltix Round, Summer 2021 (Div.1 + Div.2)

Problem - D - Codeforces

key inspection:

\[ a\ \mathrm{and}\ b + a\ \mathrm{\text or}\ b = a + b \]

DS on trees

Posted on 2021-08-23 Edited on 2022-02-24

Data structure/Divide and Conquer Technique On Trees

Centroid Decomposition（点分治）

[IOI2011]Race - 洛谷

DSU on Tree

Problem - D - Codeforces

Centroid Tree（点分树/动态点分治）

The essence of Centroid Decomposition:

Tanuj Khattar's Tutorial on Centroid Tree

Consider any two arbitrary vertices A and B and the path between them (in the original tree) can be broken down into A–>C and C–>B where C is LCA of A and B in the centroid tree.

The vertex C can also be seen as : If we assign labels to centroids in the order in which they are removed from the graph / labels equal to the level at which the centroid occurs in the centroid tree, then C would be the node with smallest label on the path from A–>B in the original tree

Therefore centroid tree breakdown every \(O(n^2)\) path by centroids in a certain layer. When we try to extract all paths passing by an arbitrary node \(u\), all relevant centroids are ancestors of \(u\) on centroid tree.

Additionally, non simple paths(which fall back to the same sub-tree as \(u\) on centroid tree) needs to be excluded.

Exercises:

Problem - G - Codeforces CF757G centroid tree + dynamic segment tree / Persistent Centroid Tree

【模板】点分树 | 震波 - 洛谷

Heavy-Light Decomposition （链分治）

Tricks

链加，单点查询\(\rightarrow\) 树上差分BIT

Exercises:

[SCOI2015]情报传递 - 洛谷利用树上差分，维护一个点到根的和，单点修改时只用修改受影响的子树。

[LNOI2014]LCA - 洛谷对于区间可减贡献，可以将\([l, r] \rightarrow[0, r] - [0, l - 1]\) 扫描线完成

[BJOI2014]大融合 - 洛谷

[Ynoi2017] 由乃的 OJ - 洛谷 directed path, double constant. Difficulty: lxl

七彩树 - 题目 - 黑暗爆炸OJ

Presets for NOI series Algorithm Contests

System Settings

Editor Configuration

GNOME Terminal

Vim

Code::Blocks IDE Configuration (Debugging)

Code Snippets/Templates

C++ main solution file

C++ generator

checker script (random test cases batching)

one-liner validator script

one-liner stress test script

other linux utilities

generate strings from /dev/urandom.

Reminders

Checklist

Coding (Vim)

Update

AtCoder Beginner Contest 221

Generating Functions and Combinatorics Classes

Dependencies

Lagrange Inversion

OGF

Basic Constructions

Note:

Polya Theorem

\(PSET_k,MSET_k\)的计算

Additional Useless formula

EGF

Additional constructions

AtCoder Beginner Contest 217

Deltix Round, Summer 2021 (Div.1 + Div.2)

Data structure/Divide and Conquer Technique On Trees

Centroid Decomposition（点分治）

DSU on Tree

Centroid Tree（点分树/动态点分治）

The essence of Centroid Decomposition:

Exercises:

Heavy-Light Decomposition （链分治）

Tricks

Exercises:

generate strings from `/dev/urandom`.