에디토리얼 내지는 후기를 쓰려고 하는데 워낙 오래 지난 일인데다가, 자세히 쓰면 미래에 이 문제를 연습용으로 풀 분들의 창의력을 저해하는 일이 아닌가 하는 생각이 듭니다.
그래도 다른 이야기들도 많이 있으니 어느정도 써보도록 하겠습니다.
문제명은 SubgraphIsomorphism 으로 아주 self-explanatory 합니다. 각 케이스 당 비교적 sparse한(평균 degree 4~60 정도?) 특정 프로세스에 의해서 만들어진 원본 그래프(n=1000~20000) 가 하나 주어지고, 여기서 랜덤하게 떼어낸 size가 5인 subgraph가 입력으로 들어옵니다. 그러면 원본 그래프에서의 위치를 찾아서 리턴하면 됩니다. 이 때 subgraph에 edge도 원본 그래프의 매치된 자리에서 모두 없어야 합니다. 여러 군데서 찾을 수 있으면 그 중 한 군데만 찾으면 되구요, size 5짜리 subgraph를 해결했다면 size 6짜리가 들어옵니다. 이걸 풀면 7짜리가... 이런식으로 해서 시간제한 10초 안에 subgraph match를 한 갯수가 이 케이스의 점수가 됩니다.
유키님은 이 문제가 알고리즘적으로는 상당히 어려운 문제라고 했지만, MM은 어떻게 하든지 결과만 잘 나오면 장땡 아니겠습니까. 이 문제도 다른 MM 문제와 비슷하게 일단 지르고 나서 개선시켜 나가는 방법으로 풀 수 있는 문제였습니다.
이 문제는 DFS+pruning 외에는 다른 해법을 찾기가 아주 힘든 문제입니다. 나름 Sparse graph인것도 있고 해서 괜찮은 결과를 볼 수 있었습니다. 가장 중요한 것은 특징이 있는 node/edge/area 부터 찾아 나가는 것이 pruning이 잘 된다는 것입니다. 예를 들어서, 주어진 subgraph를 degree 순서대로 내림차순 정렬을 하고 찾으면 첫 검색의 대상 node의 수가 줄어들 뿐만 아니라, 검색을 조금만 해도 connection에 대한 제한조건이 많이 생기기 때문에 평균적으로 찾아보는 depth도 줄어들 확률이 높습니다. 다른 예로는 sparse graph이니만큼 n>=3 complete graph부터 찾아보는 것도 검색을 시작할 수 있는 괜찮은 특징을 잡는 것이라 볼 수 있겠죠.
이런 식으로 코딩을 해나가다보면 대부분의 케이스의 경우 매우 빠른 속도로 찾을 수 있게 되는데, 몇몇 서브그래프에 대해서 주어진 10초를 거의 다 잡아먹게 됩니다. 그래프를 출력해가면서 이런 경우들을 그룹지어서 원인을 찾아서 해결하는 방법을 찾아야 하고, 이러한 반복적 방법론의 특징 때문에 이 문제에 투자한 시간과 최종 결과에는 굉장한 상관관계가 있었습니다. 또한 반복 한 번을 하는 것 자체가 시간을 많이 소모하는 일이었구요. Provisional score 기준으로, 2주 중에 1주일이 지났을 때는 1위가 4000점대 극초반대였지만, 최종 결과로는 16위까지가 4000점 이상이 되었습니다.
제 경우에도 문제를 해결해나가면서 점점 tricky case의 빈도는 낮아져 갔습니다. 마지막까지 결국 해결하지 못했던 경우는 4 이상 길이의 path가 존재하는 그래프였습니다. 즉 (어느정도 통통한 그래프1) - 노드 - 노드 - 노드 - 노드 - (어느정도 통통한 그래프2) 이런식으로 연결되어 있는 경우이죠. 이 경우에, 그래프1을 대략 찾고 나서 그래프2로의 경로를 찾게 되는데, 중간에 노드 하나만 연결되어 있는 경우는 가장 흔한 경우인데다가, depth가 꽤 들어가기 때문에 경우의 수가 기하급수적으로 늘어납니다. 그래프2에서 커팅이 잘 된다고 하더라도 이미 늦은 일이죠.
또한, 많이 sparse하면서 크기가 1000~2000 정도로 비교적 작은 그래프의 경우에 대해서는, 대략 100개 이상의 subgraph를 격파하고 n>=100짜리 subgraph가 입력으로 들어오기 시작하면, DFS 순서를 잘 정했다면 오히려 경우의 수가 크게 줄어들기 때문에, 대부분 빛의 속도로 찾을 수가 있습니다. 따라서 300~400 이상의 점수를 받는 경우도 생기기 시작하는데, 이 때 각 입력 케이스에 대해서 걸리는 최소 시간이 O(n^3)보다 작다면, 10초 안에 1000점을 넘어서서 이론적으로 가능한 최고 점수인 n-5점을 받는 경우도 생길 수 있습니다.
저는 이런 예제들에 대해서는 최고 점수가 600~700점 정도였는데, Psyho 등 몇몇 코더의 경우에는 이 경우를 정확히 찾아서 특별 처리를 해줌으로써 1500점 이상의 점수를 받는 일도 생겼습니다. Provisional test 50개에는 이런 예제가 없었지만 사실 이런 경우는 그리 드물지 않기 때문에, 정확히 반영되는 최종 순위에는 큰 변화가 생겼습니다.
최종 결과는 제가 7위를 기록했고, 평균 100개를 찾았습니다. (system test 1000개 결과 100273점) 원래도 1위였으면서 위에서 설명한 케이스를 잘 처리해서 독보적인 1위가 된 Psyho는 139677점으로 평균 140개를 찾았구요, 12위 커트라인으로 대역전을 성공시킨 ploh는 89129점을 기록하였습니다. 1~20위까지의 모든 프로그래머는 DFS를 사용하였네요.
Final에 갈 수 있는 R3이니만큼 경쟁도 아주 치열했습니다. 보통의 Marathon Match는 2주 내내 하는 사람은 그리 많지 않고, 상위권 코더라도 2~3일 정도의 코딩 타임을 가집니다...만 R3 최종순위 1~30위 정도까지는 첫날부터 2주간 계속 달린 것으로 보입니다. Psyho의 경우 첫날 첫 서미션부터 24시간동안 10번 서밋을 하는 괴력을 보이며 레이스를 주도했으며, ACRush는 중간에 GCJ Final을 다녀오는 시간을 제외하고는 계속 달리는 강철체력을 과시했습니다. 저는 여름휴가 간다고 6일째가 되어서야 첫 서밋을 했는데, 마감 24시간 전에 제출한 솔루션부터 커트라인을 돌파한 것으로 추정합니다.
다른 MM과 마찬가지로 빠른 development cycle과 시간 투여가 중요한 대회였습니다.
13년 전
0개의 댓글이 있습니다.
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면
온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야
합니다. 현재 문제를 푸셨습니다.
일루
안녕하세요. 어쩌다보니 R3을 통과해서 Final로 가버린 ainu7입니다.
에디토리얼 내지는 후기를 쓰려고 하는데 워낙 오래 지난 일인데다가, 자세히 쓰면 미래에 이 문제를 연습용으로 풀 분들의 창의력을 저해하는 일이 아닌가 하는 생각이 듭니다.
그래도 다른 이야기들도 많이 있으니 어느정도 써보도록 하겠습니다.
문제명은 SubgraphIsomorphism 으로 아주 self-explanatory 합니다. 각 케이스 당 비교적 sparse한(평균 degree 4~60 정도?) 특정 프로세스에 의해서 만들어진 원본 그래프(n=1000~20000) 가 하나 주어지고, 여기서 랜덤하게 떼어낸 size가 5인 subgraph가 입력으로 들어옵니다. 그러면 원본 그래프에서의 위치를 찾아서 리턴하면 됩니다. 이 때 subgraph에 edge도 원본 그래프의 매치된 자리에서 모두 없어야 합니다. 여러 군데서 찾을 수 있으면 그 중 한 군데만 찾으면 되구요, size 5짜리 subgraph를 해결했다면 size 6짜리가 들어옵니다. 이걸 풀면 7짜리가... 이런식으로 해서 시간제한 10초 안에 subgraph match를 한 갯수가 이 케이스의 점수가 됩니다.
유키님은 이 문제가 알고리즘적으로는 상당히 어려운 문제라고 했지만, MM은 어떻게 하든지 결과만 잘 나오면 장땡 아니겠습니까. 이 문제도 다른 MM 문제와 비슷하게 일단 지르고 나서 개선시켜 나가는 방법으로 풀 수 있는 문제였습니다.
이 문제는 DFS+pruning 외에는 다른 해법을 찾기가 아주 힘든 문제입니다. 나름 Sparse graph인것도 있고 해서 괜찮은 결과를 볼 수 있었습니다. 가장 중요한 것은 특징이 있는 node/edge/area 부터 찾아 나가는 것이 pruning이 잘 된다는 것입니다. 예를 들어서, 주어진 subgraph를 degree 순서대로 내림차순 정렬을 하고 찾으면 첫 검색의 대상 node의 수가 줄어들 뿐만 아니라, 검색을 조금만 해도 connection에 대한 제한조건이 많이 생기기 때문에 평균적으로 찾아보는 depth도 줄어들 확률이 높습니다. 다른 예로는 sparse graph이니만큼 n>=3 complete graph부터 찾아보는 것도 검색을 시작할 수 있는 괜찮은 특징을 잡는 것이라 볼 수 있겠죠.
이런 식으로 코딩을 해나가다보면 대부분의 케이스의 경우 매우 빠른 속도로 찾을 수 있게 되는데, 몇몇 서브그래프에 대해서 주어진 10초를 거의 다 잡아먹게 됩니다. 그래프를 출력해가면서 이런 경우들을 그룹지어서 원인을 찾아서 해결하는 방법을 찾아야 하고, 이러한 반복적 방법론의 특징 때문에 이 문제에 투자한 시간과 최종 결과에는 굉장한 상관관계가 있었습니다. 또한 반복 한 번을 하는 것 자체가 시간을 많이 소모하는 일이었구요. Provisional score 기준으로, 2주 중에 1주일이 지났을 때는 1위가 4000점대 극초반대였지만, 최종 결과로는 16위까지가 4000점 이상이 되었습니다.
제 경우에도 문제를 해결해나가면서 점점 tricky case의 빈도는 낮아져 갔습니다. 마지막까지 결국 해결하지 못했던 경우는 4 이상 길이의 path가 존재하는 그래프였습니다. 즉 (어느정도 통통한 그래프1) - 노드 - 노드 - 노드 - 노드 - (어느정도 통통한 그래프2) 이런식으로 연결되어 있는 경우이죠. 이 경우에, 그래프1을 대략 찾고 나서 그래프2로의 경로를 찾게 되는데, 중간에 노드 하나만 연결되어 있는 경우는 가장 흔한 경우인데다가, depth가 꽤 들어가기 때문에 경우의 수가 기하급수적으로 늘어납니다. 그래프2에서 커팅이 잘 된다고 하더라도 이미 늦은 일이죠.
또한, 많이 sparse하면서 크기가 1000~2000 정도로 비교적 작은 그래프의 경우에 대해서는, 대략 100개 이상의 subgraph를 격파하고 n>=100짜리 subgraph가 입력으로 들어오기 시작하면, DFS 순서를 잘 정했다면 오히려 경우의 수가 크게 줄어들기 때문에, 대부분 빛의 속도로 찾을 수가 있습니다. 따라서 300~400 이상의 점수를 받는 경우도 생기기 시작하는데, 이 때 각 입력 케이스에 대해서 걸리는 최소 시간이 O(n^3)보다 작다면, 10초 안에 1000점을 넘어서서 이론적으로 가능한 최고 점수인 n-5점을 받는 경우도 생길 수 있습니다.
저는 이런 예제들에 대해서는 최고 점수가 600~700점 정도였는데, Psyho 등 몇몇 코더의 경우에는 이 경우를 정확히 찾아서 특별 처리를 해줌으로써 1500점 이상의 점수를 받는 일도 생겼습니다. Provisional test 50개에는 이런 예제가 없었지만 사실 이런 경우는 그리 드물지 않기 때문에, 정확히 반영되는 최종 순위에는 큰 변화가 생겼습니다.
최종 결과는 제가 7위를 기록했고, 평균 100개를 찾았습니다. (system test 1000개 결과 100273점) 원래도 1위였으면서 위에서 설명한 케이스를 잘 처리해서 독보적인 1위가 된 Psyho는 139677점으로 평균 140개를 찾았구요, 12위 커트라인으로 대역전을 성공시킨 ploh는 89129점을 기록하였습니다. 1~20위까지의 모든 프로그래머는 DFS를 사용하였네요.
Final에 갈 수 있는 R3이니만큼 경쟁도 아주 치열했습니다. 보통의 Marathon Match는 2주 내내 하는 사람은 그리 많지 않고, 상위권 코더라도 2~3일 정도의 코딩 타임을 가집니다...만 R3 최종순위 1~30위 정도까지는 첫날부터 2주간 계속 달린 것으로 보입니다. Psyho의 경우 첫날 첫 서미션부터 24시간동안 10번 서밋을 하는 괴력을 보이며 레이스를 주도했으며, ACRush는 중간에 GCJ Final을 다녀오는 시간을 제외하고는 계속 달리는 강철체력을 과시했습니다. 저는 여름휴가 간다고 6일째가 되어서야 첫 서밋을 했는데, 마감 24시간 전에 제출한 솔루션부터 커트라인을 돌파한 것으로 추정합니다.
다른 MM과 마찬가지로 빠른 development cycle과 시간 투여가 중요한 대회였습니다.
13년 전