코드포스 라운드 개최 후기

우선 후기에 앞서서 대회가 진행될 수 있게 도와준 많은 분들에게 감사를 표하고 싶다.

코디네이터 Arpa와 head coordinator KAN이 대회 세팅을 정말 많이 도와줬다.

YeongTree는 나랑 문제 출제하면서 같이 문제에 대해서 고민했다. (풀렸는데 아직 출제 안 된 문제도 있다!)

tlsdydaud1님은 예전에 코드포스 라운드를 개최했던 사람으로서 여러 팁들과 피드백을 열심히 해주셨다.

테스터들은 (상당히 많아서 못 적겠다…) 문제의 난이도, 지문, TL/ML 세팅 등 문제를 예쁘게 만드는데 도와줬다.

 

 

 

 

 

 

 

처음에 코드포스 대회를 처음에 열 때에는 div1을 열고자 했다. 그래서 서울과고 친구들을 모두 모아서 문제들을 냈는데, div1E 문제를 못 내겠어서 포기했다. 그래서 그냥 혼자 생각나는 문제들을 div2 콘테스트를 위한 문제 보관소에 넣었다. Div2 콘테스트 문제 보관소를 만든 날짜가 2021년 4월 15일이다.

 

코드포스 라운드를 만들려면 문제를 다 만든 후에 대회를 propose해야 한다. 옆에서 antony 코디네이터는 문제를 10문제 정도 reject한다는 소리가 들려서 한 12문제쯤 준비해서 갔다. 고3이랑 코드포스 라운드 준비 시기가 겹치면 안 될 것 같아서 일부러 대회 propose를 좀 늦게 했다. 2021년 10월 쯤에 한 거 같은데, 준비하는데 1년 정도 걸린 거 보면 괜히 그런 걱정을 했던 것 같다.

 

대회를 propose하면 코디네이터한테 연락이 온다. 연락까지 생각보다 시간이 오래 걸리는데, 나같은 경우에는 6개월 정도 걸린 것 같다. 연락이 오면 코디네이터가 이거해라 저거해라 말해준다. 일단 첫번째로는 문제들을 보면서 무슨 문제를 낼지 알려준다. 아무래도 코포 라운드다보니 난이도 곡선을 맞춰야 되니까 그런 것 같다. 내가 12문제를 준비해가서 그런지 5문제를 accept 해줬다. 하나도 리젝을 안한건지, 리젝을 다 해도 5문제인건지 나는 모른다. 아무튼 하나도 리젝이 안 됐으니까 좋았다.

 

12개의 문제들 중에 A번 난이도의 문제가 없어서 호다닥 하나 만들었다. 그렇게 만들어진게 지금의 B번이다(…). 아이디어 하나면 풀리는데, A로 들어가기에는 어려운 아이디어인가보다. 암튼 그래서 6문제를 들고 세팅을 시작했다. 문제 출제도 처음 해봐서 (예전에는 문제 아이디어를 말하면 세팅을 고수 친구들이 해줬다.) 신도 나는데 문제 세팅이 생각보다 어렵다는 것을 깨달았다. AC 코드 만드는 것이 가장 쉬운 일인 것 같다.

 

일단 글쓰기와 담을 쌓아서 그런지 지문 쓰는 것이 어려웠다. 특히 영어로 쓰는데, 무슨 단어를 쓸지 잘 모르겠어서 대충 한글 영어 번역기를 사용하면서 단어들을 찾았다. 지문을 쓰면 validator checker를 짜야 된다. Validator는 데이터가 유효한 데이터인지 알려주는 코드고, checker는 답이 맞는지를 확인해주는 코드다. 이거를 짤 때는 testlib를 사용해야 한다. testlib를 써본 적이 없어서 evenharder님의 블로그를 열심히 보면서 checker와 validator를 짰다. 요즘에는 코드포스 측에서 tutorial guide를 준다. 그것도 도움이 될 것 같지만 그냥 안 읽었다. Validator와 checker를 다 만들면 테스트케이스를 만들어야 한다. C번과 D번 같은 문제들은 그냥 랜덤 데이터를 넣으면 되어서 편하게 데이터를 만들 수 있다. 그런데 A번(지금 B번)과 같은 경우에는 가능한 x, y쌍을 하나 찾는 문제인데, 툭하면 뚫릴 것 같아서 가능한 모든 뚫는 방법을 생각해서 저격 데이터를 만들어줘야 한다. 그리고 F번의 경우 케이스가 여러 가지 있을 수 있어서 각각에 대해서 테스트케이스를 만들어줘야 되고, 트리니까 성게 그래프 / 직선 그래프 도 만들어줘야 하고, 만들 테스트케이스가 많았다. 지금 생각해보면 그렇게 많은 테스트케이스를 만들어야 했나 싶기도 하다.

 

테스트케이스를 만들면서 문제가 쉽다는 생각을 하게 될 수 있다. 특히 이번 F번은 만들면서 비슷한 문제가 굉장히 많다는 생각이 들어서 조금 더 문제를 어렵게 만들었다. 원래는 모든 간선 가중치 xor을 최소화하라는 조건이 없었는데, prefix xor을 생각하고 나면 문제가 3830번과 너무 비슷한 것 같아서 뭐를 더 추가했다. E번도 원래 풀이는 set을 이용한 dp였지만, 1년이 지난 뒤에 다시 보니까 그냥 세그트리로 슥삭 밀면 풀리는 비빔밥이었다는 것을 깨달았다. 비빔밥 제조기가 된 것 같아서 슬펐지만, 그렇다고 문제들을 갈아엎기는 싫어서 그냥 계속 문제를 세팅했다. 아래는 nor라는 테스터의 피드백 중 일부이다.

 

E: Nice standard problem that finishes quickly once you write down the bruteforce and rearrange some terms. After solving this problem, I remembered that I have solved a problem in the past that used this problem as a subroutine (some codeforces round, probably div 1), but I couldn't find it.

F: The main idea here is quite standard - I have seen a lot of path-xor-queries-on-tree problems (on codeforces itself) that just need prefix xor (from the root), and once you can realize that, the problem is no harder than div2c in my opinion.

(대충 웰노운 비빔밥이라는 뜻)

 

아무튼 그렇게 해서 세팅을 다 하면, 테스터들을 모아야 한다. 나 같은 경우에는 그냥 아는 사람들이 있는 서버에서 모았다. 그리고 나니까 너무 한국인 중심 테스터가 되어버려서 최근 라운드 테스터들에게 연락을 해서 몇 명 모으기도 했다. 그래도 외국인 테스터가 부족해서 코디네이터한테 외국인 테스터를 요청하기도 했다. 코디네이터가 모으는 테스터들은 아마 숙련된 테스터들인 것 같다.

 

테스팅을 하면 문제를 정돈하기 시작한다. 시간/메모리 제한도 맞추고, 문제에 이상이 생기면 고치러 가야 된다.

F번의 경우 풀이가 $O(N)$이기 때문에 $N$ 범위를 $10^6$으로 했지만, 예상보다 큰 상수에 $N$ 범위를 줄여야 했다. 사실 아직도 코드가 왜 느린지 모르겠다. $N$ 범위가 $250000$인데 500ms가 걸린다!

A번(현재 B번) 문제가 원래는 쉽다고 생각했는데, 테스터들이 상당히 못 풀었다. B C번을 풀고 A번을 못 푼 테스터도 있다!

그리고 원래 B번이 다른 문제였는데, 테스터 중 한 명이 geeksforgeeks라는 사이트에 같은 문제가 있다고 해서 문제를 못 쓰게 됐다. 내 입장에서는 장난 문제 하나 만든건데, 생각보다 기초적이고 웰노운인 문제여서 슬펐다.

그래서 B번을 없애고 A번을 B로 옮겨서, 새로운 A번을 만들어야 했다. A번 난이도의 문제를 순식간이 2개를 만들어서 코디네이터한테 줬더니, 한 문제를 뽑아서 세팅하라고 했다. 그래서 만들어진게 현재 A번 문제이다.

D번의 경우 풀이가 매우 짧아서 별 생각없이 1초 256MB를 줬는데 테스터들이 dp 풀이를 들고 오기 시작했다. $O(N^2)$의 메모리를 잡아먹는 덕분에 넉넉하게 1024MB까지 메모리를 늘렸다. 그리고 파이썬 코드들을 돌게 해주기 위해서 시간을 1.5초까지 늘렸다. 사실 이 문제는 $O(N^2)$ 풀이와 $O(N^2logN)$ 풀이가 있다. lower_bound 때문에 붙는 로그라서 별로 신경을 안 쓰고 있었는데 파이썬에서 이 로그를 떼주면 굉장히 빠르게 잘 돈다. 1.5초를 괜히 줬나 싶기도 한다.

 

이렇게 테스팅을 다 마치면 문제들을 돌면서 최종점검을 한다. 코드포스 지문들을 위한 advice가 있는데, 그것을 다 지키면서 문제를 쓰기가 쉽지 않다. 덕분에 지문을 많이 고쳤다. 그리고 생각보다 과거에 내가 짠 코드들을 보는 것이 쉽지 않다. 내가 ps만 해서 그런지 몰라도 예전에 만든 데이터 generator를 보면서 숨이 탁탁 막혔다.

최종점검 과정에서 A번의 $O(N^2)$ 코드가 돌아야 한다고 코디네이터가 말했다. 뉴비들이 와서 $O(N)$에 못 풀고 대회를 안 치는 참사가 일어나면 안 되서 $N$ 범위를 좀 줄였다. 근데 이러고 나니까 문제에서 하라는 것을 그대로 하는 코드가 돌기 시작했다. 문제에서 구간 곱셈이 같아야 한다고 했는데, 정풀은 2의 개수를 세는 것이지만 정말로 구간의 곱셈을 하는 풀이가 돌기 시작한 것이다. 시간복잡도를 계산해보니까 스위핑을 하면서 구간 곱셈을 하는 풀이는 $O(N^2)$이라서 막을 수가 없었다. 그래서 정말 모든 $k$에 대해서 구간 곱셈을 하는 $O(N^3)$ 풀이만 막고 나머지는 모두 통과시켰다.

F번 원래 시간제한이 3초가 아니었다. 모든 테스터들의 코드가 $O(N)$으로 500ms에 돌아서, 1.5초 정도면 넉넉할 줄 알았다. 근데 나의 $O(NlogX)$ 코드가 1.5초에 돌기 시작하고, N과 X의 범위를 보면 누가 봐도 $O(NlogX)$가 넉넉히 돌아야 할 것 같이 생겼기 때문에 3초로 시간제한을 변경했다. 대회 며칠 전에 테스터가 낸 $O(NlogX)$ 풀이가 3초에 겨우 도는 것을 보면 잘 늘렸다는 생각이 든다.

최종 점검 과정에서 F와 상당히 비슷한 문제가 있다는 제보가 들어왔다. 들여다봤는데 핵심 아이디어도 같고 dfs 돌리는 것도 같아서 좀 슬펐다. 근데 문제가 옛날 문제기도 하고 완전히 똑같지는 않아서 대회에 지장을 주지는 않을 것 같기도 했다. 그냥 그런가보다 하고 넘겼다.

 

대회 직전(대략 2일 전)에는 head coordinator가 문제를 보면서 고칠 것을 고치라고 issue들을 남긴다. 그러면 그것들을 모두 처리해야 한다. 가장 바쁠 때라고 생각한다. 덕분에 지문도 깔끔해지고, 체커도 깔끔해지고, 좋은 것 같다. 이때 러시아어로 번역해주는 사람이 와서 문제 번역도 해주고 간다. 그래서 코드포스에는 러시아어 지문이 있다.

대회 정말 직전에는 대회 문제 배점을 정해야 한다. 코드포스 댓글을 보면 가끔 문제 배점이 왜 늦게 올라오냐고 물어보는 사람들도 있는데, 테스터들과 협의해서 문제 배점을 만들어야 하기 때문에 생각보다 빠르게 올리기가 쉽지 않다. 몇몇 테스터들은 대회 직전에 테스팅을 하기 때문도 있다.

테스팅 때 A가 어렵다는 지적을 너무 받아서 배점을 500-1250-1500으로 시작할까 생각했는데, 난이도가 B로는 잘 맞는 것 같아서 그냥 500-1000-1500으로 배점을 맞췄다. 그리고 앳코더식 사고방식에 익숙하지 않은 사람들은 D번을 어려워해서 D번에 2250점을 줬다.

 

여기까지 코포 시작 전에 적었다. 이후로는 코포 끝난 후에 적는거다.

 

코포 라운드 구경은 꽤 재미있다. 처음에 A가 순식간에 풀리길래 좀 놀랐다. 그리고 나서 B, C를 정말 빠르게 사람들이 밀어줬다. E가 D보다 먼저 풀린 것도 좀 재미있었다. 처음에 너무 빨리 풀리는 것을 보고 난이도가 너무 쉬웠나 생각했는데 알고 보니까 누텔라 레드들이 밀고 간거였다.

 

라운드 어드민만 볼 수 있는 것이 있는데, 바로 system test 결과를 미리 볼 수 있다는 것이다. 예전에 어디에서 들은 것 같은데, pretest를 돌리고 남는 자원들을 사용해서 system test를 미리 돌린다고 했다. 그래서 나는 pretest는 맞고 system test는 터진 사람들 코드를 구경했다. D번에서 modulo 연산을 할 때 음수 처리를 안해준 안타까운 코드 몇 개가 있었고, 나머지는 어디서 틀렸는지 잘 모르겠다. 굉장히 신경써서 pretest를 만들어도 꼭 한두명은 sys fail이 나는 것 같다.

 

코포를 하는 도중에 세터와 테스터들의 일은 질문을 받는 것이다. 나는 permutation이 뭔가요, modulo가 뭔가요 하는 다양한 질문들이 나올 줄 알았는데 의외로 별로 많은 질문들이 나오지 않았다. B번에서 n이 짝수면 n/2, n/2로 나누면 되는데, 이게 너무 날먹이라고 생각한 참가자들이 있는지 x와 y가 같아도 되는지 물어보는 질문들이 많았다. 그리고 C번에서 s 순서대로 답을 내지 않아도 되는지에 대한 질문들이 많았다. 같은 질문들이 계속 들어오면 똑같은 답변을 계속 해주면 되서 좋았다. 도중에 러시아어 질문들이 많았는데, head coordinator인 KAN이 잘 받아줬다.

 

코포가 끝나고 사람들 반응을 좀 보았다. 너무 수학수학한 라운드라서 밸런스에는 자신이 없었는데, 많은 사람들이 재미있게 풀어준 것 같다. C번은 지루한 문제라고 하는 경향이 있는데, 반쯤 사실이라서 할 말이 없다. D번에서 dp로 뇌절한 사람들, E번에 dp식 다 만들었는데 세그를 못 짠 사람들과 같이 고통받는 사람들도 좀 있었다. 내 문제를 열심히 풀어주는 사람들이 있어서 좋았다.

 

F번에서 $O(NlogX)$ 코드를 짜고 TLE를 받은 사람들이 좀 있었는데, 3초로 늘려도 TLE를 받아서 좀 슬펐다. 상식적으로 N X 범위가 작은데 3초면 돌 줄 알았지... 그리고 이렇게 숫자 크기가 작은데 4초씩 주면 사람들이 $O(N\sqrt{N})$ 정도의 이상한 시간복잡도인줄 알고 도망칠 것 같아서 그냥 TL을 3초로 유지했다. Rated인 사람들은 다들 잘 커팅해서 3초 안으로 넣은 것 같다.

 

D번이 단순 더블카운팅 문제인 것 같아서 많이 풀릴 줄 알았는데 의외로 적게 풀렸다. 이번 기회에 다들 엣코더맛 문제를 접해서 기분이 좋다. 반면 E번은 자구 비빔밥 문제이다. div2라서 많이 못 풀 줄 알았는데 다들 잘 풀었다. F번도 사실 첫번째 아이디어만 잡으면 나머지 식정리는 줄줄 나오는 문제라서 많이 풀릴 줄 알았는데 정말 적게 풀렸다. 역시 출제자는 자신의 문제를 과소평가한다는 것이 맞는 말인 것 같다.

 

이번 코포가 무사히 끝나서 다행이라는 생각이 든다. 며칠 전에 C번의 풀이가 터져서 라운드 전체가 언레 되는 사건이 있었다. 이 사건을 보고 내 라운드도 터지면 어떡하지 해서 상당히 걱정이 많았는데, 다행히 순조롭게 흘러간 것 같다. 앞으로 진행하는 대회들도 이번 라운드처럼 순조롭게 흘러가면 좋겠다.