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