11월 2일은 올해의 2007 ACM-ICPC Asia Programming Contest - Seoul 대회가 열린 날이다. 이 대회는 정보통신부가 주최하는 제 7회 대학생 프로그래밍 경시대회와 함께 개최되었다. 2001 년 첫 대회를 시작으로 벌써 7회째를 맞는 대회이다.
나는 직접참관을 고려하다가 이런저런 사정으로 그냥 회사에서 인터넷으로 관람을 했는데 매우 재미있었다. 대회 중계에도 참여해보고.. ㅋㅋ
ACM-ICPC 서울지역대회는 매년 그 규모가 성장하여 작년에 참가팀수가 200 팀을 넘어선데 이어 ( 207팀 ) 올해는 300 팀을 훌쩍 넘겼다. ( 349팀 ) 아시아에서는 중국 다음가는 큰 규모이다.
대회 홈페이지 : http://acm.kaist.ac.kr
ACM-ICPC 서울대회 문제 셋
ACM-ICPC 서울대회 문자중계 기록
ACM-ICPC 의 재미있는 점중 하나는 대회 진행도중 문제를 하나 풀때마다 풍선을 하나씩 달아준다는 것이다. 각 풍선의 색깔은 문제번호를 의미하고, 높이 달리는 풍선일수록 난이도가 어렵다는 것을 의미한다. 대회가 진행되다 보면 풍선을 많이 단 팀과 풍선을 적게 단 팀간의 희비가 엇갈린다.
대회는 오전 10시부터 오후 3시까지 5시간동안 치뤄졌고, 총 10문제가 출제되었다.
대회가 시작하자마자 가장 쉬운 A 번부터 많은 팀들이 순식간에 풀기 시작한다.
이 당시는 아직 팀명이 제대로 나오지 않던 상태의 스탠딩이다.
team22 = KAIST Farmer John, team4 = 서강대 KURU, team15 = 포항공대 Poscat, team31 = 서울대 We Are But Men, Rock (이하 WABMR), team13 = ICU Strawberry, team14 = ICU Anytime, team33 = 대만국립대 AC 순이다.
A 번은 주어진 화학식에 섞여있는 원소기호와 숫자를 파싱해서 원소기호의 무게 * 숫자를 계산하면 되는 쉬운 문제이다.
2 번째 문제를 가장 먼저 푼 팀은 team14 = ICU Strawberry 였고, 그 뒤가 서울대 WABMR 였다. B 번은 주어진 문자열에서 2번 이상 나타나는 가장 긴 Substring 을 찾는 문제였다. suffix tree 를 이용해서 구현하면 된다고 하는데, 입력의 최대길이가 N = 5000 밖에 안되므로 그냥 무식하게 Brute Force 로 돌려도 풀린다. Team42 (중산대학교 ZSU_Dubhe) 팀은 특이하게 B 를 첫번째 문제로 선택해서 가장 먼저 풀었다.
대회 시작 40분이 되면서 서울대의 Mighty Friend 팀이 3번째 문제를 풀면서 잠시 중간순위 1위를 차지하기도 하였으나...
대회시작 50분이 지나면서 중국의 명문, 중산(中山, ZhongShan University) 대학교 가 4문제 (B A D E)를 가장 빨리 풀면서 다시 중간순위 1위로 올라선다. (중산대학교는 2006 년 서울대회에도 참가하여 3위를 기록한바 있다.) 그 뒤로 3문제를 푼 2위 그룹이 형성되어 있는데, 파키스탄에서 온 Punjab Univ. College of Information Technology 가 3문제로 순위권에 포함된 것이 의외였다.
대회 시작후 1시간 30분이 지난 시점. 놀라운 이변이 일어났다. 대회 전까지 누구도 주목하지 않았던 파키스탄의 펀잡 기술대학이 5번째 문제를 풀면서 (A B E C D) 1위로 올라선것. 관람하던 사람들과 중계하던 사람들 모두 웅성거리면서 올해 서울대회에서 한국팀이 우승을 차지하기가 쉽지 않겠다는 의견이 나오기 시작한다.
바로 이 팀이 중반이후 1위로 치고올라선 문제의(?) 펀잡 기술대학이다. 왠지모를 포스가 느껴진다~~
오전 11시 38분. 대회 시작한지 1시간 35분 정도가 지난 시점. 서울대 Incoming 팀도 5문제를 풀어 (A B E D F) 펀잡을 뒤쫒고 있다. 이 시점까지 2 문제 이상을 푼 팀은 총 24팀이고 아직 한문제도 풀지 못한팀도 4 팀이 있었다.
오전 11시 52분, 대회시작 후 110 분이 지난 시점이다. 펀잡은 또다시 6번째 문제 ( A B E C D F ) 를 풀면서 단독 1위를 질주한다. 인하대가 3번째 문제를 풀면서 초반에 선전하고 있다. ( 인하대는 여기에서 더이상 문제를 추가로 풀지는 못한다. )
차츰 대회는 중반을 넘어서 후반으로 가고 있었다. 대회 도중에는 도시락이 지급되어 참가자들은 식사를 하면서 문제풀이 코딩을 한다. ( 일부 열혈 참가자들은 밥을 굶으면서 대회에 매진한다. ^^ ) 파란색 풍선이 가장 많이 보이는 것으로 보아 역시 제일 쉬웠던 A 번이 파란색 풍선을 의미하는 것으로 보이고, B 번이 노란색 풍선인 것 같다.
대회 시작 2시간 10분이 조금지난 12시 15분 경, 온라인 예선에서 1위를 차지했던 WABMR 팀이 6번째 문제를 풀면서 다시 1위 자리를 빼았았다. WABMR 팀은 lewha0, zizavino 님과 같은 TopCoder 의 한국 상위 랭커가 팀을 이룬 강력한 우승호보 팀이다. 한편, 온라인 예선에서 좋은 성적을 거두었던 몇몇 팀들이 상대적으로 부진한 것도 눈에 띈다.
오후 1시 10분, 대회 시작한지도 3시간이 넘어섰다. 펀잡이 1시가 되기 조금전 7번째 문제 (G) 를 먼저 풀고, 10여분 후에 서울대 WABMR 팀도 7번째 문제 (F) 를 풀었다. 한편 외국팀들도 상당히 선전하면서 슬금슬금 순위가 올라오는데, 3 위의 중산대, 7 위의 홍콩과기대, 12 위에 천진 대학이 위치해 있다. 온라인 예선 1-2-3 위를 차지한 서울대는 서울대회 본선에서도 중간순위 2-4-5 를 차지하는 저력을 보여주고 있으며, ACM-ICPC 의 전통의 강호 ICU 와 KAIST 도 10위권 내에 위치하고 있다. 한편 4번째 문제를 푼 서강대 KURU 팀의 선전이 눈에 띈다.
오후 1시 50분. 온라인으로 공개하는 공식 순위 업데이트는 대회가 종료되기 1시간 전부터 중단된다. 이제 공식순위 업데이트가 얼마남지 않은 시점에서 여전히 1,2 위팀은 7문제에 멈춰있다. 서강대 KURU 팀이 5 번째 문제를 풀면서 ( A D E F B ) 10위까지 치고 올라갔고, 경희대 Zraler ( 즈랄러 라고 읽는다 -_-;; ) 팀 역시 4 번째 문제 ( A D C B ) 를 풀면서 입상 안정권에 들어섰다. TopCoder 에서 최근 많은 활동을 보이고있는 서강대와 경희대 두 학교는 모두 작년에 비해 향상된 성적을 거둘 가능성이 높았다.
오후 2시 12분. 순위 업데이트가 끝나고 더이상의 공식적인 순위 정보는 제공되지 않아 이제 현장에 구경간 특파원? 들의 정보에 의존해야 하는 상황이었다. 이 당시 상황으로는 펀잡의 월드파이널 출전과 서울대회 우승이 매우 유력해 보이는 상황이었다. 상대적으로 서울대 WABMR 팀은 패널티에서 밀리고 있어서 우승을 하기 위해서는 8번째 문제를 풀고 펀잡이 7문제로 굳는 것을 바랄 수 밖에 없는 상황이었다.
대회 1시간 남겨놓고 펀잡에 이어 2위에 있던 서울대 WABMR 팀. 괴로워하고 있음 -_-
그런데 대회 종료를 얼마남겨놓지 않은 시점에서 사고?? 가 터졌다
소식을 듣기로는 펀잡의 부정행위가 발각되어 급히 대회 스탭들이 사실 여부를 조사하기 시작한 것이다. 정확한 내용은 알려진 바 없으나 펀잡이 대회장 내에서 해킹을 시도하여 다른팀의 소스코드를 해킹하여 문제를 풀었다 한다.
부정행위로 인해 실격처리 되어 자리에서 Out 된 펀잡... -_-; ;
결국 펀잡의 서울대회 돌풍은 한바탕 해프닝으로 끝나게 되고, 막판에 8 번째 문제를 푼 서울대 WABMR 팀이 우승을 차지했다. ( 중산대도 8 문제를 풀어서 2위, 3위는 ICU. 최종 공식 순위는 아직 홈페이지에 공개되지 않음. )
최종 결과가 나오면 다시 정리하겠지만, 금년 대회도 매우 흥미로웠다. ;)
역시 Competetion 은 당사자에게는 피를 말리지만 보는 사람에게는 재미와 즐거움을 준다 -_-;;
