History: 알고스팟 모의고사 준비 프로세스

그동안 알고스팟은 1년에 두 번 정도 정기적으로 모의고사를 준비해 왔다. 대회의 규모는 점점 늘어나 해외 팀을 초대하기에 이르렀다. 하여, 지금까지 대회를 준비하면서 얻은 노하우나 기억해야 할 사항들을 이 문서에 정리한다.

초반

대회 준비 결의

가장 먼저 해야 할 일은 대회의 목적과 준비 방법, 일시 등 밑그림을 그리는 일이다. 알고스팟 대회의 경우 항상 정해진 규칙에 따라 날짜를 정해 왔고, 목적이 분명하기 때문에 이 부분은 크게 문제가 되지 않는다.

  • k주년 기념 대회: 인터넷 예선 전 주의 토요일
  • 리저널 대비 모의고사(k.08주년 기념 대회): 리저널 전 주의 토요일

밑그림을 그렸으면 가장 먼저 필요한 일은 주변에서 함께 할 사람들을 모아 설득하는 작업이다. 전문가들에게 조언을 구하는 것도 좋다.

문제 아이디어 수집

알고스팟의 경우 어떤 문제를 쓸 지 본격적으로 결정하기 이전에 무차별적으로 문제 아이디어를 수집한다. 이 과정의 효율성에 약간 문제가 있긴 하지만, 다들 각자 생업에 바쁜 운영진들에게 언제까지 문제 하나를 만들어 내라고 하기엔 무리가 따른다.

문제 아이디어를 수집하는 과정에는 너무 허황된 것이 아니라면 어떤 것도 괜찮다. 단, 향후 문제 평가 과정에서 쓸 수 있도록 어느 정도 구체화는 시킬 필요가 있다.

이러한 문제를 관리하는 데에 지금까지는 주로 이슈트래커(redmine)을 사용해 왔지만, 나름 장단이 있었다. 가장 큰 단점은 접근성이었는데, 나중에는 아이디어만 구글 닥스 등을 통해 공유하는 사람도 있었다. 이 과정에서 특별히 형식에 제약을 두지는 않았지만 최종적으로 관리자 역할을 수행하는 사람이 흩어진 문제 아이디어들을 한 곳에 모으고 정리하는 작업을 별도로 진행해야 했다.

중반

문제 선정

상황에 따라 다르지만 2~3주 정도 남은 시점에서 문제 풀에 쌓인 문제들을 모아 문제를 선정하는 작업을 한다.

문제 선정 회의

이 과정에서 무엇보다 가장 큰 난관은 출제진들이 바쁘다는 점이다. 이는 두 가지 문제를 야기한다. 첫째, 다른 사람이 제안한 문제들을 서로 서로 모두 읽기에 어려움이 있다는 점이다 (따라서 문제 아이디어를 제시할 때에 조금 공을 들여서 작성하면 도움이 될 수 있다). 둘째, 문제 선정 회의 소집 시점을 잡기가 어렵다.

이것이 전자와 후자가 엮여서 미묘한 상황을 만들어내곤 하는데, 문제 선정 회의의 시점을 특정하면 그 시점에 나타날 수 있는 사람들은 많지 않다(*명심하라: 대회를 준비하는 것은 항상 누군가의 휴식시간을 기부 받는 행위이다*). 또한 모인 사람들도 문제를 읽고 오기에 충분한 시간을 가지지 못했으므로 문제를 읽다 보면 시간이 많이 지나 몇몇 사람들은 돌아가기도 한다. 따라서 문제를 논의하기에 적절한 방식은 아니라 할 수 있다.

근래 알고스팟의 경우 구글 스프레드시트를 활용하여 문제 링크와 각자의 평가를 기입하도록 하였다. 최종적으로 문제를 선정하는 것은 IRC에 사람이 많을 때(....) 이뤄지곤 한다.

문제 선정 규칙

문제 선정 규칙에 대해서 논의하는 것만으로도 별도의 글을 작성할 수 있겠지만, 대략 다음과 같은 것들을 생각해 보아야 한다.

대회의 목적에 잘 부합하는가

모든 것의 전제조건이지만, 항상 대회를 어떤 목적으로 치르는지를 유념해 두어야 한다. 알고스팟 모의고사의 경우 인터넷 예선과 리저널 준비를 돕기 위해 치르는 것이므로 ACM-ICPC 한국대회의 경향에 지나치게 벗어나거나 수준을 맞추지 못하는 등의 일이 없도록 주의해야 한다.

난이도 분배는 적절한가

난이도 분배의 경우, 대체로 아래 다섯 그룹으로 참가자들을 나눈다고 생각하면 도움이 된다. 이 분류는 계속해서 논의에 써먹도록 하자.

  1. 입문: 대회에 사실상 처음 참여하는 사람들. 심지어 온라인 저지 경험이 없거나 거의 적다. 입출력하는 방법조차 잘 모르며, 가르쳐 주어도 잘 모르는 경우가 많다.
  2. 초보: 대회에 한 번 정도 참여해 보았고 ACM-ICPC 준비 동아리에 이름을 걸쳐 놓은 정도의 팀. 어쩌다 가끔 하는 정도이고, TopCoder SRM Div 1 Level 1 급의 문제를 주면 1~3시간 정도 걸려서 푼다.
  3. 중수: 대회 준비를 그럭저럭 열심히 한 팀. 팀 연습도 해 보았고, 나름 각 대학에서 1팀~2팀으로 분류되는 팀이다. 어느 정도 저력이 있으므로 쉬운 문제들을 모두 풀고 중급 문제를 취향껏 푸는 경우가 많다.
  4. 고수: 대회 경험이 많은 팀. 여기에는 정보올림피아드 경력도 포함된다. 중급 문제까지는 다 풀어 주고 어려운 문제를 몇 개나 푸느냐, 얼마나 빨리 푸느냐가 관건이다.
  5. 굇수: 제일의 견제 대상이다. 대회가 한참 남았는데 다 푸는 것만은 막아야 한다. 예: RoyalRoader

위 팀들을 잘 가를 수 있도록 분배하되, 다음 사항에 신경쓴다.

  • A번 급의 쉬운 문제는 최대한 가급적 꼬아 내지 않는다. 이건 입문급 팀들을 배려하기 위한 장치로 활용해야 한다. B번에 대해서는 이견이 있을 수 있지만 이건 초보급 팀들이 아주 쉽게 풀지는 못하도록 어려울 필요가 있다.
  • 난이도 스케일은 TopCoder SRM Div 1에 나온다면 난이도 얼마 정도로 나올까? 하는 기준이 비교하기에 적절하다.
  • 단, 출제진이 생각한 난이도에 1.2 내지 1.5 정도의 상수를 곱한다. 잘 지켜지지 않는 부분이지만 출제진은 풀이를 알고 있기 때문에 문제의 난이도에 대해 매우 낙관적으로 평가하게 마련이다. 주의해야 한다.

문제 장르 분배는 적절한가

아무리 난이도 분배가 적절하다고 해도 기하 문제 다섯 개를 내는 것은 일본 리저널 대비용이다. 대강 나누자면 아래와 같은 장르를 생각할 수 있다.

  • 문자열
  • 기하
  • DP
  • 그리디
  • 구현
  • 그래프
  • 탐색
  • 수학

위의 장르가 꼭 확정적인 것은 아니다. 대체로 어려운 문제의 경우 여러 장르가 혼합되어 있는 경우가 많은데, 이런 케이스는 문제 풀이 적다면 어차피 풀 팀이 몇 없으니 크게 고려하지 않는 것이 좋다(!)

기술적 어려움은 없는가

  • 입/출력 데이터가 너무 크지는 않은가: PC^2의 경우 입력을 대략 1M~10M 이내로, 출력을 0.5M 이내로 유지하는 것이 좋다.
  • Special Judge가 필요하지는 않은가: SJ를 준비하는 것은 생각보다 큰 일이고, SJ 자체가 어려운 경우도 있기 때문에 고려해야 한다.
  • 알고리즘의 효율성을 가지고 줄세우기에 애매하지 않은가: O(N)과 O(N lg N)을 구분하는 것은 보통 어렵다. 자바를 쓰는 경우에는 주의해야 한다.

기타

  • 문제가 특정 사전 지식을 요구하지는 않는가?
    • 학문적으로 특정 지식을 알고 있으면 아주 쉽게 풀리는 경우
    • 문제를 표현하는 모델이 사전 지식이 있으면 쉽게 설명되는 경우. 예를 들어 문명 5의 육각 격자 타일이라거나, 윷놀이, 볼링 등이 등장하는 경우이다.
  • ?

대회 공지

문제 선정과 독립적으로 대회 공지를 슬슬 진행한다.

대회 공지문의 작성

대회 공지는 가급적 읽고 편집하기 쉬운 곳에 하는 편이 좋다. 알고스팟 v2 시절(바닐라 포럼 시절)에 게시판에 공지를 잘 하지 않고 구글 닥스를 이용하곤 했는데, 문서의 편집과 스타일링이 구렸던 것이 한 몫 했기 때문에 알고스팟 v3에서는 크게 신경쓰지 않아도 될 것으로 보인다.

해외 팀의 신청을 받는 경우 영어 공지도 병행해야 한다.

참가 신청 페이지

참가 신청 페이지는 구글 스프레드시트의 폼 기능을 활용하는 것이 가장 간편하다. 터미널 스타일 등을 사용하면 공돌이 냄새를 첨가할 수 있다.

참가 신청에 대해 변경사항의 요청이 늘 발생하기 때문에 받을 수 있는 창구를 마련하도록 한다. 참가자들이 등록 여부를 조회할 수 있는 페이지를 만들어 두면 좋다.

대회의 홍보

사람이 모일만한 곳에 홍보를 진행한다. 단, 대회의 취지와 규모를 반드시 생각해야 한다. http://acm.kaist.ac.kr/ 이나 각 대학 동아리, 페이스북과 트위터 등은 좋은 홍보 수단이다. TopCoder 포럼의 경우 고민의 여지가 있다. 대회 운영을 잘 해낼 자신이 있을 때만 하도록 하자.

문제 준비

문제 준비 과정에서 맞이할 수 있는 최악의 어려움은 "아 이 문제가 생각해 보니 이렇네!" 하고 바뀌는 것이다. 이런 상황이 항상 발생할 수 있다고 유념해 두자. 위에서 문제를 선정할 때에 결정한 어느 정도의 밑그림 안에서, 다음 각 항목을 준비한다. 최근에는 아이디어의 제시자와 각 항목을 준비하는 사람이 서로 다른 경우가 빈번해졌다 (문제 출제의 분업화).

디스크립션

사실상 최악의 경우에 이 상태 그대로 출제해도 된다고 생각될 정도로 가다듬어서 작성해야 한다. 그렇게 가다듬더라도 대회 전날, 심지어 직전까지 문제점이 보이게 마련이다. 디스크립션은 최대한 빨리 써 두는 편이 좋다. 디스크립션을 작성하며 서로 다른 사람에게 계속해서 조언을 구하면 도움이 된다. 이 때 실력이 굇수에 가까운 사람일수록 디스크립션을 대충 읽는 경향이 있으므로 주의.

영문 디스크립션이 필요한 경우는 영작에 자신이 없으면 보통 한국어로 작성한다. 최초에 작성한 출제자의 의도가 명확하게 드러나야 향후 문제가 생겼을 때 수습할 수 있기 때문이기도 하고, 사실 무엇보다 출제자가 불필요하게 스트레스를 받지 않는 것이 중요하다. 향후 영어에 능통한 출제진의 도움을 받아 영작을 진행한다.

레퍼런스 솔루션

레퍼런스 솔루션의 경우 가능한 한 문제에서 주어진 조건을 최대한 검증하도록 짜는 것이 좋다. 중복된 값이 주어지지 않는다고 한 것을 지키는지, 범위를 지키는지를 명확하게 항상 검사하도록 하자.

테스트 데이터

"어떤 케이스를 오답으로 인정할 것이냐"를 생각하고 데이터를 만들어야 한다. 보통 시간 복잡도를 기준으로 가르는 경우가 많으므로, 이 경우는 느린 솔루션을 자르기 위한 큰 데이터와 예외적인 몇 가지 경우들을 간단히 추가하는 것이 최소한 갖춰야 할 사양이다. 여기에 말도 안 되는 그리디 솔루션이나 각종 탐색 가지치기 테크닉을 활용하지 못하도록 신경쓰는 것을 더하면 좋다.

또한 데이터는 위에서 언급한 기준에 따라 크기에 항상 주의해야 한다. 데이터의 형식은 (복잡한 구현을 의도한 문제가 아니라면) 가능한 간결하게 정해야 한다. 데이터를 만드는 과정에서 문제의 제한이 자주 변경되는데, 잊지 않고 문제 디스크립션에 즉시 반영한다.

여기에 필요하다면 Special Judge가 추가된다.

문제 검증

문제 준비 작업과 별도로 준비되는 것부터 문제 검증 작업을 진행해야 한다. 출제자의 마인드가 되어 문장 단위로 뜯어 가며 읽는 작업이 필요하다. 이 때, 최대한 출제 과정에 엮이지 않았으며 문제를 꼼꼼하게 풀어 본 사람에게 주는 편이 좋다. 가능하면 해법을 미리 알려주지 않아야 한다.

맞춤법 검사기를 활용하는 것도 도움이 된다.

후반

대회가 며칠 남지 않은 시점이다. 문제 출제 진행 상황을 수시로 점검하며 여러 제반 사항들을 신경쓸 시점이다. 매일 대회 등록 팀 수의 델타가 증가할 것이다.

서버 섭외

PC^2 서버가 생각보다 많은 리소스(트래픽, CPU, 메모리)를 점유하기 때문에 좋은 서버를 구해 두는 편이 좋다. PC^2 버그로 로그가 수십 GB 쌓여 하드디스크 풀이 발생, 대회가 파탄난 적도 있다.

지금까지 우리 사랑하는 최치선님>.<의 레드필을 애용해 왔다. 감사합니다 ㅠㅠ 다만 이런 경우는 서버 관리자분께 대회 진행 동안 트러블슈팅을 부탁드려야 하므로 죄송스러움이 가중된다.

시간 결정

보통 날짜만 잡아 두고 시간을 안 정하는 경우가 많은데, 이 즈음에는 시간을 확정해야 한다. 확정 공지를 잘 하도록 하자.

예비소집 준비

예비소집은 참가자에게도 중요하지만 대회를 운영하는 입장에서 시스템이 잘 굴러가는지를 검증할 수 있는 테스트 단계이다. 역시 일시를 확정하여 공지한다.

문제를 준비하는 데에 너무 노력을 쏟지 않도록 하되, 참여한 사람들에게 적당한 지적 만족감을 줄 수 있도록 아주 쉬운 문제 하나, 쉬운 문제 하나, 어려운 문제 하나 정도를 준비해 두도록 하자. 전에 조판한 것을 토대로 가급적 조판까지 미리 마쳐 놓는 편이 좋다(종반에는 몹시 바쁘다).

저지 섭외

대회 시간을 확정했으면 해당 시간동안 접속 가능한 저지들을 섭외해야 한다. 대회 규모에 맞게 진행해야 하지만, 보통 알고스팟 규모로 100팀 정도 참여하는 경우 4~5명은 있어야 부드럽게 진행이 가능하다.

이상적으로는 문제별로 전담 저지를 두어야 한다. 더욱이 알고스팟은 각자 자신의 PC를 활용해 채점하기 때문에 대회 처음부터 끝까지 있을 수 있는 사람들에게 문제들을 나누어 맡겨야 한다. 파트타임으로 접속이 가능한 경우 수행 시간과 관련 없는 문제를 맡기거나, 런이 밀려 바쁠 때 런타임에러나 말도 안 되는 솔루션들을 걸러내는 데에 도움을 줄 수 있다.

저지들은 같은 환경을 쓰도록 주의해야 한다. 각 컴파일러의 버전에 항상 유의한다. 일례로, 32-bit JDK와 64-bit JDK의 차이로 저지마다 일관적이지 않은 결과를 내어 놓은 적이 있다(스택 사이즈가 다름). 헤더 의존성이 바뀌는 경우도 있다. 꼭 확인하도록 한다.

조판

슬 문제 조판 작업에 들어가야 한다. 문제 조판은 알고스팟의 경우 품질 문제로 LaTeX을 활용한다. LaTeX을 쓸 줄 아는 사람이 얼마 없어 어려움이 있다.

알고스팟의 경우 Jenkins(Continuous Integration 시스템)을 활용하여 서버에서 문제 조판을 지속적으로 진행하여 TeX이 설치되지 않은 출제진의 환경에서도 현재 상황을 확인할 수 있게 한다.

대회 직전까지 계속해서 변경 사항이 발생하기 때문에 대충 준비 된 문제들은 빠르게 조판해서 넘겨버리는 것이 좋다.

조판의 어려움에 대해 다룬 문제로는 TYPESET이 있다(?)

종반

대회 전날부터 대회가 끝날 때까지이다.

문제 및 조판 마무리

문제는 아무리 준비해도 끝이 없다. 보통 당연하게도 전날 밤을 새곤 한다. 데이터가 이 때 만들어지는 경우도 많고, 이 때까지 나오지 않는 경우도 꽤 잦다(!) 핫식스와 박카스를 부으면서 열심히 준비하자 ㅠㅠ

문제 순서도 결정해야 한다. 컨벤션은 A, B에는 가장 쉬운 순으로 두 개를 넣고 나머지를 적당히 섞는 것이지만 ACM-ICPC World Finals의 경향을 따라 한국 대회도 그런 것 없이 섞고 있다. 알고스팟도 최근 대회부터는 그 경향에 동참하고 있다.

계정 발급

대회 시스템에 접근하기 위한 패스워드를 발급해 주어야 한다. 알고스팟의 경우 구글 스프레드시트에서 동작시킬 수 있는 구글 앱스 스크립트를 활용하여 계정과 패스워드를 정해 각 참가자가 등록한 메일 주소로 발송해주고 있다 (자랑). 또한 계정 시트를 PC^2에 바로 공급하기 좋은 형태로 적절히 가공하는 도구를 갖추고 있다 (자랑).

여분의 계정을 몇 개 정도 만들어 두는 것이 좋다.

대회 시스템 설정

대회 시스템, 즉 PC^2를 설정하는 단계이다. 예비소집 때 한 번, 본 대회 때 한 번 진행해야 한다. 아래의 사항들이 설정할 만한 것들이다.

  • accounts
  • groups
  • problems
  • languages
  • contest time
  • scoreboards(balloon colors)
  • responses
  • contest title

알고스팟에서는 외부 설정 파일을 읽어들여 위의 사항들을 설정한 PC^2 프로필을 생성하는 도구를 갖추고 있다 (자랑). 풍선 색상을 지정하면 풍선 이미지를 만드는 도구도 갖추고 있다 (자랑).

스코어보드설정과 스코어보드 접근 방법에 대해서도 결정하고 집행해야 한다.

예비소집

위에서 언급한 바와 같이 예비소집을 진행한다. 대체로 예비소집때는 시간 맞춰서 오는 사람도 얼마 없기 때문에 시스템 전체를 돌아보는 마음으로 진행하도록 한다.

이 과정에서 발생한 문제점이 있다면 조치를 강구한다. 예비소집이 끝나면 계속해서 밤새 문제 준비를 달리도록 한다.

임시 대회 페이지 준비

대회 때 트래픽이 급속도로 몰리기 때문에 임시 페이지를 준비해야 한다. 임시 페이지는 대회에 문제가 생겼을 때에 공지 수단으로도 활용되기 때문에 염두에 두어야 한다. 항상 추가적으로 남기는 메세지에는 시각을 기록하도록 하자.

문제 배포 준비

문제가 제 시각에 배포될 수 있도록 하는 편이 좋다. 일부 요청이 있는 경우에는 인쇄를 위해 미리 문제를 보내준 경우도 있는데, 원칙이 확립되지는 않았다. 가능하면 10분 전에는 패스워드를 걸어 압축한 것을 배포하고, 대회 시작 시간이 되면 압축의 패스워드와 원본 PDF를 동시에 제공하고 있다.

저지의 환경 설정

MinGW gcc/g++

  • http://sourceforge.net/projects/mingw/files/MinGW/ 에서 인스톨러인 mingw-get-inst-########.exe를 받아 설치한다.
  • 설치 시 반드시 g++을 포함시켜야 한다.
  • 설치가 다 되었으면 PATH 환경 변수에 기본 경로 기준으로 c:\mingw\bin\을 추가하여야 한다.
  • 새 커맨드 프롬프트를 띄워 gcc -v, g++ -v를 했을 때 목적 버전이 나와야 한다.

Microsoft Visual Studio Express

  • http://www.microsoft.com/visualstudio/en-us/products/2010-editions/express 등에서 Visual C++ Express를 다운로드받아 설치한다.
  • 채점용 환경을 설정하기 위해 환경 변수나 pc2env.bat 등을 수정하는 방법도 있지만,
  • 시작 메뉴에서 Microsoft Visual Studio 2010/Visual Studio Tools/Visual Studio Command Prompt를 실행하면 관련 환경 변수 등이 설정된 커맨드 프롬프트가 뜬다.
  • cl /? 을 실행하여 버전을 확인한다. (32-bit C/C++ blabla.. 16.00...)
  • 이 상태에서 pc2judge.bat 등을 실행하면 문제없이 채점이 가능하다.

Oracle JDK

  • http://www.oracle.com/technetwork/java/javase/downloads/index.html 등에서 Java SE 7을 다운로드, 설치한다. 이 때, 반드시 32비트 타겟 플랫폼 (x86) 버전을 설치한다.
  • 위에서와 마찬가지로 PATH 환경 변수에 C:\Program Files (x86)\Java\jdk1.7.0\bin 등을 추가한다.
  • 커맨드 프롬프트에서 java -d32 -version을 실행하여 버전을 확인한다. 이 때 32비트용이 아니라면 지원하지 않는다는 메세지가 출력되고, 버전은 1.7.0이 출력되어야 한다. javac -version 도 1.7.0을 확인한다.

대회

대회 직전

타이머 시작 버튼을 누를 때까지 긴장의 끈을 놓칠 수 없지만, 가능하면 30분 전에는 여유를 찾고 커피라도 한 잔 끓여 오도록 한다. 아래의 사항을 다시 한 번 점검한다.

  • 조판 상태
    • 문제 수정 요청이 모두 처리되었고 반영되었는지
    • 오탈자, 예제 데이터, 범위
  • PC^2 설정 상태
    • 대회 시간 설정
    • 문제별
      • 시간 제한
      • Validator
      • 데이터
  • 임시 대회 페이지와 스코어보드 접근은 문제없이 되고 있는지
  • 저지들이 모였고 채점 준비가 잘 되었는지

대회 시작

시작 버튼을 누른다. 문제들의 난이도에 따라 짧게는 5분에서 길게는 15분까지 제출이 없다. 시스템이 이상하다고 생각하지 말 것.

첫 런이 오면 각 저지들은 첫 번째 런을 채 가기 위해 손이 눈보다 빠르다는 것을 증명해야 한다.

이후로는 별 문제가 발생하지 않는다면 졸음을 조금만 참아 가며 대회를 즐기면 된다. 굇수가 어이 없게 틀린 것에 비웃어 주기도 하고, 스코어보드를 지켜보면서 관전을 하기도 하면 된다.

대회에 문제가 발생했을 때

주로 문제에 특정 조건을 빠트리거나, 제한이 빠졌거나, 오탈자가 있거나, 설명이 부족한 경우가 대부분이다. 아예 데이터가 틀리는 경우도 종종 있지만, 쉬운 문제의 경우 준비하면서 틀리기 쉽지 때문에(!) 고수~굇수 팀 정도나 말릴 것이다 (!)

아무튼 문제에 변경 사항이 있으면 Clarification과 공지 페이지를 통해 동시에 알리도록 한다. Clarification은 push이지만 알림이 잘 안 되고, 공지 페이지는 각 팀이 poll 해야 하므로 역시 좋지 않다. 가급적 이런 사태를 만들지 않도록 하자.

종반 및 마무리

적절히 순위 경쟁이 climax에 다다르면 스코어보드 갱신을 중단한다. 물론 운영진들은 다 보고 있다.

대회가 끝나면 결과를 대충 갈무리해 업로드한다. 대회 풀이와 알고스팟 온라인 저지에의 등록은 너무 피곤하니 좀 쉬고 나서 하도록 한다(..)