대회 링크

http://codeforces.com/contest/22

해설

A. Second Order Statistics

간단한 정렬 문제이므로 생략

B. Bargaining Table

O( N^{2} M^{2} ) $O( N^{2} M^{2} )$ 해법

• 모든 (i,j)$(i,j)$에 대해 top-left가 (0,0)$(0,0)$이고 bottom-right가 (i,j)$(i,j)$인 사각형 구간의 누적합(1의 개수)를 미리 계산한 테이블을 가지고 있으면 임의의 top-left가 (a,b)$(a,b)$, bottom-right가 (c,d)$(c,d)$인 구간의 1의 개수를 O(1)$O(1)$에 구할 수 있다.
• 이를 이용하여 모든 구간이 0인 구간 중 최대가 되는 사각형 구간이 답이 된다. 이 때 둘레는 (height+width) * 2 $(height+width) * 2$로 계산 가능하다.

O( N^{3} M^{2} )$O( N^{3} M^{2} )$ 해법

• 우선 문제 조건이 25^5$25^5$기 때문에 가능한 해법
• 각 행에 대한 누적합을 구하고 지정한 사각형 구간에 대해 O(N)$O(N)$으로 스캔하여 0만 존재하는 구간인지 확인하여 후보 구간을 선별한다.

• 선별된 구간 중 둘레가 최대가 되는 구간이 답이 된다.

• 소스코드(hyunhwan작성)

C. System Administrator

• 문제가 성립하기 위해서는 간선의 개수가 적어도 n - 1 개 이상이어야 합니다. 또한 간선의 개수는 최대 nC2개 입니다.
• 문제를 만족하면서 최대로 존재할수 있는 간선의 개수는 (n-1)C2 입니다. 이는 다음과 같이 증명할수 있습니다.

1. v서버가 fail 되었을때 전체 시스템이 망가지기 위해서는 v서버가 그래프에서 삭제되었을때 서로 다른 k 개의 그래프로 나뉘어져야합니다.
2. k개의 그래프의 각 노드의 수를 n1, n2, ... nk 라고 가정하면 최대로 가능한 간선의 개수는 n1C2 + n2C2 + n3C2 + ... nkC2 입니다. 또한 n1 + n2 + ... nk = n - 1 입니다.
3. n1C2 + n2C2 + ... nkC2 = ((n1 ^ 2 + n2 ^ 2 + ... nk^2) - (n1 + n2 + ... nk)) / 2 이며 이는 (n1 + n2 + ... nk) * (n1 + n2 + ... nk - 1) / 2 = ((n1 + n2 + ... nk) ^ 2 - (n1 + n2 + ... nk)) / 2 보다 작습니다. (n1 + n2 + ... nk) * (n1 + n2 + ... nk - 1) / 2 = (n-1)C2 입니다.

• 따라서 그래프가 최대의 간선을 갖도록 세팅하려면 v 노드와 v와 연결되어있으면서 v 가 아닌 한 노드를 제외한 나머지 노드가 모두 연결되어있도록 구성하면 됩니다.
• 따라서 다음과 같은 방법으로 m 개의 간선을 채워나갑니다.

1. v 와 연결되는 임의의 다른 노드 p 간선 생성
2. p 를 제외한 나머지 노드간의 간선 생성. 만일 m개 간선이면 종료
3. p를 제외한 나머지 노드중 중복되지않은 간선을 m 개 생성될때까지 생성

• 소스코드(kws4679작성)

D. Segments

O(N^{2})$O(N^{2})$ 해법

• 좌표의 순서대로 (왼쪽부터 오른쪽으로) 이동하며 못을 박는다 하자. 이 경우에 이동시 못을 박지 않고 지나친 segment가 존재하면 올바른 답이 아니기 때문에, 무조건 박아야 한다는 사실을 알 수 있다. 또한 이 전략을 취할 때 한 segment에 대해 못을 박을 경우 맨 오른쪽에 못을 박는것이 좋다는 사실 또한 알 수 있다. 따라서 다음의 알고리즘을 통해 이 문제를 해결 할 수 있다.

1. O(N)$O(N)$에 현재 못박지 않은 segment 중 오른쪽 끝 좌표가 최소인 segment를 찾아 그 부분에 못을 박는다.
2. 이때 O(N)$O(N)$의 연산을 통해 이 부분에 포함되는 segment역시 못을 박았다 간주한다.
3. 앞의 과정을 모든 segment에 대해 처리했을 때 종료한다.

• 소스코드(hyunhwan작성)

E. Scheme