-
Aeren's profile image
Aeren
January 18, 2022
Nimber
Table Of Contents Introduction Simplest Group Structure Over Ordinals Simplest Group Extension Theorems Simplest Field Structure Over Ordinal Simplest Field Extension Theorems Conclusion Introduction 안녕하세요, Aeren입니다! $\oplus$가 bitwise-xor을 나타낼 때, nim game에서 크기 $x$와 $y$인 heap 두개로 이루어진 game과 크기 $x \oplus y$인 heap 한개로 이루어진 game이 동치임은 많이 알려져 있습니다. 그 때문에, $\oplus$를 nim-addition이라 부르기도 합니다. 이번 글에서는 nim-addition및 관련 연산을 game theory가 아닌 순수한 algebra의 관점에서 바라봐 보려고 합니다. 이 글은 John Horton...
-
Aeren's profile image
Aeren
December 21, 2021
Bostan-Mori Algorithm
Table Of Contents Introduction Review of the Kitamasa’s Method Bostan-Mori Algorithm Optimization under the DFT Setting Review of DFT DFT Doubling Bostan-Mori Algorithm under the DFT Setting Benchmarking Introduction 안녕하세요, Aeren입니다! 주어진 commutative ring $R$과 어떤 positive integer $d$에 대하여 $\begin{align} a _ {i + d} = \sum _ {j = 0} ^ {d - 1} c _ j \cdot a _ {i + j} \end{align}$ 꼴의 recurrence relation으로 표현되는 sequence $a : \mathbb{Z} _...
-
Aeren's profile image
Aeren
November 22, 2021
Operations on Set Power Series
Table Of Contents Introduction Set Power Series Addition Or Convolution Subset Convolution Composition of Set Power Series Exponential General Case Example: ARC105 F Introduction 안녕하세요, Aeren입니다! 이번 글에서는 set power series와 그와 관련된 연산들을 소개하고, combinatorial problem에서 어떻게 활용될 수 있는지 간단하게 소개하겠습니다. Set Power Series 어떤 set $G = \lbrace g _ 0,g _ 1,\cdots ,g _ {N-1} \rbrace$와 commutative ring $R$이 주어질 때, 함수 $p:\mathcal{P}(G) \rightarrow R$를 set power series라고 부릅니다. 그리고 일반적인...
-
Aeren's profile image
Aeren
October 20, 2021
PQ Tree (Part 1)
Table Of Contents Introduction Structure of a PQ Tree Construction of a PQ Tree Operation Reduce Leaf Node P Node Q Node Implementation Introduction 안녕하세요, Aeren입니다! 이번 글은 Codeforces Global Round 15에서 알게 된 PQ tree를 소개하는 첫 번째 글입니다. 어떤 finite set $U$와 $U$의 subset들의 집합 $C$가 주어졌을 때, $U$의 permutation $P$가 permissible하다는 것은, $S$의 각 원소 $T$에 대하여, $T$의 원소들이 $P$에서 연속적으로 나타나는 것을 의미합니다. PQ tree는 주어진 constraint $C$에 대하여 모든 permissible...
-
Aeren's profile image
Aeren
August 22, 2021
Expected Complexity of Random Convex Hulls
Table Of Contents Introduction Experimental Results Notations Planar Case On Higher Dimension Summary Introduction 안녕하세요, Aeren입니다! Convex hull은 computational geometry의 가장 기본이 되는 개념 중 하나입니다. 이번 글에서는 $\mathbb{R} ^ 2$의 compact (closed and bounded와 동치입니다.) and convex subset에서 uniformly random하게 선택된 점들의 집합의 convex hull의 vertex의 갯수의 기댓값을 알아볼 것입니다. 이 글은 다음 글을 바탕으로 작성되었습니다. Experimental Results 다음은 $C$가 unit disk, unit triangle, unit square일때 100회의 sampling으로 얻어낸 convex hull의 평균 vertex 갯수입니다....
-
Aeren's profile image
Aeren
July 20, 2021
Introduction To Retroactivity
Table Of Contents Introduction Preliminaries Operations Partial Retroactivity Full Retroactivity Runtime General Retroactivity Specific Retroactivity Queue Deque Union-Find Priority-Queue Summary Introduction 안녕하세요, Aeren입니다! Persistent data structure는 어떤 data structure의 여러 상태를 저장하면서 임의의 상태로부터의 연산을 통해 도달한 새로운 상태를 관리할 수 있게 합니다. 이렇게 만들어진 상태들의 관계는 tree 구조룰 이루게 되죠. 이번 글에서 소개할 내용은 이와 대비되는 개념인 retroactive data structure입니다. Retroactive data structure에서 각 상태들의 관계는 line graph형태로 고정되있습니다. 그리고 어떤 상태가 연산을 통해...
-
Aeren's profile image
Aeren
June 21, 2021
Fast Polygon Triangulation
Table Of Contents Introduction Preliminaries Degeneracy Strict Total Order Monotone Polygon Montone Polygon Triangulation Example Polygon Triangulation Boundary Vertex Classification Sweepline Events Example Implementation Introduction 안녕하세요, Aeren입니다! Polygon triangulation은 classical한 computational geometry problem중 하나로, 어떤 simple polygon의 boundary가 counterclockwise하게 주어질 때, triangulation을 찾는 문제입니다. 이번 글에서 소개할 내용은 $N$을 polygon의 vertex 갯수라고 할 때 $O(N \log N)$시간 안에 위 문제를 해결하는 알고리즘입니다. 참고로 이 문제는 $O(N)$시간 안에 해결 가능함이 알려져 있습니다. (참조) Preliminaries Degeneracy 이...
-
Aeren's profile image
Aeren
May 20, 2021
Data Structure For Range Mode Query
Table Of Contents Introduction Hardness Result First Method Second Method Third Method Final Method Introduction 안녕하세요, Aeren입니다! Competitive programming을 해본 적 있는 분이라면 range sum query, range minimum query 등등의 다양한 range query문제를 접해보셨을 것입니다. 많은 range query problem들은 linear memory만으로 sublinear time query를 가능하게 해주는 data structure가 존재합니다. 이번 글에서는 비슷한 맥락의 range mode query 를 해결하는 linear memory data structure에 대해 알아 볼 것입니다. 이 글은 다음 논문을 바탕으로 작성되었습니다. Array 혹은 multiset...
-
Aeren's profile image
Aeren
April 20, 2021
Heavy-light Decomposition With Globally Balanced Binary Trees
Table Of Contents Prerequisite Introduction Main Idea Implementation Benchmark Prerequisite Segment tree - Tutorial on cp-algorithms Heavy-light decomposition - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 다음 문제를 생각해봅시다. Monoid $(T,+)$와 $(L,+)$, left monoid action $\ast(\ast):(L,T)\rightarrow T$, tree $G=(V,E)$와 각 node의 가중치 $W:V\rightarrow T$이 주어진다. 다음 연산들을 수행하라. $u,v\in V$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 $\sum_{w\in P}W(w)$의 값을 출력한다. $u,v\in V$와 $f\in L$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 각 $w\in...
-
Aeren's profile image
Aeren
March 23, 2021
Skew-binary Lifting
Table Of Contents Prerequisite Introduction Implementation Performance Analysis Benchmark Prerequisite Binary Lifting - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 이 글에서 소개할 내용은 skew-binary number system을 기반으로 한 skew-binary lifting입니다. 이 글은 An Applicative Random-Access Stack by Eugene W. MYERS을 기반으로 작성되었습니다. 일반적인 binary lifting과의 차이점 중 하나는 각 node $u$가 $O(\log(\textrm{depth}[u]))$ 대신 $O(1)$ 만큼의 공간을 필요로 한다는 것입니다. 표로 정리하면 다음과 같습니다. (Time) / (Additional Space Required) Operation Binary Lifting Skew-binary Lifting Add A...