2023.10.22 problem solving notes

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$ 가 단조증가 한다는 것으로 정의한다.

두 수열 $A, B$ 가 다 convex하면 어떨까?

• max conv: 가능한 최소 i/j만 해보면 되어서 간단히 $O(n+m)$ 에 풀 수 있다.
• min conv: minkowski sum을 구하면 merge sort와 비슷하게 $O(n+m)$ 에 풀 수 있다.

한 수열만 convex할 때는 어떨까?

• min conv: $f(i+j)$ 를 답이 최소가 될 때 골랐던 $j$라고 하자. ($i$가 아님) $f(x) \leq f(x+1)$ 이 성립함을 수열의 볼록성으로 보일 수 있다. 고로 분할 정복 최적화를 사용하여 $O(n \log n)$ 에 해결할 수 있고, 동일하게 SMAWK를 사용하여 $O(n)$ 에 해결할 수 있다. (코드: https://judge.yosupo.jp/submission/165397)
• max conv: $n = m$이라고 가정하고, $f(0), \ldots, f(n)$ 만 일단 구하자. $b_j$ 를 골랐을 때의 답을 함수처럼 두면, 이 함수는 $b_{j-1}$ 과 비교해서 교점이 단 하나 존재하고, $j$가 클 수록 처음에 주는 효용이 크다. 교점이 하나밖에 없기 때문에 monotone queue optimization처럼 이분탐색으로 교점을 찾고 CHT하듯이 하면 된다. $f(n), \ldots, f(2n)$은 $a^\prime[i] = a[n-i], b^\prime[i] = b[n-i]$ 로 두고 동일하게 하면 된다. 사실 $n\ge m$이면 이걸로 이미 충분하다. $n<m$이면, b를 $\frac{m}{n}$ 개 구간으로 나눈 후 위 알고리즘을 그만큼 반복하자. (코드: https://judge.yosupo.jp/submission/249246)

위 알고리즘을 사용하여 냅색을 최적화 할 수 있다. 이득이 v이고 비용이 c인 물건이 N개 있는데 v <= D 라고 하자. 그냥 하면 N^2 D 시간이 걸린다. 각 비용마다 전이를 몰아서 하면, f(x) = f(x - kc) + [이득 v인 물건 k개 최소 비용] 과 같이 전이 식이 나온다. f(x - kc) 는 모르겠지만, 뒤에 것은 convex고, min conv로 ND에 해결할 수 있다.

연습 문제:

• *https://www.acmicpc.net/problem/13058
• https://judge.yosupo.jp/problem/min_plus_convolution_convex_convex
• https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
• 2023 ICPC 서울 리저널 예선 J

Probabilistic Arguments

$n$ 개의 정점을 가지며 평균 차수가 $d (\geq 1)$ 인 그래프는 항상 $\frac{n}{2d}$ 이상의 크기를 가지는 독립 집합을 가진다. 이 사실을 증명해 보자.

• 어떠한 확률 $p$ 로 $n$ 개의 정점들을 sample하자. 그렇다면 샘플링된 정점 수의 기댓값은 $np$, 간선 수의 기댓값은 $\frac{ndp^2}{2}$ 이다. 고로, $V - E$ 의 기댓값은 $np - \frac{ndp^2}{2}$ 이다.
• 기댓값이 저렇다는 것은, 그 이상의 크기를 가지는 실제 집합이 존재한다는 것이다. 이 집합을 고르자. 이제 각 간선에 대해서 간선의 양 끝점 중 하나를 랜덤하게 지우자 (이미 지워졌으면 패스). 이 과정을 하면 남는 정점들은 모두 독립 집합을 이루며 그 크기가 최소 $V - E$ 이다. 이 수는 $np - \frac{ndp^2}{2}$ 이상이다.
• 고로 모든 $0 \le p \le 1$ 에 대해 $np - \frac{ndp^2}{2}$ 이상의 크기를 가지는 독립 집합이 존재한다. 이는 $\frac{nd}{2}p(\frac{2}{d} - p)$ 이니, $p = \frac{1}{d}$ 일 때 최대화되고, 그 때의 값은 $\frac{n}{2d}$ 이다.

다른 예시는 https://rkm0959.tistory.com/47 에 있는 문제이다.

• distinct cycle로 이루어진 그래프의 간선 수에 상한을 찾는 식으로 하자.
• distinct cycle들을 높은 확률로 다 걸러주는 적절한 "체" 를 둔 다음에 남은 사이클 개수 + "체" 의 크기가 작음을 보이는 방식으로 진행한다.
• 각 간선을 $p$ 의 확률로 random sample하자. 체의 크기는 $mp$ 이다.
• 남은 사이클의 개수는 몇 개일까? 길이 $i$ 의 사이클이 선택되지 않을 확률은 $(1-p)^i$ 이다. 사이클의 크기는 $3$ 이상 $N$ 이하이니 남은 사이클 수의 기댓값은 $(1-p)^3 + (1-p)^4 + \ldots + (1-p)^N$ 이하, 즉 $\frac{1}{p}(1-p)^3$ 이하이다.
• (트리엣지 수) + (체 크기) + (백엣지 수) = m 이고, 트리엣지수 <= n-1, 벡엣지수 <= 사이클수, 고로 임의의 체에 대해. m <= n - 1 + 체크기 + 사이클수
• $p$ 를 고정하면 체의 크기와 사이클의 수를 합해서 $mp + 1/p(1-p)^3$ 이하인 체가 존재한다.
• 고로 $m \le n - 1 + mp + \frac{1}{p} (1-p)^3$ 이다. $p = \frac{1}{\sqrt m}$ 으로 두고 이차방정식을 풀면 된다.

rkm0959 블로그에 있는 예시 중 Low Diameter Decomposition에 대해서 하나 더 알아보고 가자.

• $B_r$을 $dist_G(v,w) \le r$인 정점 $w$의 집합이라 하고, $E(B_r)$ 을 $B_r$ 내부에 존재하는 간선의 개수라고 하자
• $E(B_r) > (1 + \delta) E(B_{r-1})$ 이 모든 $r$에 성립하려면 diameter가 $\log M / \delta$ 여야 함. 고로 그 경우는 종료
• 아니면 $E(B_r) \leq (1 + \delta) E(B_{r-1})$ 인 $r \le \log N / \delta$ 가 존재함. 그러면 $E(B_r) - E(B_{r-1})$ 을 그래프에서 제거하자. 이건 최대 $\delta E(B_{r-1})$ 임. 고로 남긴 connected component 크기의 $\delta$ 배만큼 지웠음
• 이제 이걸 처리 되지 않은 connected component에 대해 계속 반복하면 됨.
• 결론적으로 $\sqrt M$ 개의 간선을 제거하여, 남은 connected component의 diameter가 전부 $\sqrt M \log N$이 되게 할 수 있음. 그래프의 모든 cycle이 distinct하니 각 connected component의 백엣지 개수 합은 $\sqrt M \log N$ 개여야 할 것.