0w1

Template

HE April Circuits 2A - Bear and All Permutations ( Bigint )

https://www.hackerearth.com/april-circuits/algorithm/2a-bear-and-all-permutations-1/ We can simply simulate for each answer since n is only up to 12. However, it still takes a lot of time, and the number is extremely large, we will have to…

Math Vector Template

Haven't yet tested well, might have some bugs. #include <bits/stdc++.h> using namespace std; const double EPS = 1e-10; const double PI = acos( -1.0 ); int dcmp(double x){ if( fabs( x ) < EPS ) return 0; return x < 0 ? -1 : 1; } struct Vector{ double x, y</bits/stdc++.h>…

Persistent segment tree

2104 -- K-th Number Given n ≤ 1e5 numbers a1, a2 .., an, then there are m ≤ 1e5 queries [ l, r ], for each query, answer the k-th minimum number among al, a(l + 1) .., ar. First we discretize the integers so that there are at most 1e5 inte…

POJ 3260 The Fewest Coins ( Knapsack multiple & complete DP )

3260 -- The Fewest Coins n ≤ 100 types of currency exists, each value v[i] ≤ 120, and I have c[i] ≤ 100 of them. Answer the minimum sum of coins that I have to give and take, when I am to buy a product of T ≤ 10000 dollars. This is basical…

Lowest common ancestor

I have finally started to understand the LCA algorithm for transforming to RMQ. Here are the basic steps for static LCA queries: 1. DFS from any node as the root for the tree, making timestamps as it goes ( called the Euler's tour ). 3 bas…

Fast Fourier Transform

Fast fourier transform can be applied on multiplication of polynomial functions, giving O( N lgN ) time complexity. One of the most common usage is for fast multiplication on big numbers. It exploits the property of the complex roots of un…

Introduction to DP on digits ( 桁DP / 數位統計 )

pekempey.hatenablog.com 苦手だったけどpekempeyさんの記事見てよく理解できました、ありがとうございます。pekempeyさんの書き方をモノマネする事になるけどそこはどうか許してください(汗)。 Atcoder Beginner Contest 29 pD. Submission #631749 - AtC…

Randomized binary search tree

いつか貼ろうと思ってました。始めて学べた頃は可読性の高いソースコード見当たらなくて(中国人のコードはもう。。)、理解に色々と苦労しましたOrz、もちろん自分のがわかりやすいとも言えませんが、もし分からない部分があれば是非コメントして下さい、知…

Monotonous slope optimization DP

This optimization is also called "Convex Hull Trick" because it is either maintaining an upper convex hull ( decreasing slopes ) or a lower convex hull. Also note that there are problems that do not necessarily have to be monotonous but st…

Randomized binary search tree on value

I have never wrote one to split by value, but for segments. Here's a simple problem that gave me my first chance to solve one like that. http://zerojudge.tw/ShowProblem?problemid=d794 World Ranking The input will give you scores, and you h…

Strong connected components

When a directed graph set S satisfies "for every vertex u and v, exists a path from u to v", this graph could be called an SCC. SCC can be found by applying DFS twice. This is called Kosaraju's algorithm O( V + E ). DFS1 will start from an…

Biconnected Components

A vertex biconnected component (bcc) can be defined as a connected component (cc) that is still a cc after any vertex is plucked out of the graph, and usually we would think about the bcc as the largest component that satisfies. An edge bc…

Introduction to Mo's Algorithm

Range Mode Query: http://zerojudge.tw/ShowProblem?problemid=b417 Given N numbers, M queries for ( ql, qr ), output the maximum frequency and the count of the maximum frequency in range [ ql, qr ] of the N numbers. ( 1 <= N <= 1e5, 1 <= M <…