BOJ 19043 Balance

https://www.acmicpc.net/problem/19043

학교에서 볼록최적화입문을 듣는데, 이걸로 풀 수 있는 문제들이 있어서 풀어보는 중이다. 이 문제는 알고리즘 문제랑 duality 개념이 잘 섞여있는 느낌이 들어서 재밌었다.

---

1.

먼저 문제에서 주어진 balanced의 조건인 \(1\le i,j<n\)에 대해서 \(A[i][j]+A[i+1][j+1]=A[i+1][j]+A[i][j+1]\)를 해석해야 한다.

이 조건은 Monge array의 조건의 equation 형태이다. 따라서 \(1\le i<k\le n,~1\le j<l\le n\)에 대해서 \(A[i][j]+A[k][l]=A[i][l]+A[k][j]\)이다 (https://en.wikipedia.org/wiki/Monge_array).

그리고 이 조건을 만족하면 \(A\)의 원소는 \(A[i][j]=x_i+y_j\) 형태라는 성질을 알 수 있다:

• 주어진 조건을 \(A[i][j]-A[i][l]=A[k][j]-A[k][l]\)로 쓸 수 있다.
• 고정된 \(i,k\)에 대해서 \(j,l\)을 임의로 옮긴다고 생각해보면, \(i\)행 안의 모든 원소쌍의 차와 \(k\)행의 모든 원소쌍의 차가 같다는 의미이다.
• 따라서 모든 행에 대해서 이 원소쌍의 차가 같다는 의미이다.
• 열에 대해서도 마찬가지이고, 이러한 조건을 만족하려면 \(A[i][j]=x_i+y_j\) 형태여야만 한다.

이제 보석상 (https://www.acmicpc.net/problem/1281) 문제와 거의 같다.

2.

balnced인 \(B[i][j]=x_i+y_j\)이므로, \(x_i+y_j\ge A[i][j]\)를 만족하는 \((x,y)\) 중에서 \(\sum_{i=1}^n\sum_{i=1}^n(x_i+y_j)\)가 최소인 쌍을 찾으면 된다. 편의상 \(\sum_{i=1}^nx_i+\sum_{j=1}^ny_j\)를 최소화한다고 생각하자 (\(n\)배 차이).

$$ \begin{align*} &\text{minimize}&&\sum_{i=1}^nx_i+\sum_{j=1}^ny_j\\ &\text{subject to}&& x_i+y_j\ge A_{ij},~i,j=1,\cdots,n \end{align*} $$

이 LP의 Lagrangian은

$$ L(x,y,\Lambda)=\textbf{1}^Tx+\textbf{1}^Ty+\sum_{i=1}^n\sum_{j=1}^n\Lambda_{ij}\left(A_{ij}-(x_i+y_j)\right) $$

이다. 이제 dual problem은

$$ \begin{align*} &\text{maximize}&&\sum_{i=1}^n\sum_{j=1}^n\Lambda_{ij}A_{ij}\\ &\text{subject to}&&\sum_{j=1}^n\Lambda_{ij}=1,~i=1,\cdots,n\\ &&&\sum_{i=1}^n\Lambda_{ij}=1,~j=1,\cdots,n\\ &&&\Lambda_{ij}\ge0,~i,j=1,\cdots,n \end{align*} $$

이다. 그리고 이 문제는 \((i,j)\)의 매칭 비용이 \(A_{ij}\)인 이분매칭의 최대비용을 구하는 문제와 같다. 따라서 MCMF로 풀 수 있다.

이제 dual solution인 \(\Lambda^*\)를 통해서 \(x^*,y^*\)를 찾아야 한다.

3.

LP이기 때문에 KKT condition을 만족하는 \((x,y,\Lambda)\)를 찾으면 optimal solution이다. 일단 \(\Lambda\)는 \(\Lambda^*\)를 쓴다고 생각했을 때, 다시 Lagrangian을 보면

$$ L(x,y,\Lambda)=\textbf{1}^Tx+\textbf{1}^Ty+\sum_{i=1}^n\sum_{j=1}^n\Lambda^*_{ij}\left(A_{ij}-(x_i+y_j)\right) $$

여기서 모든 \((i,j)\)가 primal problem의 constraint인 \(x_i+y_j\ge A_{ij}\)를 만족하고, \(\Lambda^*_{ij}=1\)인 \((i,j)\), 즉 매칭된 \((i,j)\)에 대해서는 \(x_i+y_j=A_{ij}\)인 \((x,y)\)를 찾으면 optimal solution이 된다. 사실 이 결론은 KKT condition을 몰라도 당연하다.

여기까지 와서도 쉽지 않았다.

우선 \((i,j)\)가 매칭된 쌍일 때, 어떤 \(k\)에 대해서 \(x_k+y_j\ge A_{kj}\)라는 식을 변형할 수 있다. \(y_j=A_{ij}-x_i\)를 대입하면, \(x_k\ge x_i+A_{kj}-A_{ij}\)이다.

이렇게 얻은 \(n^2\)개의 inequality를 통해서 조건을 만족하는 최소한의 \(x\)를 찾는다고 생각했을 때, 각각의 inequality를 \(x_k\leftarrow\max(x_k,x_i+A_{kj}-A_{ij})\)의 연산으로 사용한다.

이 연산을 \(n^2\)개 전부 해주면, 최소한 하나의 변하지 않는 \(x_k\)값이 생긴다. 따라서 이 작업을 \(n\)번 해주면 모든 inequality를 만족하는 \(x\)가 구해진다. \(x\)가 정해졌으니 \(y\)도 정해진다.