# [AIdrifter CS 浮生筆錄](https://hackmd.io/@iST40ExoQtubds5LhuuaAw/rypeUnYSb?type=view#Competitive-Programmer%E2%80%99s-Handbook) Competitive Programmer's Handbook : <br> Ch1. Introduction <br> Ch2.Time Complexity
# Basic thechniques
# Introduction
## Programming Language
2017 code jam 有79% 參賽者使用C++ (3000 participants).
## Input and output
- C++ Template
- include `<bits/stdc++.h>`
- `g++ -std=c++11 -O2 -Wall test.cpp -o test`
- `-Wall` : shows warnings about possible errors(-Wall)
- 加速IO
- `ios::sync_with_stdio(0); cin.tie(0);` => make io more effiient
- `\n` is faster than `endl`, becuase `endl` need flush operation
- `scanf()`, `printf()` 還是c的比較快

#include <bits/stdc++.h>

using namespace std;

int main() {

    // enhance IO function
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    freopen("input.txt","r",stdin);
    freopen("output.xtt","w",stdout);

    // possibly containing "spaces"
    string s;
    getline(cin ,s)
    
    // if the amount data is unknown
    while(cin>>x){
        // code
    }
    
    int T,N;
    scanf("%d %d",&T,&N);
    for(int i=1;i<T;i++){
        for(int j=0;j<N;j++)
    }
}

## Working with numbers
### Intergers
- LL is suffix
- `int * int = int` => 所以一定要轉型
- `(long long)`int*int

long long x = 123456789123456789LL;

int a = 123456789;
long long res = (long long)a * a; 

### Modular Arithmetic(模數運算)
(a+b)%m = ((a%m) + (b%m))%m
(a-b)%m = ((a%m) - (b%m))%m
(a*b)%m = ((a%m) * (b%m))%m

- 求n!%m

long long x = 1;
for(int i=1;i<=n;i++)
    x = (x*i)%m;

- C++ 內 modular 為負數
- the remainder of a negative number is either zero or negative.

x = x%m;
if(x<0) x+= m;

### Floating Point numbers
- 印出小數點後九位數

printf("%.9f\n", x);

- rounding errors(捨入誤差)

double x = 0.3*3 + 0.1;
printf("%.20f\n", x) // 0.99999999999999999898

- IEEE 754會有誤差 所以...
- A better way to compare floating point numbers is to assume that two numbers are equal , if the difference between them is less than $\varepsilon$, where $\varepsilon$ is a small number.
- In practice, the numbers can be compared as follows ($\varepsilon=10^{-9}$):
- using \texttt{double},it is possible to accurately represent all integers whose absolute value is at most $2^{53}$.

if(abs(a-b) < 1e-9){
    // a and b are equal
}

## Shortening code
- type name and macro

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for(int i = a; i<=b; i++)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


ll a = 123456789, b=987654321;
cout<<a*b<<endl;
v.PB(MP(y1,x1));
v.PB(MP(y2,x2));
int d = v[i].F + v[i].S;

REP(i,1,n){
    search(i);
}

## Mathematics
### Sum formula
$\sum_{x=1}^n x = 1+2+3+\ldots+n = \frac{n(n+1)}{2}$

and

$\sum_{x=1}^n x^2 = 1^2+2^2+3^2+\ldots+n^2 = \frac{n(n+1)(2n+1)}{6}$
### Arithmetic progression(等差數列)
$3+7+11+15=\frac{4 \cdot (3+15)}{2} = 36$
and
$\underbrace{a + \cdots + b}_{n \,\, \textrm{numbers}} = \frac{n(a+b)}{2}$

### Geometric progression（等比數列）

$a + ak + ak^2 + \cdots + ak^{n-1} = \frac{a(1-k^n)}{k-1}$

special case
$1+2+4+8+\ldots+2^{n-1}=2^n-1.$
### harmonic sum(調和數)
$\sum_{x=1}^n \frac{1}{x} = 1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n} = \log_2(n)+1$

$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6} \le
1+\frac{1}{2}+\frac{1}{2}+\frac{1}{4}+\frac{1}{4}+\frac{1}{4}$

### functions
- celing floor max min
- Fibonacci numbers
- Binets's Formula

### Set Theory
- operation
- intersection
- union
- difference
- Number
$\mathbb{N}$ (natural numbers),
$\mathbb{Z}$ (integers),
$\mathbb{Q}$ (rational numbers) and
$\mathbb{R}$ (real numbers).

### Logic
- **Truth Table**
The value of a logical expression is either
${true}$ (1) or ${false}$ (0).
The most important logical operators are
$\lnot$ ($negation$),
$\land$ ($conjunction$),
$\lor$ ($disjunction$),
$\Rightarrow$ ($implication$)
$\Leftrightarrow$ ($equivalence$).
The following table shows the meanings of these operators:

- To evaluate a if an argument form is valid, the trusty old truth table can be used to evaluate if $(p_1 \land p_2 \land ... \land p_n) \to c$ is indeed a tautology. Using the argument form described above:
$$
\begin{align*}
&p\to q\\
&p \\
\hline
\therefore ~&q
\end{align*}
$$
The truth table:

| $p$ | $q$ | $p\to q$ | $((p \to q) \land p) \to q$ |
| :--: | :--: | :------: | :-------------------------: |
| 1 | 1 | 1 | T |
| 1 | 0 | 0 | T |
| 0 | 1 | 1 | T |
| 0 | 0 | 1 | T |

- A **predicate** is an expression that is true or false
depending on its parameters.
we can define a predicate $P(x)$
that is true exactly when $x$ is a prime number.
Using this definition, $P(7)$ is true but $P(8)$ is false.

- A **quantifier**
- $\forall$ (**for all**) and $\exists$ (**there is**).

### Logarithms
The logarithm of a product is
$log_k(ab) = \log_k(a)+\log_k(b),$

and consequently,
$log_k(x^n) = n \cdot \log_k(x)$

In addition, the logarithm of a quotient is
$log_k\Big(\frac{a}{b}\Big) = \log_k(a)-\log_k(b)$

Another useful formula is
$log_u(x) = \frac{\log_k(x)}{\log_k(u)}$

The **natural logarithm** $\ln(x)$ of a number $x$
is a logarithm whose base is $e \approx 2.71828$.
Another property of logarithms is that
the number of digits of an integer $x$ in base $b$ is
$\lfloor \log_b(x)+1 \rfloor$.
For example, the representation of
$123$ in base $2$ is 1111011 and
$\lfloor \log_2(123)+1 \rfloor = 7$.
## Content and resources
IOI- Ihe International Olympiad in Informations
ICPC - The International Collegiate Programming Contest

# Time Complexity
Asymptopic Notation: Big O

## Caculation rules
- Order of magnitude
- 我們忽略係數 : O(3n) = O(n)
- 選最大的single phase 因為是bottleneck : O(n^3)
- Several Variables : O(mn)
- O(n^3) + O(nm) + O(n) = O(n^3)

// O(3*n)
for (int i = 1; i <= 3*n; i++) {
    // code
}

// O(n^3)
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; j++) {
        // code
        }
    }
}

for (int i = 1; i <= n; i++) {
    // code
}

- Recursion
- 以前離散的recursicve function
- f(n) = f(n-1)+1, n>=1
- f(n) = o(n)

void f(int n) {
    if (n == 1) return;
    f(n-1);
}

- g(n) = 2g(n-1) + 1, n>=1
- g(n) = O(2^n)

void g(int n) {
    if (n == 1) return;
    g(n-1);
    g(n-1);
}

## Complexity Classess
- 除了O(2^n) 和 O(n!) 其他都是polynomial time
- 非polynomial time
- NP-hard problems are an important set of problems, for which no polynomial algorithms known.

$O(1)$
The running time of a **constant-time}algorithm**
does not depend on the input size.
A typical constant-time algorithm is a direct
formula that calculates the answer.

$O(\log n)$
A **logarithmic** algorithm often halves
the input size at each step.
The running time of such an algorithm
is logarithmic, because
$log_2 n$ equals the number of times
$n$ must be `divided by 2 to get 1`.

$O(\sqrt n)$
A **square root algorithm** is slower than
$O(\log n)$ but faster than $O(n)$.
A special property of square roots is that
$\sqrt n = n/\sqrt n$, so the square root $\sqrt n$ lies,
in some sense, in the middle of the input.

$O(n)$
A **linear** algorithm goes through the input
a constant number of times.
This is often the best possible time complexity,
because it is usually necessary to `access each
input element` at least once before
reporting the answer.

$O(n \log n)$
This time complexity often indicates that the
algorithm sorts the input,
because the time complexity of efficient
`sorting` algorithms is $O(n \log n)$.
Another possibility is that the algorithm
uses a data structure where each operation
takes $O(\log n)$ time.

$O(n^2)$
A **quadratic** algorithm often contains
two nested loops.
It is possible to go through all `pairs` of
the input elements in $O(n^2)$ time.

$O(n^3)$
A **cubic** algorithm often contains
three nested loops.
It is possible to go through all `triplets` of
the input elements in $O(n^3)$ time.

$O(2^n)$
This time complexity often indicates that
the algorithm iterates through all
**subsets** of the input elements.
For example, the subsets of $\{1,2,3\}$ are
$\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$,
$\{1,3\}$, $\{2,3\}$ and $\{1,2,3\}$.

$O(n!)$
This time complexity often indicates that
the algorithm iterates through all
**permutations** of the input elements.
For example, the permutations of $\{1,2,3\}$ are
$(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$,
$(3,1,2)$ and $(3,2,1)$.
## Estimating efficiency
- 根據不同的input size，其實可以大概推估演算法所需的複雜度。
- 實際跑測試，不能忘記constant factors，O(n)下除以2，或是*2都是相差兩倍的時間。

| $input size$ | $required time complexity$ |
| :--: | :--: |
| $n \le 10$ | $O(n!)$ |
| $n \le 20$ | $O(2^n)$ |
| $n \le 500$ | $O(n^3)$ |
| $n \le 5000$ | $O(n^2)$ |
| $n \le 10^6$ | $O(n \log n)$ or $O(n)$ |
| $n$ is large | $O(1)$ or $O(\log n)$ |
## Maximum subarray sum
題目條件
- 求出最大的連續元素相加總合
- 元素可以為負
- an empty subarray is allowed, so the maximum subarray sum is alwasys at least 0

### Brute Force　$O(n^3)$
固定起始點**a**，**b**為結束距離，用k去紀錄`{0,n}`中的n個元素。

{0,0} {0,1}  ...  ... {0,n}
      {1,1} {1,2} ... {1,n} 
                      {n,n}

int best = 0;
for (int a = 0; a < n; a++) {
    for (int b = a; b < n; b++) {
        int sum = 0;
        for (int k = a; k <= b; k++) {
            sum += array[k];
        }
        best = max(best,sum);
    }
}
cout << best << "\n";

### Prefix sum　$O(n^2)$
固定起始點**a**，**b**為結束距離，但是不需要用k去重算上次算好的結果，`{0,n} = {0,n-1} + {n,n}`

int best = 0;
for (int a = 0; a < n; a++) {
    int sum = 0;
    for (int b = a; b < n; b++) {
        sum += array[b];
        best = max(best,sum);
    }
}

### One loop $O(n)$
Consider the subproblem of finding the maximum-sum subarray
that ends at position $k$.
There are two possibilities:

- The subarray only contains the element at position $k$.
- The subarray consists of a subarray that ends
at position $k-1$, followed by the element at position $k$.

In the latter case, since we want to
find a subarray with maximum sum,
the subarray that ends at position $k-1$
should also have the maximum sum.
Thus, we can solve the problem efficiently
by calculating the maximum subarray sum
for each ending position from left to right.

int best = 0, sum = 0;
for (int k = 0; k < n; k++) {
    sum = max(array[k],sum+array[k]);
    best = max(best,sum);
}
cout << best << "\n";