제 3회 IDTCup 개최 후기

어제 끝난 제 3회 IDTCup의 후기이다. 무려 21명이 운영진이었고, 참가자는 20명에 불과한 대회였지만 그래도 준비 과정을 적어본다. 부족한 운영 능력에도 불구하고 열심히 검수/참가해주신 분들에게 감사를 표한다.

Special thanks to jhhope1.

 

넋두리

대회에 대한 구상이 구체적으로 나온 건 12월 전후인 것 같다. 이때는 그래도 ICPC를 다시 나가고 싶다는 생각이 있었고. 올해 휴학을 할지 말지 정해진 부분이 없었기 때문에 PS에 대한 관심이 별로 식지 않았던 때였다. 그 사이에 이렇게 급격하게 PS에 무관심해질 줄은 몰랐다. 그래서인지 막판에는 즐겁다기보단 일로 느껴져서 부담되는 부분도 있었다.

출제자들 모두 PS에 대한 관심이 떨어진 상태라, 좋은 대회를 만들자기보다는 그냥 내고 싶은 문제를 내는 대회로 생각했다. 그래서 난이도 조절을 딱히 할 생각이 없었다. 이외에도 일하기 귀찮아서 홍보나 상금같은 부분이 미흡했던 부분이 있다. 

내년에 또 할지는 모르겠지만 아마 이름이 IDTCup은 아닐 것 같다. 몇 가지 구상중인 건 있는데 안 바빠지면 생각하려고 한다.

 

문제별 후기

풀이를 다 아는 건 아니라서 그냥 에피소드만 적으려고 한다. 그래도 스포일러가 있을 수 있으니 주의해서 읽자.

 

A. 더치페이

출제자는 Diuven. 유일하게 실생활과 관련이 있는 문제다. 실제로 정산 과정이 귀찮아서 문제를 만들었다는 이야기가 있다. 가장 쉬운 문제 중 하나로 기획했다. 검수 과정에서 의외로 선형 시간 풀이가 많이 나오지 않았다. 다들 유파나 세그트리를 사용했는데 선형에도 된다고 한다.

$0$원 송금을 하면 안된다는 사실을 문제 중간에 적어놔서 여러 사람이 틀릴 수 있겠다고 생각했고 실제로 그것 때문에 시간을 쓴 사람이 많았다. 작년처럼 입구에 있는 문제 치고 까다로웠을 듯하다.

B. 운전 브이로그

출제자는 imeimi2000.

www.acmicpc.net/problem/18862의 정풀을 아무도 시도하지 않는 것에 아쉬움이 남아 출제했다고 한다. 이 문제도 다들 정해대로 짰는지는 잘 모르겠다. 풀이부터 들었을 때는 전혀 모르겠던데 검수진들은 곧잘 풀었다. 실제로 3~4번째로 쉬운 문제로 평가되고 있다.

C. 아즈텍의 섬

출제자는 TAMREF.

원래 문제는 지금과는 전혀 달리 $O(n^{4}\log n)$에 MCMF로 풀리는 문제였다. $n \le 100$을 줬다가 안 돌아서 한 번 줄여서 $n \le 50$이 됐고, 그렇게 대회 일주일 전까지 안 건드리고 방치하고 있었는데 갑자기 풀이 반례가 나왔다. ㅋㅋ! Special thanks to aeren.

브루트포스와 MCS 사이에 마땅한 나이브 풀이가 없어서 가만히 두었던 것이 화근이었던 것 같다. 그래서 결국 원래 문제 세팅을 완전히 들어내고 어거지로 새로운 문제를 채웠다. 무려 $O(n^{8})$이라는 무식한 복잡도를 가진 문제를 내게 될 줄은 몰랐고, 결국 $n \le 8$이 되었다. 더 큰 $n$에서도 동작하긴 하지만, 커팅을 안한 deterministic algorithm이 시간 안에 돌도록 TL을 설정하였다.

D. 트리와 2개의 지름

출제자는 imeimi2000.

원래는 내가 쿼리 없는 문제를 제안했고, 적당한 플래티넘 문제로 나갈 생각이었다. 3플래 대회가 될 것 같아서 아이디어 당시에는 이것저것 뇌절을 해놨는데, 별 상관이 없을 것 같아서 선제 회의에 그대로 내놨다. 그런데 '이거 쿼리 됨?' 이라는 말이 나오고 망했다. 작년에는 그래도 다이아2 선에서 끝났는데, 이번에는 좀 더 악독한 문제가 나왔다.

사실 검수는 전날까지 안되고 있다가, 내가 짠 $O(NQ)$코드를 300min 34s 동안 돌려서 데이터를 검증했다. 아직 MCS와 같은 복잡도를 짠 사람은 출제자밖에 없다. 루비1은 무난할 듯.

E. Inversion Statistics

출제자는 TAMREF.

이 문제를 풀어보고 마음에 들어서 가지고 놀다가 $k \le 2n$이 되는 것 같아서 만들었다. $k / n$이 더 클 때도 깔끔한 풀이가 있는지는 안 해봐서 모르겠다. Mahonian Number라는 잘 알려진 문제였다.

사전 지식이 있으면 별다른 장벽 없이 풀 수 있는 문제였고 실제로 대회 중에도 풀렸다.

F. 불순 분자 만들기

출제자는 L0TUS.

SUN인장 분자 만들기 / 직선형 분자 만들기의 정신적 후속작이다. 원래 이름은 무려 "반동 분자 만들기"였지만 논란의 여지가 있을 것 같아서 검열했다.

원래 풀이는 센트로이드도 나오고 뭔가 복잡해서 바라만 보고 있었는데, 간단한 HLD풀이가 있다길래 후다닥 달려가서 검수했다. 검수를 거치면서 난이도가 예상보다 낮아진 몇 안되는 문제. 실제로 대회 중에도 HLD 풀이가 많이 나왔다. 요즘 HLD 문제의 감정가를 잘 몰라서 플래를 가지 않을까 기대했지만 넉넉하게 다이아인 것 같다.

G. 메시라이브

출제자는 jhhope1 TAMREF.

어... 그러니까

C가 루비가 아니었고, D에 쿼리가 없던 시점에 선제 회의를 했고, 대회가 MAX=다이아 인 셋이 될 것 같아서 "루비 논문 문제를 내자!"라는 철학 아래에 출제한 문제다.

Planar $s$-$t$ cut으로 검색하면 여러 논문을 찾을 수 있다. 그 중에서 Reif (1983)의 $O(n\log^{2}n)$ 풀이를 보고 감동받아서 그대로 출제하기로 했다. 물론 풀이와 구현은 전혀 다른 문제였고, 나는 결국 정해 코드를 완성하는 데 실패했다.

imeimi2000과 jhhope1이 눈물겨운 풀이를 완성해주었고, 다른 검수진들이 열심히 Maxflow 알고리즘을 짜서 데이터를 공격해주었다. 문제가 천국과 지옥을 여러 번 왔다갔다했지만 다행히 잘 매조질 수 있었다.

H. SAT-2

출제자는 Diuven.

역시 셋에서 가장 쉬운 문제 중 하나로 의도되었다. 그런 것 치고는 문제가 무섭게 생기긴 했지만 다행히(?) 참가자가 그렇게 많지 않아서 걱정하는 일은 생기지 않았다. 가장 많은 clause를 참으로 하는 배정 찾기 같은 변종이 나오긴 했지만 그냥 satisfiability 문제로 최종결정.

풀이 생각하는 건 어렵지 않은데 짜려고 앉으면 별로 풀기 싫어지는 유형의 문제다. 그래도 다른 문제가 워낙 포악해서인지 검수도 솔브도 많이 나왔다.

I. 2차원 점과 쿼리

출제자는 Diuven, leesongun.

$D(U, V)$가 어떤 의미를 갖는지는 잘 모른다. 모종의 휴리스틱 알고리즘과 연관이 있는 듯. 무난한 자료구조 문제였고, 역시 난이도와 무관하게 많이 풀린 문제였다. 풀이는 로그랑 로그제곱이 있는데 굳이 갈라놓지는 않았다.