Introduction An st-ordering (or bipolar odering) of a simple undirected graph is $G = (V, E)$ is a specific permutation $l$ of vertices, where any permutation $l$ induces a natural partial order on vertices $u < v \iff l(u) < l(v) \text{ and } uv \in E$. $l$ is called to be an st-ordering if and only if for a given pair of vertices $(s, t)$, $s$ (resp. $t$) is the unique minimal (resp....
Intro Definition. Given $n$ items labeled by $[n]$, and item $i$ has value $v_{i}$ and cost $c_{i}$, we define minimum knapsack problem as following optimization problem - integer programming in fact. $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i} \\ \text{s.t.}\quad& \sum_{i} v_{i}x_{i} \ge D \\ & x_{i} \in \set{0, 1} \end{aligned} $$ where $D$ is given desire on value. We can devise a naive LP relaxation for this: $$ \begin{aligned} \text{minimize}\quad& \sum_{i} c_{i}x_{i}\\ \text{s....
수직선상에 깃발 $N$개를 놓되, $i$번째 깃발은 $x_i$ 또는 $y_i$에 놓아야 한다. 이 때 깃발들 사이의 최소 거리의 최댓값을 구하는 문제이다. 문제 링크 Solution sketch 일단 파라메트릭 + 2-SAT을 해야 한다는 것 까지는 자명한 관찰이다. 즉, “가장 가까이 있는 깃발이 $d$ 이상 떨어져 있게 할 수 있는가?”에 관한 문제를 풀자. 그런데 2-SAT에 사용할 그래프 에지를 단순하게 만들면 $O(N^2)$개가 된다. Idea 1. 2-SAT Segment Tree 편의상 $x$좌표들을 정렬된 순서대로 $p_{1}, p_{2}, \cdots, $라 두자....
Grundy Number는 PS에서 굉장히 자주 쓰이는 데 비해 그 증명이나 수학적 배경이 잘 알려져 있지 않다. 앞으로 일련의 포스팅에서는 Sprague-Grundy Theorem에 대해 공부한 것을 PS 스타일로 정리하려 한다. 그 중에서 이 글은 Grundy Number의 정의와 Sprague-Grundy theorem의 증명에 대해 다룬다. Nim-Game의 필승 전략에 대한 사전 지식이 필요하며, 문제풀이에 최적화된 글이기 때문에 statement가 실제 theorem의 내용과는 다소 차이가 있다. References sirkingnightingfail, “A Blog on Sprague-Grundy Theorem” Wikipedia: Sprague-Grundy theorem Definition of Game “게임”은 상당히 광범위한 용어이지만, Sprague-Grundy theorem의 영향 아래 있는 “Game”은 다음의 조건을 만족하는 일종의 state collection을 말한다....
rkm0959, jhhope1이랑 진행한 문제풀이의 간략한 풀이. 스포일러에 주의하자. BOJ 15313. 정과프 해적단 $[l, r]$ 값이 없는 문제는 좌표압축 + 세그먼트 트리를 이용한 dp로 $O(n\log n)$에 해결할 수 있다. 이 때 $l$이 증가할수록 조건을 만족하기 위해 필요한 최소의 $r$도 증가하므로 inchworm을 얹어주면 $O(n^{2}\log n)$이 된다. BOJ 15504. 프로그래밍 대결 제일 실력이 높은 선수를 제외하고, 각 선수마다 ‘자신을 이기는 선수’를 정해주면 스패닝 트리가 유일하게 결정된다. 해당 작업을 mcmf로 모델링하면 $O(n^{4})$. 늘 그렇듯 플로우 문제에서 시간복잡도는 아무 의미 없다....