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…

1236 -- Network of Schools Given a network, answer at least how many nodes we need to spread information to let the whole graph know, and the minimum directed edges required to add so the whole graph becomes an SCC. The first query is just…

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

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

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…

A deque ( double ended queue ) is a data structure that supports push/ pop from both ends with constant time complexity. It can be used to optimize algorithms that deal with monotonous properties. The first time I saw this data structure, …

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem. Here are some problems for exercise from the ant book. 3250 -- Bad Hair Day POJ 3250 Bad Ha…

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…

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…

Problem statement: 100 people are on the same field, and each of them wears a hat with a color ( only 2 kinds of colors ). Each of them can see all the distribution of the colors except his/her own. Now each person has to guess the color o…

Dashboard - AIM Tech Round (Div. 2) - Codeforces pA. Print ( L - d ) / ( v1 + v2 ). #include <bits/stdc++.h> using namespace std; int main(){ int d, L, v1, v2; scanf("%d %d %d %d", &d, &L, &v1, &v2); double dis = (double)L - d; double vel = (double)v1 + </bits/stdc++.h>…

Mex ( minimum excludant ), has an interesting property in game theory, where an sprague grundy value of a state in a fair game can be deduced from the mex of the sg-values of all the states it could reach in the next step.The definition of…

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…

There are many problems that require high precision mathematical operations that we need to implement big number functions. However, sometimes we could avoid this by making use of double and long double, and perhaps some cmath library func…

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 <…