2019 UNICON 운영 및 출제 이야기

대회 개최 전

아마 작년 9~10월 정도부터 Layer7라는 해킹 동아리에서는 Layer7-CTF를, Team Log라는 서버 동아리에서는 LogCon을 여니까 Unifox에서 UniCon을 열자는 이야기가 나오기 시작했다.
올해 초에 딱히 이야기가 안 나오길래 그냥 없어지는 줄 알았는데 갑자기 예산을 배정받기 시작하더니 6~7월쯤에 대회 개최가 확정되었다. 작년에 문제를 몇 개 만들어 놓은 것은 있어서 다행이였지만, 시간이 많이 않아 많이 굴러야 할 것 같았다.

문제 출제 1

처음에는

Div2B/Div3D 이하 난이도 3개
KOI 초등부 2번 ~ 중등부 1번 정도의 난이도 2개
KOI 고등부 1번 정도의 난이도 2개
KOI 고등부 1~2번 사이의 난이도 1개
KOI 고등부 2번 정도의 난이도 1개
KOI 고등부 2~3번 사이의 난이도 1개

총 10문제를 계획했다.

처음에는 생각나는 문제들을 모두 만들어서 모아봤는데 총 18문제가 나왔다.
그러나, 검수자와 이야기를 하면서 PS 대회에 적합하지 않는 지나치게 수학과 가까운 문제, 분야가 겹치는 문제, 구데기 문제 등을 제외하고 생각했더니 12문제정도가 남았다.
생각나는 문제를 모두 적어서 내다보니 기존에 계획했던 난이도 분포와 큰 차이가 나게 되었고, 결국 ~~눈물을 머금고~~ 좋은 문제 몇 개를 버리고 새로운 문제를 추가하기로 했다.

검수자

대회에는 검수자가 있어야 한다.
문제가 잘못된 풀이에 뚫리는지, 데이터를 잘못 만들지는 않았는지, 출제자의 풀이가 잘못되지는 않았는지 등 당연히 검증해야 하는 것을 객관적인 시선에서 바라봐준다.
또한, UniCon처럼 PS대회 운영 경험이 전혀 없는 사람들끼리 여는 대회에게는 대회 운영에 필요한 점들을 도와준다.
반대로, 이런 검수자가 없다면 대회는 매우 높은 확률로 망하거나 욕을 먹는다. ~~물론, 검수자가 있는 대회도 검수를 한건지 안 한건지 모르겠는 대회도 있다.~~

이 대회의 경우에는 문제 출제를 마친 후(데이터를 만들기 전)에 검수자를 구했다.
위에서 언급했던 18문제를 보면서 검수자와 이야기를 해보니 대회 준비에서 잘못된 점들이 정말 많이 눈에 보이기 시작했다.
난이도가 고르지 않고, 분야가 겹치는 문제가 있으며, 디스크립션이 좋지 않고, PS대회에 적절하지 않은 문제가 여러 개 있었다.
또한 폴리곤을 사용하지 않고 데이터를 만들며, 참가자의 수준을 고려하지 않은 문제들이 몇몇 있었다.
그리고 내가 어려운 문제라고 만든 것들은 풀이를 떠올리는 것이 어려운 문제가 아닌, 그냥 어려운 알고리즘을 사용하는 문제라서 이 문제들도 버리기로 했다.

결국 많은 문제들을 버리고 6문제만 대회에 반영하기로 했다. 나머지 4문제는 새로 출제했다.

문제 출제 2

검수자와 함께 난이도 분포부터 다시 정했다.

Div2A 정도의 난이도 5문제
Div2B 정도의 난이도 1문제
Div2C 정도의 난이도 2문제
Div2D, Div2E 난이도 각각 1문제

실제 대회에서 쓴 문제들을 보면 4~5번과 8번 난이도가 약간 올라가긴 했지만, 어느정도 잘 지켜진 것 같다.
기존에 만든 문제들 중에 정말 쉬운 문제가 없기 때문에 2개(MAX, PIANO) 만들었고, 어려운 문제 중에도 정상적인 문제가 없어 2개(TREE, EXHIBITION)를 새로 만들었다.

폴리곤을 사용하지 않고 직접 데이터를 만들겠다고 한 다른 출제자를 열심히 설득해서 결국 모든 문제는 폴리곤을 이용해 만들었다. ~~[이 블로그](http://evenharder.tistory.com/) 없었으면 대회 망했을지도 모른다.~~

다른 출제자들이 만드는 문제는 코너 케이스를 빡세게 만들어야 할 문제가 없지만, 유독 내가 만드는 문제는 그런게 많았다. 그래서 많이 굴렀다.

실제 대회에서 쓰인 문제들은 코포 스타일 문제와 OI 스타일 문제가 섞여있어 난이도가 어느 수준인지 정확하게 측정하기 어려운 것 같다.

Div2A 이하 3문제(1, 2, 3번)
Div2 B~C 난이도 3문제(4, 6, 7번)
KOI 고등부 1번 난이도 2문제(5, 8번)
KOI 고등부 2~3번 사이의 난이도 1문제(9번)
KOI 고등부 3~4번 사이의 난이도 1문제(10번)

스위핑(혹은 구간 처리), 트리, 기하, dp, 파라메트릭, 완전탐색 등 다양한 분야의 문제가 출제된 점은 만족스럽다.

문제 출제 3

내가 담당한 문제는 6번(BOMIN), 8번(DASH), 9번(TREE), 10번(EXHIBITION)이다.

6번

먼저, 6번은 올해 4월쯤에 만든 문제다. 어떤 친구가 미연시를 하는 것을 보고 영감을 받아 만들었다. 전형적인 파라메트릭 서치 문제다.
랜덤 데이터만 만들었고, 생각보다 데이터가 강한 것 같았지만, 대회중에 이상한 커팅을 시도해 맞은 사람이 있었다…

8번

8번은 여름학교 3일차때 숙소에서 자기 전에 만든 문제다. 이때 총 3개의 문제를 만들었지만 대회에는 1개만 사용했다.
정해는 prefix sum을 사용한 O(n)풀이다. fenwick tree 등을 사용한 O(n log n) 풀이를 막기 위해 노력했지만, 잘못하면 O(n)풀이까지 막힐 수 있을 것 같아서 O(n log n) 풀이는 허용하기로 결정했다.
결국, AC를 받은 4명 모두 O(n log n) 풀이를 사용했고, prefix sum도 fenwick tree도 아닌 스위핑을 이용했다…

9번

9번은 여름학교 10일차때 small to large 설명을 듣자마자 구상한 문제다.
KOI2016 중등3번에서 사용한 쿼리를 뒤집는 아이디어와 APIO2012 A번 등에서 나오는 큰 set에 작은 set을 붙이는 아이디어를 섞은 문제다.
디스크립션은 KOI2016 중등3번을 가져와 문제에 맞게 변형만 했기 때문에 몇몇 사람들은 익숙한 디스크립션이였다.

데이터를 정말 공들여서 만들었다.
랜덤 데이터는 1~40, 45, 58~70, 총 54개를 넣었다. 앞에 있는 40개는 큰 데이터, 뒤에 있는 14개는 작은 데이터다.
트리 문제니까, 당연히 치우친 트리가 있어야 한다. 모든 정점의 차수가 0 또는 2인 트리 4개(41~44)와 차수가 0 또는 1인 트리 1개(46)를 넣었다.
혹시 몰라서 모든 노드의 부모가 루트인 트리를 1개(47) 넣었다.
모든 정점의 색깔이 같은 트리를 10개(48~57) 넣었다.

치우친 트리에서만 TLE가 나는 코드와 모든 노드의 부모가 루트인 트리에서만 TLE가 나는 코드가 모두 나와서 기분 좋았다.

대회가 끝나고 좋은 문제라고 많은 칭찬을 받았다!

10번

10번은 이 문제을 잘 포장한 문제다.
교내에서 저 문제를 푼 사람이 없길래 그대로 쓰려고 했지만, 검수자가 문제를 잘 포장해서 기하 문제지만 기하 문제가 아닌 것처럼 바꿨다.
뭔가 dp같은 것을 사용해야 할 것 같지만, 식을 잘 전개하면 사선 공식으로 다각형의 넓이를 구하는 식이라는 것을 알 수 있다.
한 명쯤은 풀 줄 알았는데 아무도 못 풀었다.

데이터는 그냥 공식 데이터를 썼다.

서버 운영

갓-구글께서 GCP에 300달러 크레딧을 주길래 서버 예산은 신청도 안 했다.
CMS를 사용하기로 했고, 세팅부터 서버 모니터링까지 서버에 관련된 모든 것은 다른 운영진이 맡아서 했다.

원래는 워커 10개를 켰지만, 생각보다 트래픽이 많이 몰려서 워커를 2개 줄이고 그 자원을 대회 페이지에 줬다.

대회 당일

스코어보드는 비공개였지만, 운영진들은 일요일이지만 학교에 나와 빔 프로젝터로 스코어보드 띄워놓고 구경했다. 정말 재밌었다.

대회가 시작하자마자 서버가 죽어서 10분 후에 완벽히 복구해서 이후로는 안정적으로 돌아갔다.
대회가 시작되고 50분정도 지난 시점에 누군가가 실수로 재채점 버튼을 눌러 70개의 제출이 모두 재채점되었다. 양이 많지 않고, 채점이 빨리 되는 문제라서 다행이였다.

운영진들이 해야할 일은 질문에 답변을 하고, 참가자들의 제출 현황을 보며 이상한 점이 있는지 찾고, 서버 모니터링이다.
제출 현황과 스코어 보드 구경하는 것이 정말 재밌다. 실력이 비슷한 참가자 두 명이 계속해서 서로를 추격하는 것이 흥미진진했다.~~자강두천~~

대회가 종료된 후에는 최종 순위 집계와 특별상 선정을 하고, 다 같이 밥을 먹으러 갔다.

마무리

대회를 여는 것은 확실히 어렵다. 해야할 것도 많고, 빠뜨리기 쉬운 것도 많으며, 하나라도 안 지키면 대회가 구데기가 될 가능성이 큰 요소들은 정말 많다.
내가 대회를 열면서 세운 첫 번째 목표가 “욕 먹지 않을 수준의 대회 만들기”다. 최근에 이상한 대회가 많이 생겨나서 최소한 나는 그런 대회를 만들고 싶지 않았다.
작년부터 많은 대회에 참가하고, 이상한 대회에도 많이 당해봤기 때문에 참가자의 심정을 잘 알고 있다. 그래서 오류 없는 대회를 만들기 위해 정말 많이 노력했다.

작년부터

선지에 답이 존재하지 않는 문제
입력 데이터가 형식에 맞지 않는 데이터가 존재하는 문제
출제자의 풀이가 잘못된 문제
출제자의 풀이가 잘못된 것을 알았지만 끝까지 공지하지 않고 종료한 대회

등등 이슈가 많은 문제가 대회에 출제되었다. 4개의 예시만 봐도 어떤 대회인지 바로 보이는 사람들도 있겠지. 모두 절대 나오면 안 되는 문제들이다.

대회를 여는 것이 어렵고, 좋은 문제를 만드는 것을 확실히 어렵다. 그러나, 좋은 문제를 만들지는 못하더라도, 오류가 있는 문제를 만들지는 말아야 한다. 만약 오류가 발견되면 최대한 빨리 참가자들에게 공지를 해야한다. 아니면 참가자만 고통 받는다.

stop make xxxx problem

목차