대회 링크

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

• 노드에 들어가는 간선만 있는 노드를 인노드, 나가는 간선만 있는 노드를 아웃노드라고 하자
• 문제 조건상 뉴스의 흐름을 그래프로 표현하면 3가지 타입중 하나가 되는데 첫번째는 인노드가 1개이며 아웃노드가 1개 이상인 일반 그래프, 두번째는 인노드가 없고 아웃노드가 1개 이상인 사이클로 종료되는 그래프, 인노드도 없고 아웃노드도 없는 완전 사이클이다.
• 문제의 뉴스 흐름을 connected component 의 집합으로 만들면 각각의 그래프의 인노드와 다른 그래프의 아웃노드를 번갈아가면서 ( 전체 그래프가 사이클을 이루도록 ) 연결하는 것이 최적해이다.
• 만일 A 그래프의 인노드가 A 그래프의 아웃노드로 연결되는 최적해가 있다고 가정해보자. 이경우 A 그래프와 다른 임의의 그래프 B 그래프가 연결되기 위해서는 적어도 1개 이상의 간선이 필요하다. 그러나 위에서 언급한 방법의 최적해는 이미 이 간선을 포함하므로 더 나은 최적해가 존재한다.
• 따라서 다음과 같은 방식으로 해를 구한다

1. 뉴스 흐름을 그래프로 표현하고 각 그래프별로 인노드,아웃노드,사이클을 구한다. 사이클은 모든 사이클을 구할필요는 없고 사이클에 포함되는 한개의 노드만 있으면 된다.
2. 연결돼지않은 노드를 가진 임의의 그래프 2개를 선택하여 인노드와 아웃노드를 연결한다. 사이클인경우 사이클에 포함되는 노드와 아웃노드를 연결한다. 둘다 사이클인경우 사이클에 포함되는 두 노드를 연결한다.
3. 더이상 연결되지 않는 그래프가 없을때까지 반복한다.

소스코드(kws4679작성)