-
testlib 사용하기
개요 testlib는 Polygon에서 프로그래밍 문제를 만들기 위한 유틸리티를 한데 모아놓은 라이브러리입니다. Generator, validator, checker 및 interactor 제작에 공통적으로 사용되며, 신뢰도 높은 랜덤 함수, 안정성 있으며 정규표현식을 지원하는 문자열 파싱, Polygon 및 채점 시스템과의 상호작용 등의 다양한 기능을 갖추고 있으며 Polygon과 GitHub 페이지에서 다양한 사용 예제들도 제공해 줍니다. 문제 출제를 위한 플랫폼 - Polygon 사용하기 글에 간단한 사용 예시가 나와있습니다. 유용한 기능을 많이 갖추고 있고 코드의 주석 또한 훌륭한 반면에 testlib에 대한 별도의 문서화는 이루어지지 않았습니다....
-
Variance Reduction Algorithms and Catalyst Acceleration
서론 본 글에서는 단순히 convex function $f$를 최소화 하는 것이 아니라, 이들의 합인 $F = \frac{1}{n} \sum_{i=1}^n f_i(x)$ 를 최소화하는 알고리즘에 대해서 알아보고, 이에 Catalyst를 적용해보겠습니다. 이와 같은 형식의 함수 $F$는 Logistic Regression 등 Machine Learning에서 등장합니다. 원래는 $F$에 추가적인 “proximal function”이 있어, $F = \frac{1}{n} \sum_{i=1}^n f_i(x) + \psi(x)$ 형태를 가지나 (예를 들어 $l_1$ regularization) 여기서는 편의상 $\psi$에 대한 논의를 생략하겠습니다. 글의 순서는 대략적으로 다음과 같습니다. $F$를 최소화하는 알고리즘이 발전한 과정의 큰 흐름에 대해서...
-
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...
-
Union Find의 시간 복잡도 증명
Union Find Union Find 또는 Disjoint Set이라고 불리는 자료구조는 여러 개의 원소를 포함하고 있는 집합들을 다루는 자료구조이다. 초기에, $N$개의 원소들과 $N$개의 집합들이 만들어져 있고, 각각의 집합은 서로 다른 원소 하나씩을 가지고 있다. 이 위에 다음과 같은 두 개의 연산을 할 수 있다. Union(x, y) : 원소 x가 속한 집합과, 원소 y가 속한 집합을 합친다. Find(x) : 원소 x가 어떤 집합에 속해있는지 반환한다. 보통 x가 속해있는 집합의 대표 원소 하나를 반환한다. struct dsu { dsu() {...
-
Li Chao Tree의 Lazy Propagation
개요 리차오 트리는 직선들을 관리하는 동적 세그먼트 트리의 일종으로, Convex Hull Trick 등등에서 쓰이는 자료구조입니다. 다른 세그먼트 트리와 마찬가지로 리차오 트리에도 레이지 프로퍼게이션을 적용할 수 있지만, 이에 대해서는 잘 알려져 있지 않습니다. 이 글에서는 리차오 트리에 레이지 프로퍼게이션을 적용한 확장 연산들과 그 활용에 대해 소개합니다. 리차오 트리 좌표 범위가 $N$일 때, 기본적인 리차오 트리는 다음과 같은 연산들을 할 수 있습니다. insert(a,b) : 새로운 직선 $y=ax+b$를 삽입한다. $O(\log{N})$ get(x) : 주어진 $x$좌표에서 $y$좌표의 최솟값을 구한다. $O(\log{N})$...