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) の位置に駒を置く…

Hadamard Transform

Wikipedia には Hadamard Transform について次のように書かれている。Hadamard transform - Wikipedia。 The Hadamard transform can be regarded as being built out of size-2 discrete Fourier transforms (DFTs), and is in fact equivalent to a multi…

April Challenge 2018

Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。CHEFAT: この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割+遅延評価で平均的に速くなるようにした。 多くの提出は $\log(1-x)=…

FFT

(追記:rots の配置変えたら SIMD でやったのとそうでないのとで速度が全く同じになった…。切ない) 追記 環境 多項式乗算を行うだけのコード。サイズ n の 2基底FFT を n/4, n/4, n/4, n/4 の FFT に分割し、n/4 の FFT を SIMD で4並列で行う。実装が簡単…

Visualization Floyd's Cycle Detection

Floyd's Cycle Detection

コンパクトにmod逆元を求める(続き)

コンパクトにmod逆元を求める - pekempeyのブログ で一部解析していなかった部分がうまくいったので書いておきます。具体的には 2-log4 の部分です。a.hs · GitHub再帰の深さの最大値、再帰の深さの総和、最大値を与える最小の x、最大値を与える最大の x、…

CodeChef March Challenge 2018

PSHTRG Q=1 で考えてみよう。これは,数列をソートして最大 3 つを見る,それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと,50th max 程度まで保持するセグメント木があれば…

ARC091 F Strange Nim

https://arc091.contest.atcoder.jp/tasks/arc091_dK を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは,その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。 実験から…

yukicoder 661, 662, 663, 664, 665

最近いろんな作業を Rust で書いてるんですが、Rust やってると Haskell が書きたくなってくる。664はまだです。 661 ハローキティはりんご3個分 import Control.Monad main = getLine >> getContents >>= mapM_ (putStrLn . solve . read) . lines solve n …

SRM 729 Med. FrogSquare

問題概要 n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。 誤解法 四隅だけ使えばよく,到達でき…

ランダムに生成した行列は高確率で正則

$\mathbb{F}_p ^{2 \times 2}$ の行列をランダムに生成すると、高確率で正則になる。$\mathbb{F}_p ^{2 \times 2}$ のうち、正則なものは $(p^2-1)(p^2-p)$ 個ある(解析は付録に書いておく)。そのため、ランダムに生成した行列が正則になる確率は\begin{eq…

状態がループするゲームの解析(後退解析)

状態がループするゲームは、DAG ではないため動的計画法が使えない。代わりに 後退解析 というテクニックを用いる。次のゲームを考えよう。n 頂点 m 辺の有向グラフが与えられる。最初、頂点 s に駒が置かれている。プレイヤーは駒を隣接頂点に動かすことが…

ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_bこの解説では、座標を(横,縦)で表している。$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。 $(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である…

CF #458 E. Palindromes in a Tree

重心を求めるコードが間違っていたので修正しました(sz[v] >= x / 2ではなくsz[v] > x / 2が正しい)。計算量に影響はないです。2018-01-22 21:25http://codeforces.com/contest/914/problem/E重心分解による分割統治法で解く。重心を c としたとき、回文パ…

CF #458 G. Sum the Fibonacci

AND, OR, XOR 畳み込みを使う。ANDは分割統治、ORは高速ゼータ変換と高速メビウス変換、XORは高速アダマール変換を使うことで処理できる。n=2^17 としたとき、ANDがO(n log n)、ORがO(n log^2 n)、XORがO(n log n)になっている。OR も O(n log n) で行けるの…

根が頻繁に変わる木で親を求める

根が のとき頂点 の親を で求めるコード。以下の場合分けによるアルゴリズム。 $r$ が $u$ の子孫だった場合、$r$ を $u$ にぶつからない限界まで持ち上げる。 それ以外の場合、根が頂点 0 だった場合の親をそのまま返す。 // Verified at http://codeforces…