# CF #526 Div.1 E: The Fair Nut and Rectangles

https://codeforces.com/contest/1083/problem/EIf we may use 128bit integers, this problem will be easier than the original one. The most difficult task is the comparison of two rational numbers with large digits. There exists a sophisticate…

# Compute exp and log of formal Dirichlet series in O(n log^2 n) time

Maybe this already exists and some of them are unreliable. The exponential of a formal Dirichlet series can be written as\begin{align} \exp\left( \frac{a_2}{2^s} + \frac{a_3}{3^s} + \frac{a_4}{4^s} + \cdots \right) = \exp\left( \frac{a_2}{…

# Codeforces #519 F. Make It One

UPD: November 11, 2018I believe this property always holds, but I haven't shown the correctness yet. For small n, we can check the correctness partially: https://ideone.com/ljg1Ul. Perhaps, the Dirichlet convolution and the Möbius inversio…

# Exponential Function Evaluation

This article shows an implementation of the exponential of a formal power series. This runs in O(n log n) time. I compute the nth term of the partition function for benchmark.https://ideone.com/m1LAWr [1] is a standard reference of formal …

# Analysis of path halving for DSU

Consider the following implementation of DSU. This approach is shown in [1, 2]. int find(int x) { while (p[p[x]] != p[x]) x = p[x] = p[p[x]]; return p[x]; } void link(int x, int y) { p[find(x)] = find(y); } Surprisingly, both find and link…

# Find the nth partition number mod p in O(n log n)

This algorithm comes from a study of subset sum [1]. exp, log, recip are described in [2]. The generating function of partition number is $(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)(1+x^3+x^6+\cdots)\cdots.$The logarithm of this function is\[ …

# Regarding linear time implementation of shakutori

I introduced this problem before: https://pekempey.hatenablog.com/entry/2018/09/18/085432This technique can be applied to shakutori (also known as two pointers or sliding window). Its implementation is a little complicated but it might be …

# RMQ using BIT

An implementation of this document: https://ioinformatics.org/journal/v9_2015_39_44.pdfUpdate O(log n), query O(log n). Update is slightly slower than segtree based RMQ, but query is slightly faster. I have written it once before, but it i…

# Pivots

https://onlinejudge.u-aizu.ac.jp/beta/room.html#ACPC2018Day3/problems/BI found an interesting solution. Most of the solutions use a linked list, but it is based on another property. The operation LxR->RxL is similar to LR->RL. LR->RL is we…

# Knapsack and Queries

https://jag2018summer-day2.contest.atcoder.jp/tasks/jag2018summer_day2_dIt's very interesting. The key property is a queue can be simulated by two stacks. Each push query, you can compute new values of dp in O(mod). Pop query is trivial, j…

# September Challenge 2018

Official editorial: https://discuss.codechef.com/tags/sept18/ BSHUFFLE I don't know why this is correct. https://ideone.com/p8tq79 TABGAME View the win-loss table diagonally and alternately. You can realize that the values almost unchange …

# digit dp

digit dp を説明する。過去に書いた記事では digit dp による複数の問題を扱っているが、この記事では最も基礎となる $n$ 以下の自然数の総数を求める問題のみを扱う。https://pekempey.hatenablog.com/entry/2015/12/09/000603明らかに答えは $n+1$ である…

# Microsoft Q# Coding Contest - Summer 2018

http://codeforces.com/contest/1002I had never study quantum computing. I acquired all the knowledge of quantum computing from only a official tutorial. I mean I am not an expert, so this article is unreliable.Write a quantum program | Micr…

# Euler tour tree implementation using a circular skip list

I implemented an euler tour tree using a skip list. Typically, a skip list is used as dictionary structures. However this skip list is merely used as a doubly linked list which can be joined and split fast, and can determine whether given …

# GCJ 2018 round2

A 問題 i 番目と i+1 番目の間をいくつのボールが通過するかを計算できると、それをそのまま。 B 問題 丁度にする必要はなくて、適当に辻褄をあわせることができる、というのが重要な考察。 (i,j) を使う、というのを n×n グリッドの (i,j) の位置に駒を置く…