djm03178's profile image

djm03178

September 16, 2019 16:30

개요

• Codeforces Round #578 (Div. 2)
  • Announcement
  • Editorial

지난 8월 11일, 현재 세계 최대 규모의 사설 프로그래밍 대회 사이트인 Codeforces에서 hyunuk (aka. jwvg0425) 님과 제가 공동 개최한 Codeforces Round #578 (Div. 2)가 열렸습니다. 이전까지 소규모 대회 개최에 출제자나 검수자로 참여해보기는 했었으나, 백 명 내외가 참가했던 기존 대회들과는 달리 무려 만 명이 넘게¹, 그것도 전세계에서 참가하는 대회였기에 본격적이었습니다.

이 글에서는 이 라운드가 개최되기까지의 전 과정을 돌이켜보며 생각을 서술하고, 문제별로 간단한 솔루션과 함께 코멘트를 남겨보려고 합니다.

역사

우선 대회가 처음 계획되었을 때부터 대회가 종료될 때까지의 주요 이벤트들과 그때의 생각들을 시간순으로 적어보겠습니다. 개별 문제에 대한 분석과 평가는 아래에서 따로 쓰겠습니다.

계획 및 Proposal 작성

처음 코드포스 라운드 개최를 제안한 것은 hyunuk 님이었습니다. 8월 11일 제2회 소프트콘이 끝난 직후, 바로 다음 대회를 코드포스에서 같이 준비해보지 않겠느냐는 제안을 주셨고 제가 수락하면서 대회를 만들게 되었습니다.

가장 먼저 한 일은 대회의 proposal을 만드는 것입니다. 코드포스의 대회는 개최자가 마음대로 여는 것이 아니라, 코드포스의 coordinator들에게 출제할 문제들에 대한 개요를 적은 proposal을 보여주고, 대회로 만들기에 적합한 문제 세트라는 인정을 받아야 합니다. Coordinator들은 또한 문제들의 디스크립션, 솔루션, 데이터 등을 검토하고 러시아어로 번역할 뿐 아니라², 테스터들을 모으고 완성된 문제들을 코드포스 플랫폼에 적용시켜 대회를 관리하고 출제자들과 함께 대회 중 질문에 답변하는 등 대회 전반에 걸쳐 운영을 이끌어주는 분들입니다.

Proposal은 문제의 아이디어와 의도된 풀이 정도만 제시하는 것이기 때문에, 형식적이지 않으며 엄밀한 제한도 설정하지 않아도 됩니다.

초기에는 hyunuk 님이 3문제, 제가 4문제를 기획하여 문제의 개요와 간단한 풀이를 작성하고 proposal을 열었습니다. 여기까지는 한 달 정도밖에 걸리지 않았고, 문제들도 괜찮았다고 생각했기 때문에 금방 대회를 개최할 수 있을 것이라고 생각했으나…

기다림, 거절, 그리고 새로운 문제들

그 당시 proposal이 많이 밀려 있던 상황이었기 때문에, coordinator의 연락은 아무리 기다려도 오지 않았습니다. 설상가상으로, 10월 13일에는 실수로 proposal을 닫는 버튼을 눌러 대기 큐의 맨 뒤로 밀리는 사고까지 벌어지고 말았습니다.

그렇게 해가 넘어가고, 몇 달이 지나도 아무런 일이 일어나지 않아 이대로 묻히는 줄 알았던 저희에게 처음으로 coordinator로부터 연락이 온 것은 2019년 4월 15일이었습니다.

오랜 시간 기다려 온 저희가 받은 coordinator KAN 님의 첫 평가는 냉정했습니다. 7문제 중 5문제가 너무 전형적이거나 이미 출제된 적이 있는 문제라는 이유로 거절되었습니다. 그 날 OK 사인을 받고 대회에 실제로 출제된 문제는 B. Block Adventure와 D. White Lines 두 개 뿐입니다.

생각보다 까다로운 기준에 놀라기도 했지만, 라운드가 개최될 희망이 보인다는 것이 더 기뻤습니다. 어려운 난이도의 문제들이 대부분 거절당했기에, 쉽지 않은 수준의 좋은 문제들을 다시 만드는 것이 간단하지는 않았습니다.

약 한 달에 걸쳐 다시 6문제가 완성되고, 그 후 KAN 님이 다시 찾아오신 날은 6월 4일이었습니다.

문제 작성

최상위 난이도가 다시 한 번 거절되었지만, 나머지 문제들에 대해 통과 신호를 받고 대회 구성을 시작해도 된다는 허락을 받았습니다. 이때 통과된 세 문제가 A. Hotelier, C. Round Corridor, 그리고 E. Compress Words입니다. 또한 KAN 님과의 보다 원활한 소통을 위해 Telegram을 사용하기 시작했습니다.

코드포스의 대회 문제들은 Polygon³에서 제작하게 되어 있습니다. Polygon에서 작성한 문제를 코드포스가 직접 가져오는 형식으로 되어 있기 때문입니다. 또한 가이드라인을 가능하면 지킬 것이 요구됩니다. 이때부터 대회 개최 전까지는 시간 나는 대로 지문을 작성하고, 데이터를 생성하고, 다양한 솔루션 / 틀린 코드들을 만들었는데, 이에 대한 것은 아래에서 문제별로 다시 서술하겠습니다.

그 동안 최상위 문제도 두 개를 더 만들었고, 둘 다 괜찮다는 이야기를 들었지만 그 중 더 마음에 들었던 문제인 F. Graph Traveler를 마지막 문제로 하기로 결정했습니다.

7월 31일경에는 KAN 님이 여러 테스터 분들을 불러 대회 문제들을 모아놓은 비공개 gym을 만들고 테스트를 해주셨습니다. 얼마 후 저희가 직접 백준 온라인 저지에서 홍보를 통해 여러 테스터 분들을 더 모셨고, 많은 테스트를 통해 문제들이 한층 더 두터워지게 되었습니다.

대회 직전인 8월 10일과 11일에는 지문과 데이터를 마지막으로 점검하고, 공지글 및 에디토리얼을 작성했습니다.

그리하여 정확히 1년간 준비해 온 코드포스 라운드를 드디어 개최하게 되었습니다.

대회 개최

대회 당일에는 KAN 님이 바쁘셔서 대신 arsijo 님이 봐주시게 되었습니다. 전날에서야 대회 내용을 보게 되신지라, 재빨리 문제들을 한 번씩 풀어보고 대회 세팅을 마무리 해주셨습니다. 대회 중 저희가 해야 할 일에 대한 설명을 듣고, 텔레그램 방에 모여서 대회 시작을 맞이했습니다.

관리 권한이 있는 사람에게 보이는 대회 메인 페이지는 참가자들과는 사뭇 달랐습니다. 우선, 우측에 suspicious challenges를 알리는 칸이 마련되어 있었습니다.

Suspicious challenges는 핵⁴ 시도가 성공했지만, 그 코드가 기존의 모든 system test 데이터를 통과한 경우를 의미합니다. 주로 출제자의 데이터가 약하거나, 고의로 특정 케이스에서만 틀리는 코드를 만들어 일부러 핵을 유발한 경우에 주로 보이게 되지만, 이 대회에서 유독 suspicious challenges가 많았던 이유는 따로 있는데, 문제별 분석에서 설명하겠습니다.

소문으로만 들었던 shadow judgment도 직접 볼 수 있었는데, 채점 서버가 대회 중에는 pretest만⁵ 수행하는 것이 아니라 실제로는 참가자들에게 보이지 않게 system test도⁵ 자원이 남는 선에서 같이 수행하고 있었습니다. 물론 모든 제출을 system test까지 돌릴 여력이 되지는 않기 때문에 일부 제출만의 최종 결과를 미리 볼 수 있었습니다.

대회 중에 출제자가 할 일은 질문에 답변하는 것이 거의 전부였습니다. 문제가 러시아어로도 번역되어 있기 때문에 간혹 러시아어 질문이 올라오기도 했는데, 그런 질문들은 arsijo 님이 답변을 대신 해주셨기 때문에 신경쓰지 않아도 괜찮았습니다. 총 116개에 달하는 질문들에 2시간 동안 답변을 했습니다.

참가자 수가 워낙 많다 보니, 질문도 가지각색이었습니다. 대부분은 단순히 지문을 잘못 해석한 것이 원인이었지만, 생각지도 못한 부족한 조건을 찾아내는 참가자들도 있었습니다. 또한 문제가 안 풀린다고 출제자에게 욕을 하는(…) 질문도 있었습니다. 조건이 명확히 부족한 것이나 헷갈릴 여지가 있는 것들은 모아서 전체 공지를 보냈습니다.

그렇게 무사히 대회가 종료되고, system test를 거친 뒤 최상위권 참가자들을 축하해준 뒤, 에디토리얼 글을 올리는 것으로 모든 일정이 마무리 되었습니다.

문제별 분석 및 평가

문제에 대한 자세한 풀이법은 에디토리얼에 적혀 있으니, 이 글에서는 풀이보다는 각 문제를 출제하기까지의 과정, 또 문제를 만들고 대회를 지켜보면서 들었던 생각들을 중심으로 쓰겠습니다.

A. Hotelier (500)

hyunuk 님의 문제로, 세 종류의 연산을 간단히 브루트 포스로 처리하면 되는 간단한 문제입니다. 처음의 proposal에는 포함되지 않았지만 지금은 B번이 된 Block Adventure 문제가 제일 쉬운 난이도로 적합하지 않다는 KAN 님의 의견에 따라 새로 만들게 되었습니다. 지금 생각하면 이 문제를 만들지 않았다면 난이도가 시작부터 산으로 가버리는 세트가 되었을 것 같습니다.

이 문제를 통해 확실하게 느낀 것이 하나 있다면, 쉬운 문제일수록 pretest에 신경을 정말 많이 써야 한다는 점입니다. 문제 자체가 해야 할 일이 너무나 직설적이고, 입력 범위가 커서 세 종류의 연산을 올바르게 수행하는지 pretest만으로도 충분히 전부 점검해볼 수 있을 것이라고 생각했고, 그 때문에 출제자와 테스터 누구도 system test에서 실패하는 코드가 그렇게 많을 것이라고 생각하지 못했습니다. 알고 보니 system test에서 틀린 대부분의 코드는 단순히 반복문의 왼쪽 경계나 오른쪽 경계를 온전하게 체크하지 못한 코드들이었고, 이런 실수는 흔하게 나올 수 있음을 간과하지 말았어야 했는데 실제로 그러한 코드들을 테스트 해보지 않고 랜덤과 몇 가지 패턴만으로 pretest에서 걸러질 것이라고 안일하게 생각한 것이 착오였습니다.

B. Block Adventure (1000)

제가 만든 문제로, 위에서 언급한 것과 같이 처음에는 가장 쉬운 난이도로 쓰려고 계획했던 문제였습니다. 하지만 그것은 정말 위험한 생각이었음을 대회 중이 되어서야 느낄 수 있었습니다. 다른 분들이 저와 열심히 줄다리기를 해주지 않으셨다면 정말로 A번이 되거나, 배점이 지금보다 낮았을지도 모릅니다.

문제의 아이디어를 오래 생각하다 보니 ‘다음 기둥으로 넘어가기 전에 가능한 많은 블록을 가져가야 한다’와 ‘그렇게 하려면 $h_i$가 $max(0, h_{i+1} - k)$가 되게 만들면 된다’는 두 가지 관찰이 너무나 쉽고 당연하게 느껴졌는데, 대부분의 참가자들은 이 관찰에서 상당히 애를 먹는 모습이었습니다.

특히 두 번째 관찰의 경우 기둥의 높이가 0보다 작아져서는 안 된다는 사실을 한 번에 적용시키지 못한 사람이 굉장히 많았는데⁶, 이 역시 스스로는 실수하기 쉬운 부분이라고 생각하지 못하고 있었고, KAN 님이 그런 코드를 pretest에서 틀리게 하라고 말씀해주실 때까지도 대수롭지 않게 생각하고 있었습니다. 우연히도 그런 코드가 pretest에서 실패하도록 하는 데이터가 있기는 했지만, 스스로도 더 조심해야 할 필요가 있었습니다.

대회 결과를 보면서, 대회 proposal을 쓰는 곳에 적힌 경고문이 정말로 맞는 말이었다는 사실을 다시 한 번 느꼈습니다.

Difficulty: try to estimate the problem’s difficulty. It can be changed during review. Remember that authors tend to underestimate the difficulty of their problems. (출제자들은 자신의 문제를 쉽게 평가하는 경향이 있음을 기억하라.)

또한 이 문제는 본래 단일 테스트 케이스 문제로 계획했으나 다중 테스트 케이스 문제로 중간에 변경했는데, 이는 정말로 신의 한 수였다고 생각합니다. YES / NO 문제인 것만으로도 데이터를 강하게 만들기 어려운데, 이 문제야말로 99.9%의 케이스에서 맞는 기상천외한 코드들이 다양하게 나올 수 있는 문제이기 때문입니다. Pretest에도 나름 코너 케이스라고⁷ 만든 테스트 케이스들이 2천 개 이상 있었는데도 불구하고, 드물지만 system test에서 10번, 16번 케이스까지 가서야 틀리는 코드들이 일부 있는 것을 보면, 이를 단일 테스트 케이스 문제로 만들었다면 얼마나 데이터가 약한 문제가 되었을지 상상이 됩니다

C. Round Corridor (1250)

hyunuk 님의 문제입니다. 두 수의 최대공약수를 이용하여 두 지점이 서로 도달할 수 있는 범위에 있는지 판단하는 것이 목표입니다. 본래는 수의 범위를 $10^9$ 이하로 정해 최소공배수를 사용해서도 풀 수 있도록 했으나, B번과의 난이도 차이를 고려해 bigint가 없는 대부분의 언어에서의 풀이를 제한시키기 위해 범위를 $10^{18}$으로 늘리게 되었습니다. 또한 이 문제 역시 초기에는 단일 테스트 케이스 문제였는데, 데이터의 강도를 위해 쿼리 문제로 변환시킨 것은 탁월한 선택이었다고 생각합니다.

입력의 범위를 늘림에 따라 뜻하지 않게 막아야 하는 풀이가 하나 생겼는데, 바로 두 수의 최대공약수를 구하기 위해 제곱근까지의 모든 수를 나누어보는 비효율적인 풀이였습니다. 그러나 안타깝게도 이를 완전히 차단하지 못했는데, 수의 범위를 늘리는 결정이 너무 늦게 이루어지는 바람에 KAN 님과 충분히 이야기하지 못하고 급히 만든 데이터가 이를 확실하게 저격하지 못했습니다.

이 문제 역시 system test에서 실패한 코드가 제법 많았는데, 대부분 각 지점이 속한 구간을 구할 때 실수형으로 나눗셈을 한 코드들이었습니다. 참가자들이 오차 허용 없는 문제에서 실수형을 사용해서는 안 된다는 깨달음(?)을 얻었을 것 같아 기뻤습니다.

D. White Lines (2000)

저의 문제입니다. 이 문제는 proposal 초기에는 C번으로 계획되었으나, 지금 생각하면 그렇게 했다가는 큰일날 문제였습니다. 특별히 어려운 이론적 지식이 필요하지 않고, 아이디어와 구현만 있으면 되기에 무난하지 않을까 생각했는데, 그 아이디어를 떠올리고 구현을 하는 것이 모두 쉽지 않은 문제였습니다.

데이터를 만들고 제한을 설정하기 가장 까다로웠던 문제이기도 합니다. 의도된 시간 복잡도와 입력량이 모두 $O(n^2)$으로 같고, 막아야 하는 풀이가 $O(kn^2)$ 내지는 상수가 작은 $O(n^3)$이었기 때문에 느린 입력과 큰 상수를 배려하는 것 과 비효율적인 시간 복잡도의 코드를 막는 것 사이에서 조절하기가 매우 힘들었을 뿐 아니라, Java나 PyPy 정도까지도 통과시켜 주어야 했기 때문에 이상적인 제한을 설정하는 것은 거의 불가능해 보였습니다.

처음에는 2초 제한을 두고 생각할 수 있는 여러 비효율적인 풀이들을 작성하면서, 특히 좌표를 랜덤이나 특정 기준에 의해 정렬해놓고 순서대로 일부만 보는 코드 등에 초점을 두어 많은 테스트를 수행했는데, 전수조사도 효율적으로 만들면 어떤 케이스든 3초 내에 수행시킬 수 있는 것을 보고 너무 불안하여 1.5초로 시간 제한을 줄이기에 이르렀습니다. 이 문제에서 $O(n^3)$ 풀이를 원천 차단하는 것은 어차피 불가능할 것 같았고, 조금이라도 더 막자는 심정에서였습니다.

일부 코드만 살펴보았지만, 결과적으로도 $O(n^2)$보다는 큰 시간 복잡도의 코드들이 상당수 통과된 것으로 보입니다. 더욱 다양한 접근법들을 생각해 내고 개별적으로 저격할 역량이 되었다면 제한을 강하게 걸지 않고도 데이터의 완성도를 더 높일 수 있었을 것이라는 아쉬움이 남습니다.

E. Compress Words (2000)

다시 hyunuk 님의 문제입니다. 상위 난이도들이 proposal에서 다수 거절됨에 따라 만들어진 문제인데, 본래 의도는 KMP 알고리즘에서 사용하는 실패 함수를 멋지게 적용하는 문제를 만들어보자는 것이었습니다.

그러나, 대회를 며칠 앞두고 정해보다 훨씬 단순하지만 정답을 구할 확률이 100%는 아닌, 약간은 찝찝한 풀이가 발견되었는데, 바로 해시를 사용한 풀이가 간단하게 통과된다는 것이었습니다. 약간의 활용 능력이 필요하기는 하지만, 어쨌든 해시를 잘 구현하면 쉽게 맞을 수 있는 문제가 된 것입니다.

많은 사람들이 사용할 것 같은 해시 함수에 대한 저격 데이터를 일부 만들어 넣기는 했지만, 그 뿐이었습니다. 진짜 문제는 대회 중에 발생했는데, kcm1700 님께서 시도한 핵 데이터가 해시 풀이를 사용했던 테스터 한 분의 솔루션을 같이 저격하면서 Unexpected verdict가 나오고 만 것입니다. 부랴부랴 해시 솔루션들을 Polygon에서 지워 더 이상의 문제는 없었지만, 조금은 아찔한 순간이었습니다.

또한 최근에 코드포스에 uphacking 시스템이 추가되면서 대회가 끝난 이후에도 공개적으로 핵을 할 수 있게 되었는데⁸, 많은 분들이 충분히 강력하지 않은 다양한 해시 풀이들을 저격해 주시는 것을 볼 수 있었습니다. 흥미로운 경험이기는 했지만, 해시가 사용될 여지가 있는 문제는 앞으로는 기피해야겠다는 생각이 듭니다.

해시 풀이가 발견되면서 이 문제의 난이도가 D번보다 쉽다는 의견도 일부 있었는데, 결과적으로 맞은 사람의 수를 봤을 때 순서는 유지하고 D번과 동일 배점을 사용한 것은 매우 좋은 결정이었다고 생각합니다.

F. Graph Traveler (2500)

마지막으로 제가 만든 문제입니다. E번까지가 Div. 2 대회 치고는 쉬운 편이라는 의견이 대다수였기 때문에, F번도 너무 어렵지 않게 쉬운 기조를 유지하려고 생각하면서 문제를 만들었습니다. 결과적으로도 공식 참가자 중 44명이 풀어 황금 난이도 곡선을 이루게 된 것 같습니다.

일부 테스터 분들은 1에서 10까지의 자연수들의 최소공배수를 사용한다는 아이디어를 매우 쉽게 생각해서 D, E번과 동급으로 보기도 하셨는데, 저는 Div. 2에 참가하는 사람들에게는 그렇게 쉬운 아이디어가 아니라고 생각했고, 구현 난이도 역시 만만치 않기에 D, E와의 난이도 차이는 확실하다고 느꼈습니다.

이 문제를 만드는 과정에서 여러 차례 실수가 있었는데, 나가는 간선 수들의 최소공배수를 이용한다는 기본적인 아이디어는 동일했으나, 최종적으로 묻는 쿼리를 어떤 것으로 할 것인가를 쉽게 결정하지 못하고, 여러 종류를 시도해 보다가 틀린 풀이를 여러 번 작성하기도 했습니다.

이 문제에서 아쉬움이 남는 것이 하나 있다면, 풀이들이 대체로 메모리를 많이 사용할 수밖에 없도록 제한을 두었다는 사실입니다. 특히 정해를 비롯해 재귀로 푼 코드가 매우 많았는데, 최악의 경우 재귀 호출의 깊이가 252만에 도달할 수 있고 메모리 또한 기본적으로 200~300MB 정도를 사용하게 되는 것을 볼 수 있었습니다. Java로 재귀 풀이를 만들면 스택 오버플로를 피할 수 없고, C++로도 재귀 함수 내에 지역 변수를 과도하게 할당하면 런타임 에러가 발생하는 모습이 심심찮게 발견되었습니다.

정점 당 나가는 간선의 수 제한을 줄일 수도 있었지만 10으로 제한을 두는 것이 깔끔해보였고, 확실한 효과를 보려면 제한을 6까지는 줄여야 하는데 이는 1에서 6까지의 최소공배수가 아닌 $6!$을 주기로 삼는 풀이를 통과시킬 여지가 있었기 때문에 적절하지 않다고 생각했습니다⁹. 줄이려면 $n$ 제한을 줄였어야 하는데, $n$역시 딱 떨어지는 수로 만들고 싶었던 욕심이 문제를 애매모호하게 만든 것 같아 아쉽습니다.

결론

하위 division의 문제 6개를, 그것도 둘이 나누어 세 문제씩만 담당했을 뿐이었지만, 규모 있는 대회를 잘 만들어내야 한다는 부담감은 상당히 무거웠습니다. 대회의 기획부터 출제, 관리까지 중도에 마주치는 일들 하나 하나가 새로운 경험이었고, 발생하는 문제들에 대한 책임을 스스로 져야 한다는 것 또한 중압감이 있었습니다.

추후 다른 코드포스 대회를 열게 된다면 이번 대회에서 꼼꼼하지 못했던 부분, 시스템에 익숙하지 않아 도움을 많이 받아야 했던 부분 등을 개선해서 더 좋은 대회를 구성할 수 있지 않을까 생각합니다.