안녕하세요. 제3회 초콜릿컵 주최자 bubbler입니다.

그나마 visibility가 오래 유지될 만한 곳이 BOJ 블로그라고 판단하여 여기에 올립니다.

대회 문제 중 E와 K(입력 범위만 다르고 같은 두 문제)에서 지문이 문제의 의도와 다르다는 것이 대회 종료 후에 발견되어 아레나가 unrated 처리가 된 점에 대해 송구스럽게 생각하며, 아레나에 참가해주신 모든 분들에게 깊은 사과의 말씀을 드립니다.

원래 지문은 2단계의 조건이

• 이 단위 초콜릿을 떼어낸 후에도 남아있는 초콜릿은 하나의 조각을 이루지만, 그 이후에 이웃이 2ドル$개 이상인 단위 초콜릿을 아무거나 떼어내면 2ドル$개 이상의 조각으로 나누어진다.

였고, 현재 수정된 지문은

• 이 단위 초콜릿을 떼어낸 후에도 남아있는 초콜릿은 하나의 조각을 이루지만, 그 이후에 서로 이웃한 임의의 두 단위 초콜릿 사이를 자르면 2ドル$개의 조각으로 나누어진다.

입니다. 트리가 아니면서 수정 전 지문의 조건을 만족하는 그래프가 존재해서 문제가 되었는데, 이러한 그래프는 사이클을 하나 만든 다음 그 사이클에 속한 모든 정점에서 가지를 뻗으면 됩니다. 뻗은 가지에 사이클을 추가하고 같은 방식으로 가지를 뻗는 것을 반복하면 더 큰 그래프를 얻을 수 있습니다. 격자 그래프에서는 다음과 같은 경우가 존재합니다.

6
...#..
...#..
####..
..####
..#...
..#...

앞으로 있을 다른 대회에서도 같은 실수가 반복되지 않기를 바라는 마음에서, 이번 대회의 출제와 검수 과정에서 무엇이 잘못되었고, 어떻게 하면 이번 문제 오류를 사전에 고칠 수 있었을지 생각해 보았습니다.

제가 문제를 출제할 때에 이 문제는 "정점 하나를 지워 트리로 만드는 문제" 였습니다. 그런데 문제를 각색하는 과정에서 초콜릿을 쪼개는 컨셉에 맞추다가 "초콜릿을 아무거나 제거하면 쪼개진다"라는 내용의 지문이 되었고, 저는 이것이 당연히 트리와 동치일 거라고 생각했습니다. 따라서 정해 또한 "나이브하게 하나씩 제거해 본 후 트리 판별"이었고, 이것보다 더 나이브한 풀이는 상상할 수 없었습니다.

검수 과정에서도 구멍이 많았습니다. E는 Sweet division에 출제될 문제였기 때문에 제법 많은 검수자 분들이 풀이 코드를 남겨 주셨는데, 그에 반해 풀이에 대한 논의는 전혀 이루어지지 않았습니다. 심지어 지문 그대로 $O(N^6)$의 코드를 짜서 TLE가 나거나 시간이 아슬아슬한 코드가 있었음에도, 이 풀이를 막을 것인지 말 것인지에 대한 논의도 없었고, 이 풀이와 의도된 정해가 정말 같은 답을 내는지도 아무도 의심을 제기하지 않았습니다. 또한, 풀이를 정리한 에디토리얼을 사전에 공유하였으나 그 내용을 자세히 읽어보신 분은 없었던 것 같습니다.

대회에 낸 대부분의 문제를 테케 문제로 냈고 테케를 스트레스처럼 사용하다 보니, 테케가 없는 E/K와 L 등에서 취약점이 있었던 것 같습니다. L번의 경우 "정해"에 대한 반례가 검수 중에 발견되어 보완할 수 있었지만, E/K는 그러지 못했습니다. 대회 다음 날 커뮤니티를 둘러보다가 "문제를 내면서 스트레스도 안 돌려보는 대회가 있다?"라는 글을 보고 아차 싶었습니다.

의심되는 풀이에 대해 스트레스를 돌려봤다면, 에디토리얼 풀이를 누군가 읽고 이상하다고 생각했다면, 문제를 푸는 코드를 올린 후 각자의 풀이를 적극적으로 공유했다면, 이 중에 하나만 했더라도 아레나 언레는 막을 수 있지 않았을까 생각이 듭니다. 만약 검수 가이드라인 같은 것이 만들어진다면 다음의 내용을 포함하는 것을 제안합니다.

• 서로 다른 풀이 간에는 stress를 반드시 돌려 봅니다.
• 검수자가 문제를 풀고 나면 자신의 풀이 방법을 반드시 공유하고, 출제자와 다른 검수자가 이를 확인합니다. 출제자의 풀이에 대해서도 똑같이 합니다. 의심 가는 부분이 조금이라도 있다면 적극적으로 코멘트해야 합니다.

제가 이 글을 쓰는 동안 같은 주에 열린 다른 두 대회에서도 뭔가 일이 있었다고 알고 있습니다. 그 이후 적어도 약 한 달 동안 개인이나 단체(커뮤니티)가 여는 대회는 열지 못하게 되었는데, 이 시간이 대회 개최자, 출제자, 검수자라는 이름의 무게를 다시 한 번 느끼고, 출제자와 검수자로서 해야 할 일을 커뮤니티 차원에서 논의하고 조금이라도 더 명확히 하는 계기가 되었으면 좋겠습니다.

두서없는 글 읽어주셔서 감사합니다.