상당히 많은 사람이 easy/med/hard를 모두 풀었습니다. 그레이가 순위권 찍은게 눈에 띄네요. 사실 Qualification Round 3 자체가 한번 unrated match가 되어서 그 매치 때 2, 3등을 기록했던 한국인 두 명만 초안습이 됐습니다. 그래도 저는 8등이라도 했지 .. 지못미 ㅠ_ㅠ

Easy (250 pts.)

• 문제 설명 시키는대로 NxN array를 채우시오. 먼저 -1로 initialize하고 (0, 0)에 1을 써넣는다. 어떤 한 칸에 값을 써 넣은 다음에는 항상 아래로 a칸, 오른쪽으로 b칸 이동하여 2부터의 값을 차례대로 채운다. 만일 이미 -1이 아닌 값이 들어있다면 그 위치에서부터 아래로 c칸 오른쪽으로 d칸 이동해 본다. 그 칸에도 이미 -1이 아닌 값이 들어있다면 종료한다. 채워진 array를 출력하라. 단, array의 모양은 toroidal하다고 가정한다. (즉, 행/열 방향으로 cyclic하다) # 1 <= n <= 10 [spoiler="풀이 보기"]매우 심플한 문제입니다. 그냥 정말 시키는 대로 하면 되겠습니다. a, b, c, d가 음수일 수도 있었다면 그나마 조금 더 재미있는 문제가 되었을 지도 모르겠습니다. Failed solution도 거의 없었습니다. 재미있는 챌린지로는
  • 두 글자에 맞춰 char 타입으로 문자를 하나씩 출력하다가 100을 출력할 때 ":0" 출력 (이런 사람이 다섯이나 있더군요 ...)
  • 좀 더 나아가서 한 글자에 맞춰 char 타입으로 출력 (이런 사람은 둘이나..)
  • 맨 뒤에 공백 출력 또는 공백 없이 출력 (캐안습 ㅠㅠ....)
  • array의 크기를 5x5로 잡았다가 패망 [/spoiler]

Medium (500 pts.)

• 문제 설명 N개의 방과 그들을 연결하는 케이블들이 있다. 케이블들의 정보는 NxN 행렬의 형태로 주어지며, element (i, j)는 방 i과 방 j 사이의 케이블의 길이를 나타낸다. (구체적으로, '0'은 케이블이 없음을, 'a-z'는 1-26, 'A-Z'는 27-52) 물론 (i, j)와 (j, i)가 둘 다 케이블이 있다면 이중으로 연결된 것이다. 자기 자신과 연결된 쓸모없는 케이블이 있을 수도 있다. 방들을 모두 서로 연결된 상태로 유지하면서 최대한 쓸데없는 케이블을 많이 날리고 싶다. 얼마만큼을 없앨 수 있는가? 단, 초기에 연결되지 않았다면 -1을 리턴한다. # 1 <= N <= 50 [spoiler="풀이 보기"]눈에 뻔한 MST(minimum [cost] spanning tree) 문제입니다. prim 또는 kruskal 중에 구현이 빠를 것 같은 것을 골라내어 사용하면 됩니다. 재미있는 챌린지로는
• N = 1인 경우 (연결되지 않았다며 -1을 내는 등) 오답을 내는 솔루션들
• 엣지를 하나씩 제거해 보며 그래프가 연결된 그래프인지 판단하되, 그들 중 가장 가중치가 큰 엣지만 반복해서 제거함으로써 O(N^6) time complexity를 내는 솔루션들 이외에는 역시 traditional한 문제다 보니 솔루션 자체의 공통적인 결함보다는 사소한 부분의 실수를 잡아내는 것이 주효합니다. [/spoiler]

Hard (1000 pts.)

• 문제 설명 0 또는 1로 채워진 RxC matrix가 있다. 이 matrix의 임의의 한 열 또는 행을 잡아서 그 원소를 모두 반전하는 것을 1회의 연산이라고 하자. matrix의 모든 행과 열이 짝수개의 1을 갖도록 만들려면 몇 회의 연산이 최소 필요하겠는가? 불가능하면 -1을 되돌려라. # 1 <= R, C <= 49, R*C \in odd

[spoiler="풀이 보기"]사람마다 아이디어를 표현하는 방식이 조금씩 다른 문제였습니다. 제 풀이를 설명하죠.
이런 류의 boolean(modular) matrix operation 을 풀 때 주로 사용하는 방법으로 연립일차합동식을 나열하는 것입니다. 만일 연립합동식을 나열했을때 가우스 소거법으로 풀릴 수 있는 형태의 문제라면 쌩큐죠. 이 문제에서도 나열해 봅시다.
r_k는 k번째 행의 1의 수가 현재 홀수개라면 1, 짝수개라면 0입니다. c_k도 열에 대해 비슷하게 정의합시다.
R_k는 k번째 행을 잡아서 반전시킬 것인지(1) 말 것인지(0)를 결정하는 변수입니다. C_k 역시 그렇구요.
편의상 행렬의 크기를 NxM으로 바꿉시다. 그렇다면 아래와 같이 식을 얻을 수 있습니다.
R_1 + C_1 + C_2 + .. + C_M + r_1 = 0 (mod 2)
R_2 + C_1 + C_2 + .. + C_M + r_2 = 0 (mod 2)
R_3 + C_1 + C_2 + .. + C_M + r_3 = 0 (mod 2)
...
R_N + C_1 + C_2 + .. + C_M + r_N = 0 (mod 2)
C_1 + R_1 + R_2 + .. + R_N + c_1 = 0 (mod 2)
C_2 + R_1 + R_2 + .. + R_N + c_2 = 0 (mod 2)
C_3 + R_1 + R_2 + .. + R_N + c_3 = 0 (mod 2)
...
C_M + R_1 + R_2 + .. + R_N + c_M = 0 (mod 2)
이 식들을 모두 만족해야 일단 가능한 솔루션이겠죠.
식을 가만히 보니 예쁜 모양의 common term이 있습니다. (C_1 + C_2 + ... + C_M)과 (R_1 .. R_N) 이죠.
앞의 식을 X라 합시다. X를 2로 나눈 나머지는 0 혹은 1일 것입니다. 즉, 열을 뒤집는 횟수는 당연히 짝수번 또는 홀수번 뒤집게 되겠죠.
그런데 열을 구체적으로 어떻게 뒤집을 것인지 모르더라도, 짝수번 뒤집을 것인지 홀수번 뒤집을 것인지만 결정하면 저 식에 대입해 보면 R_k꼴의 변수가 모조리 결정됩니다. 즉, 행을 뒤집을지 말지는 행의 1의 개수와 전체 열바꿈의 parity만 알면 되는 것이죠.
따라서 C_1 + C_2 + ... + C_M(을 2로 나눈 나머지)가 0 또는 1이므로, 0 또는 1이라고 일단 치고 R_k 변수들을 모두 구합니다. 그리고 나면 C_k 변수들도 같은 원리로 모두 구할 수 있습니다. 따라서 전체 가능한 방법은 최대 두 개 뿐입니다.
조금 더 생각해 보면, 불가능할 때의 -1 없이 항상 두 가지의 방법이 존재함을 알 수 있습니다.
[/spoiler]