https://dl.acm.org/doi/pdf/10.5555/982792.982916 Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동일하다. 아이디어는, $G^*$ 에서 적당한 사이클 $C$를 찾은 다음, $C$의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 $C$의 안과 밖을 오가는 사이클을 찾는 것이다. 분할 정복이 성립하려면 일단 $C$가 $G^*$ 의 Face들을 공평하게 쪼개야 할 것이다. 이런 $C$는 $O(n)$ 시간에 찾을 수 있다. $G^*$ 의 모든 Face를 대각선에 $\infty$ 가중치 간선 넣고 대충 triangulate하자. 다음, $G^*$ 에서 아무 정점을 잡고, sho..
대충 이 노트 의 끝자락에서 한 얘기를 정리했다. 그래프가 2-edge-connected 라고 가정하자. (그렇지 않다고 하더라도 코드가 크게 바뀌지 않는다) 알고리즘은 재귀적이다. 그래프 $G$ 의 DFS 트리에 대해서, 특정 서브트리의 노드를 모두 3-connected-component로 바꿔주는 알고리즘이 존재하고, 이 알고리즘을 bottom-up 으로 호출하면서 "서브트리의 답을 합쳐주면" 된다. 2-connected 인 경우를 예시로 생각해 보자. 서브트리를 컴포넌트로 분할하는 알고리즘이 있다면, bottom-up 알고리즘은 절선으로 연결되어 있지 않으며 루트를 포함하는 컴포넌트들을 가져온 후 이들을 합쳐주면 된다. 3-connected 의 경우에는 컴포넌트 하나만 가져올 수는 없으나, 대신 D..
https://arxiv.org/pdf/2211.09606.pdf 생각보다 내용이 많이 쉬워서 살짝 날먹이라고도 생각했다. 일단 핵심 내용은 다음과 같은 알고리즘의 존재성이다: $s, t$ flow가 $T$ 이하일때까지 $s, t$ flow를 incremental하게 관리하는 $O(Tm)$ 알고리즘이 존재한다. 일단 이 알고리즘에 대해서 논의하기 전에, 이러한 알고리즘이 존재하면 어떻게 전체 문제를 해결할 수 있는지 살펴보자. 플로우의 값이 $T$ 이하일 때까지는 $O(Tm)$ 알고리즘을 돌린다. 플로우의 값이 $T$ 를 넘어갔을 때는, 일단 플로우의 값이 $T$ 라고 하고 계속 간선 삽입 쿼리를 받자. 플로우의 값이 $T (1 + \epsilon)$ 을 넘어가면 위 값이 틀리게 된다. 이것이 일어나려면..
Min-plus convolution 두 수열 $A = [a_0, a_1, ..., a_n]$, $B = [b_0, b_1,..., b_m]$ 이 있을 때 $c_k = \min_{k = i + j}(a_i + b_j)$ 를 구하는 것을 min-plus convolution이라고 한다. 저걸 $\max$ 로 바꾸면 max-plus convolution이다. min plus convolution은 3sum이나 apsp에서 오는 reduction은 없지만, 아직 subquadratic algorithm이 알려지지는 않은 상태 (cite: https://browse.arxiv.org/pdf/1702.07669.pdf). 수열이 convex하다는 것을, $a_{i+1} - a_i$ 가 단조증가 한다는 것으로 정의..
IOI 2023 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 박상훈, 43 / 60 / 65.5 / 31 / 100 / 54, 353.5점, 22등 (금메달) 이동현, 52 / 70 / 65.5 / 31 / 100 / 16, 334.5점, 28등 (금메달) 이성호, 43 / 40 / 61 / 23 / 65 / 35, 267점, 58등 (은메달) 반딧불, 43 / 60 / 65.5 / 14 / 65 / 16, 263.5점, 62등 (은메달) 금메달 2개, 은메달 2개로 평균 이상의 성적을 거두었으며, 작년과도 동일한 성적이다. 축하합니다! Day 1은 전례가 없이 어려웠는데, Day 2도 만만치 않게 어려운 문제들이 나왔다. 2018 Day 2와 유사한 결과가 나왔으니, 전례는 ..
(9/5 23:27 - 다 썼습니다) IOI 2023 Day 1 대회가 종료되었다. 올해 대회의 개최지는 헝가리로, 한국 팀은 2019년 이후 처음으로 현지에서 오프라인으로 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 이동현, 52 / 70 / 65.5, 187.5점, 29등 반딧불, 43 / 60 / 65.5, 168.5점, 33등 박상훈, 43 / 60 / 65.5, 168.5점, 33등 이성호, 43 / 40 / 61, 144점, 56등 모든 학생들의 성적이 금메달 / 은메달의 경계선에서 멀지 않아서 Day 2의 결과가 매우 중요할 것으로 보인다. 한국 학생들은 매년 Day 2 결과가 더 좋은 편이다. Day 2에서 ..
Algorithmic Engagements 2021. Koszulki 수열을 역순으로 정렬한 후 값이 $a_k$ 이상인 수를 출력하면 됩니다. POI 2019/2020. Najmniejsza wspólna wielokrotność 최소공배수가 $R - L$ 에 대해 지수적으로 커져서 탐색해야 할 쌍이 많지 않다는 사실을 사용합니다. $R - L = 1$ 인 경우, 최소공배수는 그냥 두 수의 곱입니다. $X(X+1) = M$ 을 만족하는 $X$ 가 존재한다면, $X, X + 1$ 을 출력하면 됩니다. 이 경우는 따로 처리합니다. 이차 방정식을 풀거나 이분 탐색을 하시면 됩니다. $R - L \geq 2$ 인 경우, 최소공배수는 적어도 $L(L+1)(L+2) / 2$ 이상입니다. 고로, $L \leq 2 \..
2023년 정보화진흥원 역량강화 교육 내용을 바탕으로 작성합니다. AC로 검증 못한 풀이들이 있어 주의를 요합니다. 2차 교육 B: L과 R의 중간 지점을 기준으로, 왼쪽에 있다면 R+1에 갈 필요가 없고, 오른쪽에 있다면 L-1에 갈 필요가 없다. 따라서, L과 R 중 하나를 고려할 필요가 없다. L을 고려하지 않고 문제를 해결하고, 반대의 경우는 대칭적으로 해결한다. R이 존재하지 않을 때 한 사람이 최대로 이동하는 거리 및 그 때의 총 이동 거리를 전처리해 두면, 사람이 있는 곳과 R이 주어졌을 때의 cost를 O(1)에 구할 수 있다. 이 때, 이 cost는 monge function이고, 2023 선발고사에 나왔던 “팀 만들기”의 60점 풀이를 그대로 사용하면 해결할 수 있다. D: $S < X..
그냥 아카이빙 목적으로 짧게 씁니다. 현대모비스 본선 대회 본인은 2021년 대회에서 8등인지 9등인지 했고, 2022년 대회에서 예선 탈락을 해서, 2023년 대회 참가가 가능했다. 1번을 열었는데 딱 봐도 따져야 할게 많아 보여서 힘들어 보였다. 따져야 할 걸 안 따지는 풀이를 짜니 10.2/15점이 나왔다. 일단 뒤로 넘어간 다음에, 뒤쪽 문제에서 주는 점수 기댓값이 4.8 미만일 때 돌아오기로 했다. 2번 뭔가 잘 안 읽혀서 뇌절하다가 대충 간선 하나 빼고 dag 경로 없는지 체크? 로 환원했다. 도미네이터 트리로 "풀 수는 있다" 는 것을 알았다. 더 생각해서 간단하게 만들 수도 있겠지만, 그냥 짤만해 보여서 도미네이터 트리를 짜기로 했다. 일반 그래프의 도미네이터 트리는 굉장히 테크니컬하지만,..
많은 일반적인 알고리즘은 하나의 프로세서에서 작동함을 가정하지만, 현실의 계산에서는 컴퓨팅 기계가 하나의 프로세서가 아닌 여러 프로세서를 사용할 수도 있다. Parallel Algorithm의 경우는 효율성을 위해서 여러 개의 프로세서를 두고 동시에 중앙적으로 컨트롤하지만, 가끔은 여러 프로세서를 두는 것이 단순 효율성 때문이 아니라 실제적인 시공간적 제약에 의해서일 수도 있다. 예를 들어, 세계 각지에서 정보를 모으는 컴퓨터가 있고, 이 정보들을 한데 모아서 특정한 계산을 하고 싶은데, 정보들이 하나로 모으기에는 너무 크거나, 아니면 장거리 네트워크를 사용하는 것이 아주 비효율적인 상황들이 있을 것이다. Distributed Algorithm이란 어떠한 알고리즘이 하나의 프로세서가 아니라 여러 분할된 ..
- Total
- Today
- Yesterday