djm03178's profile image

djm03178

December 15, 2020 11:18

개요

• Codeforces Round #688 (Div. 2)
  • Announcement
  • Editorial
• (이전 글) Codeforces Round #620 개최 후기
• (이전 글) Codeforces Round #578 개최 후기

올해 초 Codforces에서 개최했던 620번 라운드는 제게는 잊을 수 없는 기분 좋은 추억입니다. 처음으로 단독 출제자를 해본 대회에 무려 14612명이 등록해서 좋은 반응을 이끌어냈었다는 것이 정말 좋았습니다.

그 기분을 다시 느끼고 싶어서 라운드가 종료되고 얼마 지나지 않아 바로 다음 라운드를 준비하기 시작했고,¹ 12월 4일 22시 05분(KST)부터 2시간 15분에 걸쳐 Codeforces Round #688 (Div. 2)를 개최했습니다. 이전 라운드들 개최 때와 마찬가지로, 이번 글에서는 688번 라운드의 개최 과정에 대한 후기를 작성해보려고 합니다.

개최 준비

620번 라운드는 매우 성공적으로 개최했었지만, 다음과 같은 몇 가지 아쉬움이 남아있었습니다.

• 일부 난이도가 조금 쉬웠습니다. 특히 E번 수준에 맞는 적절한 문제를 마지막까지 찾지 못해 결국 약간 쉬운 상태로 내게 되었고 오피셜에서만 714명이나 풀게 되고 말았었습니다. F번 역시 평소 라운드보다는 쉬웠음에도 불구하고 격차가 꽤 클 정도였는데, 결과적으로 F를 서브태스크로 분할한 것이 문제셋의 밸런스 유지에 큰 도움이 되었습니다. 하지만 서브태스크는 가능하면 쓰고 싶지 않습니다.
• Div. 2 전용 라운드이기 때문에 오렌지 이상의 Div. 1 유저들의 관심을 끌어낼 수 없었습니다. 물론 인원 수로만 본다면 Div. 1 + Div. 2 라운드를 개최하더라도 참가자는 10% 정도가 늘어나는 것뿐이지만, 문제에 대한 심도 있는 토론이 오고가는 모습도 보고 싶다는 생각이 들었습니다. 약간이지만 라운드 개최비가 Div. 1 + Div. 2의 반값이라는 사실도 아쉽기는 했습니다.

그래서 새로운 라운드는 처음에는 Div. 1 + Div. 2로 준비하면서 고난도 문제를 생각하는 데에 상당히 많은 시간을 투자했습니다. 그러나 좋은 어려운 문제를 만드는 것은 간단한 일이 아니었습니다. 그 이유를 다음과 같이 정리해 보았습니다.

• Div. 2 수준을 뛰어넘는 고난도의 문제에 대한 경험이 부족했습니다. 이러한 문제들은 solved.ac 기준으로 최소 다이아몬드 이상인데, 그 수준 이상의 풀어본 문제가 수십 개에 불과하기 때문에 어려운 문제에 쓰일 수 있는 테크닉이 어떤 것들이 있고, 어떤 것들이 well-known인지, 또 어떤 문제들이 재미있을지 등에 대한 느낌이 거의 없었습니다.
• 어려운 문제의 틀을 생각해도 스스로 풀이를 떠올릴 수가 없었습니다. 특히 라운드를 단독으로 개최하고자 했기 때문에 아무에게도 물어볼 수도 없다는 점도 큰 걸림돌이었습니다. 재미있는 문제의 구조를 생각했는데 아무리 생각해도 풀이를 알 수 없거나, 또는 풀이를 찾고 보니 너무 간단하거나 전형적인 문제여서 폐기하게 된 경우도 많았습니다.
• 스스로가 좋다고 생각해서 proposal에 등록까지 했는데 coordinator 300iq 님에게 거절당한 문제들도 있습니다. 고수들에게는 well-known인 테크닉으로 쉽게 풀리는 문제였던 것도 있고, 관찰 자체는 크게 어렵지 않으나 케이스를 나누어 구현을 많이 해야 해서 지루할 것이라는 문제도 있었습니다.

이렇게 오랫동안 고난도 문제에 대해 진전을 시키지 못하고, 개인 생활도 점점 바빠지면서 반 년이 흐르기까지도 문제 아이디어를 완성시키지 못했습니다. 그 사이 틈틈이 같이 생각했던 하위 문제 아이디어들은 모두 만들어졌고, 9월이 끝나가면서도 상위 문제들에 대한 미래가 보이지 않아 결국 Div. 1 + 2를 포기하고 또 하나의 Div. 2 전용 라운드를 개최하기로 결정했습니다.

그렇게 10월부터 본격적으로 Polygon에서 작업을 시작했고, 이후로는 문제에 대한 큰 변화 없이 진행할 수 있었습니다. 본래는 11월 내로 개최하는 것이 목표였지만² 바쁜 일정이 계속되면서 12월 초까지 미루게 되었습니다.

총평

라운드 자체는 아무 문제 없이 매끄럽게 진행됐지만³, 이번에도 몇 가지 아쉬운 점들이 남았습니다.

참가자 수

라운드에는 공식 / 비공식을 합쳐 총 19478명이 등록했고, 이는 지난 라운드의 14612명보다 훨씬 증가한 수치이지만 여름 중에 Div. 2 라운드가 보통 2만 명 중반 정도를 기록했던 것에 비하면 줄어든 것이라 아쉬웠습니다. 또한 참가자 수를 고려해서 이전보다 pretest의 수를 대폭 줄여야 했는데, 그 때문에 모든 문제를 다중 테스트 케이스 문제로 만들게 되었고, 덕분에 system test에서 실패하는 코드가 많이 나오지는 않았습니다.

B번 문제의 난이도

난이도의 논란이 지난 라운드보다 훨씬 크게 나타났습니다. 이번에는 반대로 문제가 너무 어려웠기 때문인데, 어느 정도 예상해서 대회 시간을 보통의 2시간이 아닌 2시간 15분으로 했음에도 불구하고 A번 문제를 푼 공식 참가자 수인 10588명의 약 35%밖에 되지 않는 3671명만이 B번 문제를 풀었습니다. A번 문제는 무난했기 때문에 거의 대부분의 참가자들이 풀었다고 하면 전체의 65% 정도에 해당하는 참가자들이 B번 문제의 벽을 넘지 못하고 2시간을 보냈다는 뜻입니다. 당연히 공지글에는 B번 문제에 대한 아쉬움을 토로하는 댓글들이 쏟아졌는데, 그 내용이 대회 이후 달린 댓글의 반 이상이라고 해도 과언이 아닐 정도였습니다.

나머지 문제들의 난이도

다행히 C번 이후 문제들에 대한 난이도 분포는 비교적 무난했습니다. E번 문제나 F번 문제가 풀린 시점이 2시간 ~ 2시간 15분 사이에 많이 위치해 있어 시간을 길게 설정한 것은 상당히 유효한 전략이었음을 볼 수 있었습니다. 특히 F번 문제를 푼 공식 참가자가 11명이고 이 중 5명이 2시간 이후에 풀었는데, 이는 Div. 2 F번 문제에 대해 제가 생각하는 적절한 공식 솔브 수 범위의 최소인 10명을 살짝 넘은 수치입니다.

지문 해석

영어 지문 작성에는 xiaowuc1 님의 도움을 받았기 때문에 지문의 표현 등은 상당히 매끄러웠다고 생각합니다. 다만 일부 참가자들에게 지문의 길이가 길다는 피드백을 받았는데, 모든 문제에 배경 스토리를 삽입한 이상 어느 정도 길이가 길어진 것은 피하기 어려웠던 것 같습니다.⁴ 다만 스토리를 구성하는 문장들도 문제 자체와 연관성이 깊기 때문에 특별히 불필요하게 길어진 것은 아니며, 어려울 수 있는 개념을 최대한 풀어서 설명했기 때문도 있어 크게 문제가 될 정도는 아니었던 것 같습니다.

문제별 평가

각 문제에 대한 평가를 해보았습니다. 풀이에 대한 설명은 아니지만 가벼운 스포일러가 포함되어 있습니다.

A. Cancel the Trains (500점, *800)

A번 문제는 문제 풀이를 시작한지 얼마 되지 않는 참가자들도 풀 수 있어야 하기 때문에 쉬워야 하지만, 그렇다고 해서 한두 줄의 문제 설명에 한두 줄짜리 풀이가 나오는 문제는 만들고 싶지 않았습니다. 그래서 관찰이 어렵지 않으면서도 깨닫는 순간이 재미있을 만한 문제 스토리를 생각했고, 만족스러운 결과물이 만들어졌습니다. 다룰 줄 아는 그림 그리는 도구가 그림판밖에 없어서 대신에 파워포인트로 그렸는데, 생각보다 의미가 잘 전달됐는지 거의 질문이 없었습니다.

B. Suffix Operations (1000점, *1400)

논란의 B번 문제입니다. *1400이라는 난이도 측정이 보여주듯 난이도를 매우 과소평가하고 있었다는 것을 알 수 있습니다.⁵ 사실 이는 라운드 테스트 중에 어느 정도 예견이 된 일인데, 퍼플~오렌지 테스터들도 푸는 데에 10~20분이 소요되었고 이 정도면 보통의 Div. 1 A번 문제를 푸는 시간에 맞먹고 Div. 1 A는 Div. 2의 C~D번 문제에 대응한다는 것을 생각하면 C에 놓아도 무리가 아닐 수준이었다고 볼 수 있습니다.

본래 이 문제는 처음에 원소의 변경이 없는 상태에서 최소 연산 횟수를 구하기만 하면 되는 문제로 기획했지만⁶, 이후 만들어진 C번과 D번 문제가 생각보다 어렵게 만들어지면서 B번 문제의 난이도를 올려야 하는 상황이 되었고, 그래서 추가한 것이 원소를 하나 변경하고 시작한다는 조건이었는데 결국 지나치게 어려운 문제가 되고 말았습니다.

또한 이 문제에 대한 질문은 전체 질문의 반을 넘는 개수일 만큼 유독 많았습니다. 질문의 대표적인 유형들은 다음과 같았습니다.

• Operation의 동작 방식을 이해하지 못하고 임의의 원소 하나씩만을 바꿀 수 있는 것으로 생각하여 예제가 틀렸다고 주장하는 질문: 지문이 operation에 대해 명확하게 정의해주고 있기는 하지만, 구체적인 예시를 본문에서 제시해주지 않은 것이 낳은 결과인 것 같습니다. 예제 설명에서 어느 정도 보여주기는 하지만 보다 확실하게 연산의 역할을 먼저 각인시켰어야 했습니다.
• 5번째 테스트 케이스의 답이 도출되는 과정에 대한 질문: 예제를 친절하게 주려다 보니 질문할 사항을 늘려버리게 된 것 같습니다. 5번째 테스트 케이스의 답을 구하는 전략을 아는 것이 곧 문제를 푸는 핵심 열쇠였기 때문에 일부러 세부 설명을 적어놓지 않았는데, 그 때문에 질문까지 많이 받게 될 것이라는 생각은 미처 하지 못했습니다.

결국 난이도를 적절하게 조절하지 못한 것이 상당히 아프게 된 문제였습니다. 점수로는 1500점 정도를 놓았어야 할 난이도인 만큼, 과감하게 A와 C 사이에 문제를 하나 추가하고 C와 D 중 하나를 지우는 방식으로 해결했었더라면 보다 균형잡힌 라운드가 되지 않았을까 하는 아쉬움이 남습니다. 그래도 문제에서 요구하는 아이디어는 좋았다고 생각하고, 새로운 것을 배웠다고 좋아해주시는 분들도 있었다는 점은 다행이었습니다.

이와 별개로 매우 아쉬움이 남는 것은 테스트가 너무 약했다는 점인데, $n \le 10$의 랜덤 케이스 1000개를 넣은 pretest 2에 $n=2$이면서 두 원소가 서로 다른 케이스가 없는 바람에 예외 처리를 잘못한 코드들이 pretest를 통과했을 뿐만 아니라, 이를 믿고 system test에서도 $n$이 작은 케이스를 많이 넣지 않아 system test까지 뚫릴 뻔한 위험이 있었습니다. 다행히 그런 취약점이 hack 하나에 의해 수면 위로 드러났고, system test 전에 MikeMirzayanov 님이 부랴부랴 $n$이 작은 랜덤 케이스들을 더 추가해서 이러한 코드들이 통과되는 것을 막을 수 있었습니다. 이렇게 해서 막힌 풀이가 약 100개에 달했으니, 반성하지 않을 수 없는 부분입니다.

C. Triangles (1500점, *1700)

처음에는 D번으로 기획했던 문제였습니다. 입력의 구조 등도 전전 라운드의 D번을 생각하며 만들었고, 구현에서 헷갈릴 요소를 줄여주기 위해 행과 열을 구분하지 않아도 되도록 두 길이를 $n$으로 통일한 것도 동일하게 적용했습니다. 하지만 테스팅을 시작하자마자 이 문제는 D번급이 아니었다는 사실이 드러나게 되었는데, 고려하지 않아도 되는 케이스를 혼자서 추가로 고려하느라 구현이 길어졌을 뿐이었다는 것을 테스터 분들에게 배우게 되었기 때문입니다.

오히려 간단한 관찰로 해결할 수 있다고 생각했던 D번 문제가 원래 C번으로 기획했던 문제였으나 고전하는 분들이 많아 자리를 바꾸게 되었는데, 결과적으로도 이 선택은 좋은 선택이었던 것 같습니다. 비록 테스팅에서 보인 차이만큼은 아니었으나 참가자들도 어느 정도 D번을 C번보다 어렵게 느낀 것은 맞는 것으로 보였습니다.

제한을 설정하기가 매우 어려웠던 문제였는데, 정해의 시간 복잡도와 입력의 크기가 모두 $\mathcal{O}(n^2)$인 문제의 특성상 최적화된 $\mathcal{O}(n^3)$를 막으면서도 효율적이지 않은 입력 방법을 사용하는 $\mathcal{O}(n^2)$ 코드들을 통과시키기도록 하는 제한을 정하기가 애매했습니다. 추가 시간이 없는 Codeforces의 특성상 느린 언어(Python 등)에 대한 배려까지 해야 하는데, 여러 테스트를 거친 후 이를 $n \le 2000$과 3초로 설정했습니다. 아마 요즘 컴퓨터의 성능을 생각한다면 통과된 코드들 중에도 최적화된 $\mathcal{O}(n^3)$ 코드가 여럿 있지 않을까 하는 아쉬움은 들지만, 이는 현실적으로 타협점을 찾기 어려운 부분이라 그래도 대부분의 $\mathcal{O}(n^3)$ 코드가 막힌 것에 어느 정도 만족하고 있습니다.

D. Checkpoints (2000점, *1900)

C번 문제로 설정하려고 했던 계획과 달리 테스팅 과정에서 많은 분들이 고전해서 D번이 된 문제입니다. 개인적으로 취약해서 이전까지는 잘 시도하지 않던 수학 카테고리의 문제를 한 번 만들어 보았는데, 사실 지금까지도 수학 이론적인 방법으로 공식을 유도하는 접근법은 잘 모르겠습니다. 그보다는 직관으로 기댓값을 구하는 방법을 찾거나, 몬테 카를로 방법으로 시뮬레이션을 돌려 패턴을 찾는 방식으로 많이 해결할 수 있을 것이라고 생각했기 때문에 높은 난이도로 생각하지 않았습니다.

문제의 스토리의 설정은 재미있게도 지금까지 여러 게임들을 하면서 생각했던 것들이 모인 것인데, 체크포인트라는 것은 어드벤처류 게임들에서 흔한 일정 구역에 도달하면 자동으로 저장되는 시스템에서 가져온 개념이고, 확률에 따라 다음 단계로 나아가거나 처음으로 돌아가버리는 것은 아이템의 강화를 시도할 때 성공 여부에 따라 강화 단계가 높아지거나 파괴될 경우의 강화 시도 횟수의 기댓값을 구해보려는 데에서 출발했습니다. 아마 이 문제를 풀어본 참가자들도 앞으로 강화를 할 때 보다 정밀한 기댓값을 구해보는 시도를 해보게 되지 않을까 생각이 듭니다.

이 문제에도 제법 질문이 많았는데, 대체로 기댓값을 어떻게 구하는지를 묻거나 기댓값 공식을 잘못 구해서 예제가 이해되지 않는다는 내용이었습니다. 기댓값 공식과 전략을 숨기기 위해 일부러 예제를 체크포인트 사이의 간격이 1과 2인 것으로만 구성했기에 어쩔 수 없었던 것 같습니다.

E. Dog Snacks (2500점, *2300)

지난 라운드의 E번 문제를 따라 이번 라운드의 E번 문제도 트리 문제로 만들었습니다. 저번 문제는 너무 전형적이라는 평가를 받았던 만큼 이번에는 조금 특별한 것을 넣고 싶었는데, 그래서 생각한 것이 트리 내에서의 움직임에 제약을 거는 것이었습니다.

처음에는 문제에서 설정한 제약이 대부분의 노드에 대해서는 일관된 전략으로 해결되지만 루트에서 예외가 되는 것이 조금 찝찝했지만, D번 문제와의 난이도 격차를 유지하는 데에 오히려 이 예외가 도움이 되었고 특별히 까다로운 처리도 아니었기에 결과적으로는 적당한 기믹이 된 것 같습니다.

F. Even Harder (3500점, *2700)

문제 제목은 눈치챈 분들도 있겠으나 evenharder 님의 아이디를 따왔습니다. 그건 망고가 아니라 고양이예요가 제가 만든 밈을 가지고 만든 문제였기에 그에 보답하기 위한 문제였습니다.

문제의 스토리와 같이 오른쪽으로 정해진 수의 칸 이하로 갈 수 있도록 하는 규칙은 오래 전부터 생각해왔던 것인데, 이를 이용하여 만들 수 있는 마땅한 문제를 생각해내기까지 긴 세월이 걸렸습니다. 현재의 문제를 생각하고도 적절한 풀이를 생각해내기 개인적으로 상당히 어려웠던 문제입니다. 테스팅 과정에서도 대부분의 오렌지 테스터 분들이 풀지 못해서 지난 라운드의 F와는 달리 정말로 어려운 문제가 맞다는 확신이 들었고, 실제로도 공식에서 11명만이 풀어내면서 E번 문제와의 배점 격차를 크게 한 것이 정답이었다는 것을 확인했습니다.

대회 중에는 없었던 것 같지만, 이 문제가 $\mathcal{O}(n^3)$으로 뚫린다는 것을 들었을 때는 적지 않은 충격을 받았습니다. 데이터가 약해서의 문제는 아니지만, $n \le 3000$이었기 때문에 2초면 충분할 것이라고 생각했는데 컴퓨터의 성능이 좋아지고 컴파일러의 최적화 기법 또한 향상되어 뚫을 수가 있었던 것입니다. $\mathcal{O}(n^2\log{n})$은 통과시켜주고 싶었기 때문에 무리해서 제한을 강하게 하지 않았던 것인데, 세제곱이 통과된다는 것은 차마 예상하지 못했던 일이었습니다.

F번 문제를 푼 참가자들이 많지는 않았지만 신기하게도 푼 참가자들은 대체로 20분~30분의 짧은 시간 내에 해결한 것을 볼 수 있었는데, 그만한 직관이 중요한 문제가 아니었나 싶습니다. 또한 모든 문제를 58분만에 해결한 비공식 참가자가 있었다는 것도 놀라웠는데, 문제들이 전반적으로 어려워서 1시간 내에 모든 문제를 푸는 사람은 없을 것이라고 생각하고 있었기 때문입니다.

마치며

난이도의 균형은 B번 문제를 기준으로 조금 어렵게 치우쳐 버렸지만, 개별적인 문제들로 봤을 때는 마음에 드는 결과가 된 것 같습니다. 충분히 오랜 시간을 두고 흥미로운 문제들을 선별했고, 참가자들의 댓글에서도 문제의 퀄리티에 대한 비판은 거의 찾아볼 수 없을 정도로 문제 각각에 대한 준비는 잘 되었다고 생각합니다.

이렇게 개인 세 번째 라운드, 단독으로는 두 번째 라운드를 마치게 되었는데, 많은 시간과 노력이 들어간 만큼 보람차기는 하지만 앞으로 자주 하기는 어렵지 않을까 싶습니다. 다른 분들과의 공동 라운드나 게스트로 문제를 내는 정도는 가능할 것 같습니다.