Programming Tips - HackMD

<style> .reveal { font-size: 32px; } </style>  ## Programming Tips #### and Useless Knowledge `HyperSoWeak` --- ## Team Project You will learn (maybe) - Git usage (branch / merge / PR) - Basic (or advanced) python / javascript / ...? - Team programming (write clean and readable code) --- ## ToC - Functions - Miscellaneous - Recursion - Bitwise Operation - Graph --- ## Funtions ---- ### qsort ```cpp int cmp(const void *a, const void *b) { return (*(int*)a - *(int*)b); // May overflow } qsort(a, n, sizeof(a[0]), cmp); ``` ```cpp int cmp(const void *a, const void *b) { int A = *(int *)a; int B = *(int *)b; if(A > B) return 1; if(A < B) return -1; return 0; } ```  ---- ### qsort For struct ```cpp int cmp(const void *a, const void *b) { struct Date *A = (Date *)a; struct Date *B = (Date *)b; if(A->year != B->year) return A->year - B->year; if(A->month != B->month) return A->month - B->month; return A->day - B->day; } ``` For string (lexicographical order) ```cpp int cmp(const void *a, const void *b) { char *A = (char *)a; char *B = (char *)b; for(int i=0; i<strlen(A) && i<strlen(B); ++i) { if(A[i] != B[i]) return A[i] - B[i]; } return strlen(A) - strlen(B); } ``` [Merge sort](https://en.wikipedia.org/wiki/Merge_sort) ---- ### Sort (C++) ```cpp sort(a, a+n); // ascending order sort(a, a+n, greater<int>()); // descending order sort(v.begin(), v.end()); // vector bool cmp(int x, int y) { if(x & 1) return x < y; // ascending order else return x > y; // descending order } sort(a, a+n, cmp); // custom compare function ``` ---- ### gcd and lcm ```cpp int gcd(int a, int b) { int r; while(a%b != 0) { r = a%b; a = b; b = r; } return r; } ``` ```cpp int gcd(int a, int b) { return b>0 ? gcd(b, a%b) : a; } ```  ```cpp int lcm(int a, int b) { return a / gcd(a, b) * b; } ```  ---- ### pow ```cpp #include <math.h> pow(5, 3); // 125 ``` ### fastpow ```cpp ll fastpow(ll n, int p) { ll ans = 1; for(;; p >>= 1, n = n * (n % MOD)) if(p & 1) ans = ans * (n % MOD); return ans; } ```  --- ## Miscellaneous ---- ### Print Array ```cpp rep(i,0,n) printf("%d%c", a[i], " \n"[i==n-1]); ``` ---- ### Who da fuck will use this? ```cpp -~n // n + 1 ~n+1 // -n (n<<3) + (n<<1) // n * 10 ``` ---- ### Define Trap ```cpp #define int long long #define INF 1e9+1 #define intPtr (int *) int cmp(const void *a, const void *b) {} int main() { intPtr a, b; cout << -INF; } ``` ---- ### Define ```cpp #define max(x, y) ((x) > (y) ? (x) : (y)) #define abs(x) ((x) < 0 ? (-x) : (x)) ``` ```cpp #define str(x) #x str(8964) // "8964" str(" \ " is backslash) // "\" \\ \" is backslash" ```  ---- ### Define charizing operator `#@` ```cpp #define C(x) #@x C(7) // '7' ``` Token-Pasting operator `##` ```cpp #define f(x) func_##x f(3)(1, 'c'); // func_3(1, 'c'); ``` ---- ### Define ```cpp #undef MAXN #define MACRO(arg1, arg2) do { / /* declarations */ / stmt1; / stmt2; / /* ... */ / } while (0) /* (no trailing ; ) */ ``` ```cpp #ifndef _NAME_H #define _NAME_H // header content #endif #pragma once // ? ``` ---- ### Fast IO ![image](https://hackmd.io/_uploads/r1rs7yIaa.png)  ---- ### Fast IO ```cpp #pragma GCC optimize("Ofast") #define MAXSIZE (1 << 20) char buf[MAXSIZE], *p1=buf, *p2=buf; char gc() { if(p1==p2 && (p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin))==buf) return EOF; return *p1++; } static inline int readInt() { int x=0; char c=gc(), neg=0; while((c>'9'||c<'0') && c!='-' && c!=EOF) c = gc(); if(c=='-') neg = 1, c = gc(); while(c>='0'&&c<='9') { x = x*10+(c-'0'); c = gc(); } if(neg) x = -x; return x; } ``` ---- ### Fast IO ```cpp char pbuf[MAXSIZE], *pp=pbuf; static inline void pc(const char c) { if(pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf; *pp++ = c; } static inline void printInt(int x) { static char ch[16]; static int idx = 0; if(x < 0) x = ~x+1, pc('-'); if(x == 0) ch[++idx] = 0; while(x > 0) ch[++idx] = x%10, x/=10; while(idx) pc(ch[idx--]+48); } signed main() { const int MAXN = 1e6; int a[MAXN]; for(int i=0; i<MAXN; ++i) a[i] = readInt(); for(int i=0; i<MAXN; ++i) printInt(a[i]); fwrite(pbuf, 1, pp - pbuf, stdout); } ``` ---- ### Function Pointer ```cpp void func(int n, char c) {} static void (*funcPtr)(int, char) = func; funcPtr(1, 'a'); // = func(1, 'a'); ``` ---- ### Function Pointer ```cpp static void (*Command[])(int, int) = {Add, Remove, Move, Merge}; signed main() { // ... while(m--) { scanf("%d %d", &t, &x); if(t != 2) scanf("%d", &y); Command[t-1](x, y); } // ... } ``` --- ## Recursion [Example](#/5/1) ---- ## Recursion [Example](#/5) ---- ### [Patrick's Parabox](https://youtu.be/ZTriagFru3Q?t=6760) ![image](https://hackmd.io/_uploads/rJfTiJZpT.png) [Steam](https://store.steampowered.com/app/1260520/Patricks_Parabox/) ---- ### [Zerojudge f640](https://zerojudge.tw/ShowProblem?problemid=f640) ---- ### Cyclic Complexity ```cpp bool rep(int i, int end) { // do something return i<end && rep(i+1, end); } rep(1, 100); ``` ---- ### Cyclic Complexity ```cpp bool rep2(int i, int end, int j) { printf("%d ", i+(j-1)*100); return i<end && rep2(i+1, end, j); } bool rep(int i, int end) { rep2(1, 100, i); return i<end && rep(i+1, end); } rep(1, 100); ``` ---- ### DFS ```cpp bool vis[MAXN][MAXN]; int dx[] = {0, 1, 0, -1}; int dy[] = {1, 0, -1, 0}; int DFS(int x, int y) { if(vis[x][y]) return; vis[x][y] = true; // do something for(int i=0; i<4; ++i) { DFS(x+dx[i], y+dy[i]); } } ``` ```cpp DFS(x+(i&1)*2-1, y+(i>>1&1)*2-1); ```  ---- ### Josephus Problem ![image](https://hackmd.io/_uploads/ByH4AHXpp.png) $n$ people and $k - 1$ skips each round Find the initial index of the survivor ---- #### Solution 1 - Linked List Time complexity: $O(nk)$ ---- #### Solution 2 - Recursion Time complexity: $O(n)$ <span style="color: gold">yay</span> $f(n, k)$: The winner index if $n$ people and $k_{th}$ is killed  \begin{cases} \text{$f(1, k) = 0$}\\ \text{$f(n, k) = (f(n-1, k) + k)\ \%\ n$} \end{cases}  [Explanation](https://www.zhihu.com/tardis/zm/art/121159246?source_id=1003)  --- ## Bitwise Operation ```cpp ~, &, |, ^, <<, >> ``` ---- ### Warning - Always tricky and hard to debug, make sure you fully understand it before using it. Wrong ```cpp long long a; bool firstBit = a & (1 << 63); ```  Correct ```cpp unsigned long long a; bool firstBit = a & (1ULL << 63); ```  ---- ### Common Usage - $2^n$ - Small size set operations - XOR properties ---- ### Swap without temp ```cpp #define swap(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b))) ``` ----  ### Unique Element > Given an array where all elements are repeated twice except for one, please find that unique element. ##### Constraints $N \leq 10^8, -10^{18} \leq a_n \leq 10^{18}$ ##### Sample Input ``` 4 5 4 1 2 5 3 2 1 ``` ##### Sample Output ``` 3 ``` ---- ### Solution - $p \oplus 0 = p$ - $p \oplus p = 0$ - Commutative law ```cpp while(n--) { cin >> a; ans ^= a; } cout << ans; ```  ---- ### Nim Game [UVa 10165](https://onlinejudge.org/external/101/10165.pdf) #### Solution  ```cpp while(n--) { cin >> a; ans ^= a; } cout << (ans ? "Yes" : "No"); ```  [Explanation](https://gist.github.com/amoshyc/59009070d3807a02b7b5)  ---- ### SWAR ##### Find MSB ```cpp unsigned int msb32(register unsigned int x) { x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return(x & ~(x >> 1)); } ```  ##### Count One  ```cpp int countOne(unsigned int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } ```  [Bitwise Magic](http://www.aggregate.org/MAGIC)  ---- ### Fast Inverse Square Root (`0x5f3759df`) `0x5f3759df` $\approx \sqrt{2^{127}}$ $\log_2 (\frac{1}{\sqrt{x}}) = -\frac12 \log_2x$ ```cpp float q_rsqrt(float number) { long i; float x2, y; const float threehalfs = 1.5F; x2 = number * 0.5F; y = number; i = * ( long * ) &y; // evil floating point bit level hacking i = 0x5f3759df - ( i >> 1 ); // what the fuck? y = * ( float * ) &i; y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed return y; } ``` --- ## Graph ---- ### Binary Tree Node [Example](https://youtu.be/3K3MMtoG8rY) - pointer - pseudo pointer - array ---- ### Pseudo Pointer ```cpp struct Node { int val; int lc, rc; } int n = 0; Node a[MAXN]; int newNode(int val, int lc=-1, int rc=-1) { a[n].val = val; a[n].lc = lc; a[n].rc = rc; return n++; } a[x].lc = newNode(y); ``` ---- ### Array ```cpp int lc = id << 1; int rc = id << 1 + 1; ``` SegTree huh? `(L + R) | (L != R)` ---- ### Store Edges ![image](https://hackmd.io/_uploads/ryiFTF76T.png =300x) - Adjacency Matrix - Adjacency List - Edge List ---- ### Adjacency Matrix ![image](https://hackmd.io/_uploads/ryiFTF76T.png =300x) | |0|1|2|3|4|5| |-|-|-|-|-|-|-| |0|0|0|1|0|1|0| |1|0|0|0|0|0|1| |2|1|0|0|1|1|0| |3|0|0|0|0|0|0| |4|0|0|1|0|0|1| |5|0|0|0|0|1|0| ---- ### Adjacency List ![image](https://hackmd.io/_uploads/ryiFTF76T.png =300x) - **0**: 2, 4 - **1**: 5 - **2**: 0, 3, 4 - **3**: - **4**: 2, 5 - **5**: 4 ---- ### Edge List ![image](https://hackmd.io/_uploads/ryiFTF76T.png =300x) [ (0, 2), (0, 4), (1, 5), (2, 0), (2, 3), (2, 4), (4, 2), (4, 5), (5, 4) ] --- ## Exercise - [ZJ - c296. APCS-2016-1029-3定時K彈](https://zerojudge.tw/ShowProblem?problemid=c296) - [JudgeGirl - 50243. Friend Cover](https://judgegirl.csie.org/problem/0/50243) - [JudgeGirl - 248. Mine Field](https://judgegirl.csie.org/problem/0/248)