BOJ 파댕이컵 출제 후기

대회 링크: https://www.acmicpc.net/contest/view/1208

 

첫 대회 개최인 만큼 열심히 공들였던 것 같다. 출제/검수진 모집, BOJ 대회 개최 신청 컨택, 무엇보다 이모티콘 작가님 컨택까지 제법 오래 신경썼던 것 같다.

 

내가 출제한 문제는 E번, H번이다.

 

E번은 원래 "정점 분할 말고 간선 분할이 정해인 문제를 만들어보자"하고 만든 문제인데, 간선분할 데이터를 만들고 보니 정점 분할이 더 최적해였다... ... 정점 분할이 적정 부하를 받도록 문제를 세팅하고 보니 간선 분할이 메모리를 2GB나 먹는 사태가 벌어졌다. 

실제 출제 과정에서 가장 조용히 넘어갔던 문제였다. 조용히 세 분이 풀어주시고 디스크립션 수정 한두번이 끝이었다.

하지만... 대회가 시작되자마자 가장 많은 질문과 지문 수정과 토의가 이루어진 문제가 되었다. 대회 전에 문제 꼼꼼히 읽어야 한다는 것을 다시금 깨닫게 해준 문제였다.

 

H번은 이상한 알고리즘같은걸 찾아보다가 보로노이 다이어그램을 발견하고 읽던 와중에 떠오른 아이디어이다. 쌍대그래프라는 단어가 등장했는데, 쌍대를 이용한 문제를 만들고자 했다. 그때 4차원 기하학 문제를 만들고 싶어서 여러가지 생각이 많았는데, 4차원 쌍대를 발견하고 이거다 해서 만들게 되었다. 사실 결국 쌍대다포체가 풀이에 반드시 필요하지는 않아서 에디토리얼에서 쌍대다포체 얘기를 빼고 싶었는데, 예전에 문제 풀때 에디토리얼이 불친절해서 고생했던 기억이 떠올라 그래프 모델링 과정까지 작성했다. 출제검수단계에서 이 문제를 사람들이 어떻게 느낄지 좀 궁금했다. 당연히 내가 봤을 때는 4차원 이상의 기하학, 정다면체 등에 대해 집중해서 찾아봤기 때문에 대놓고 이분매칭이라는 느낌이 들었는데, 검수진들 반응을 보니 그렇지 않았던 것 같다. 특히 검수 코멘트로 "이분 그래프인지 알기 어려웠다"는 멘트가 달려서 제법 난감했다. 그래서 다차원 입방체가 이분그래프라는 말을 에디토리얼에 추가로 작성해줬다.

실제 대회에서도 이분 그래프라는 사실을 파악하지 못하고 General matching으로 해결하신 분이 있었다. 크기가 작아서 해결됐지만, 4차원이 아니고 k차원으로 줬으면 해결 못했을지도...

 

원래 전체 문제가 난이도 순으로 정렬될 예정이었으나 문제 순서에 맞게 디스크립션을 작성하다 보니 결과적으로 A,B,H정도만 제외하면 Gold~Platinum 난이도에서 섞여있는 모양새가 되었다. (C번이 빡센 구현이 된 것이 컸던 것 같다.)

 

다른 분이 출제한 문제 리뷰도 해보자면, C번은 O(NMT)를 O(T^3)으로 줄여야 풀리도록 설계되었는데, bitset을 이용해 깡으로 뚫어버린(...) 문제가 되었다.

D, E, F, G는 객관적으로 난이도가 제법 비슷했는데, G가 가장 먼저 풀렸고, 깡 수학이었던 F는 일찍 풀리긴 했으나 푼 사람이 적었다. D나 E는 웰 노운 문제들을 꼬아 낸 문제라 적당한 시간에 적당히 풀린 것 같다.

 

대회 퀄리티가 아쉬운 부분이 많았는데, 검수진들 시험기간이다 뭐다 해서 일정 여유가 적었고, 애초에 기획단계에서 기간을 촉박하게 잡기도 해서 여러 부분에서 부족한 부분이 보였다. 문제만 좋다고 좋은 대회가 아니라는 것도 겪어 봤고 (문제가 좋은지를 차치하고서라도), 성공하면 늘지만 실패하면 반복하지 않는걸 배운것이라 생각해야겠다.

 

 

TODO.

다차원 초다포체 문제 만들기