cgiosy.dev
Reply Code Challenge 2023 - Teen Edition 본문
https://challenges.reply.com/tamtamy/challenges/category/coding_teen#about
3월 3일에 junseo가 웬 처음 보는 대회를 들고 여기 같이 해보자며 팀하자고 DM이 왔다.
귀찮아서 좀 고민하다가 상금을 봤는데, 1등 5000 유로 / 2등 2000 유로 / 3등 1000 유로씩 준다길래 덥썩 물었다. 온라인 대회에 이 수준이면 상당히 후한 축에 속한다.
대충 보니까 아웃풋 온리에 휴리스틱 대회 같아서 조금 불안했는데, 내가 아는 휴리스틱이라곤 '어떤 알고리즘'밖에 없기 때문이다.
무슨 이상한 가지치기나 애드혹 관찰을 섞은 컨스트럭티브, 플로우 어쩌구로 최적화해야 하는 게 아닌가 싶어 좀 쫄았는데... 다행히 이는 기우였음이 드러났다.
이전 대회들을 풀어보며 연습해야 하는 게 아닐까 싶었지만 결국 안 했다. 이대로 괜찮은 거 맞나? 란 생각이 들었는데 괜찮더라. :)
대회 이름답게 만 19세 이하인 사람만 참가 가능하고, 팀은 최대 4인으로 구성할 수 있다. 나와 준서 말고도 hibye1217이 팀원으로 있어서 한 명을 더 구할 수 있었다. (참고로 hibye씨의 블로그에도 후기가 있다.)
근데 난 내 나이 이하인 아는 사람 중에 휴리스틱 잘 할 만한 사람이 없었고 (jjang씨가 잘한다고 듣긴 했는데 친분이 없었다), 준서도 별 소식이 없어서 3인 팀으로 나갔다. 지금 생각해보면 한 명 더 구했어도 1등이나 2등을 했을 거란 보장은 없던 것 같아서 괜찮은 선택인 듯?
팀명은 준서가 지었다. 딱히 의미는 없다.
대회 시간은 한국 기준 [3월 10일 오전 00:30 ~ 오전 04:30]이었고, 5문제 대회였다.
시작할 때 하이바이가 A, 준서가 B, 내가 C를 잡기로 했다. 지금 보면 문제 선택도 꽤 운이 좋았던 것 같다.
내가 아는 유일한 휴리스틱 알고리즘, DLAS를 미리 준비해놓고, 혹시 랜덤 수 생성 속도가 발목을 잡을까 봐 커스텀 RNG 구현 (Wyhash에 이것저것 섞었다)도 준비해놨다.
대회가 시작되었다.
(시간은 대회 시작 이후 흐른 시간 기준이다.)
00:00 - 사전에 정한 대로, 각자 문제를 잡았다.
나는 C를 봤고, 문제를 요약하면 다음과 같았다:
C. W*H 격자에서 꽃 F개를 놓을 수 있는 칸 G개가 주어질 때, 꽃들 간의 최소 맨해튼 거리를 최대화하라.
W, H ≤ 150, F ≤ G ≤ 50
음... 뇌정지가 왔다. 거리를 고정하고 파라메트릭으로 잘 찾기? 아니면 맨해튼 거리에서 x+y x-y -x+y -x-y 부호 잘 쪼개서 뭔가 그리디하게 선택해보기? 아니면 DP 식을 잘 세워서 슥슥 처리해보기? 어느 쪽이든 쉽지 않아 보였다.
00:12 - B가 풀렸다. (junseo)
00:13 - A가 풀렸다. (hibye1217)
다른 팀원 둘이 연속으로 문제를 풀었다. 난 구현 시작은 커녕 풀이도 명확히 갈피를 못 잡고 있는데, 환장할 노릇이었다.
좀 고민하다가, 데이터가 약하다는 말들을 믿고 그냥 DLAS를 믿고 해보기로 했다.
...사실 뭘 한다기도 애매한 게,
3줄짜리 O(N^2) 최대 맨해튼 거리 계산 (O(N)에 되는데, 왠지 필요없을 것 같아서 대충 짰다)
+ 1줄짜리 무작위 꽃 위치 변경 (pos[rng(N)] = rng(M))
이렇게 5분만에 짠 다음 심호흡을 하며, 주어지는 데이터들을 00:20부터 하나하나 넣어봤다. 어...
00:27 - C가 풀렸다. (cgiosy)
당황스러울 만큼 빠르게 답이 수렴했고, 뭐 막히는 부분 없이 그냥 맞았다(...)
마지막 데이터는 답이 옳은지 판별을 안 해줘서 이대로 제출해도 되나 좀 고민했는데, DLAS 돌릴 때 제한을 10배쯤 늘리고 줘도 똑같이 나오길래 안심하고 냈다.
남은 건 D와 E였는데, 둘 다 쉽지 않아 보였다. 각각 내용은 다음과 같았다:
D. N × N 격자에 Q개의 보석이 흩어져 있고, 각 보석은 C가지 색 중 한 가지 색을 가진다.
모든 색을 하나 이상 포함하는 직사각형 중, 가로 × 세로 넓이가 최소인 것을 구하여라.
N ≤ 1500, Q ≤ 17500, C ≤ 52
E. N × N 격자의 각 칸에 임의의 높이를 가진 빌딩이 세워져 있다. 다음 정보들이 주어질 때, 각 칸에 세워진 빌딩들의 높이를 구하여라.
N ≤ 14
- N × N개의 각 칸에서, 인접한 8방향 칸에 있고 높이가 자신보다 큰 빌딩의 개수가 주어진다.
- N × N개의 각 칸에서, 동서남북 각 방향을 바라볼 때 높이가 자신보다 큰 '보이는 빌딩'의 개수가 주어진다. '보이는 빌딩'은 앞에 자신보다 큰 빌딩이 없는 빌딩만을 말한다.
D는 화려한 정사각형처럼 그냥 쉽게 쓱쓱될 줄 알았는데, 직사각형이라 생각처럼 잘 되지 않았다.
일단 빨리 짜서 되는 데까진 제출해놔야 페널티가 낮기 때문에, 하이바이가 투포인터로 우선 O(N^3 C) 및 O(N^3 lg N) 풀이를 시도했다.
00:58 - D가 35% 풀렸다. (hibye1217)
E는 뭔가 잘 하면 될 것 같이 생겼는데, 진짜 풀기 싫게 생겼다. 준서가
0이 처음으로 등장하는 위치는 그 행 또는 열에서 높이가 최대인 빌딩의 위치고, 이걸 기반으로 잘 분할해주다 보면 될 것 같다.
면서 복잡한 백트래킹뇌절풀이를 짜려고 하는 것 같았다.
근데 단시간에 코딩이 마무리될 것 같지도 않고 D로 가기엔 영 애매해 보여서 E에 한 번 DLAS를 박아보기로 했다.
N도 엄청 작고 휴리스틱이 되게 잘 돌아갈 것 같이 생기긴 했는데, 내가 그 이상의 무지성 코딩을 하고 있어서 좀 조마조마했다.
짜고 나니 진짜 문제에 주어진 설명 그대로 짜기만 한 수준이라, 뭔가 최적화를 해야 될 것 같은데? 싶었다.
그래도 우선 제출해서 맞을 건 맞고 얼마나 느린지 확인하는 게 먼저라고 생각해서 데이터를 넣어봤다. 어...
01:27 - E가 풀렸다. (cgiosy)
주어지는 데이터 다섯 개 중, 쉬운 거 세 개는 C에서의 경험에 따라 당연히 맞을 거라고 생각했었는데, 네 번째부터 갑자기 확 느려졌다.
'아... 그럼 그렇지...'하고 Ctrl-C를 눌러 정지시키려는 순간, 어? 답이 나왔다. 제출했다.
혹시? 하고 다섯 번째 데이터를 넣어봤다. 시간이 더 오래 걸린다.
'아... 그럼 그렇지...'하고 Ctrl-C를 눌러 정지시키려는 순간, 어? 답이 나왔다. 제출했다.
C번이랑 달리 정답 판별이 명확히 가능했기 때문에, 틀릴 가능성도 없었다.
당황을 넘어 황당할 지경이었으나 일단 D를 풀고 그 이후에 생각해보기로 했다.
D는... 쉽지 않았다. 휴리스틱 각이 보이긴 했지만:
- C와는 달리 N과 Q 제한이 훨씬 커서 휴리스틱이 훨씬 느리게 돌 것 같았고,
- E와도 다르게 답이 맞는지 직접 검증해볼 수 없었다.
즉, 마지막 데이터를 제출할 때 믿음 100%로 내야 한단 뜻이었기에, 휴리스틱을 쓰기엔 영 불안한 감이 있었다.
투포인터 기반 풀이는 준서와 하이바이가 열심히 고민하고 있었기 때문에, 난 대충 O(Q^2 C) 풀이가 되나 싶어 짜보았다.
...20분동안 짰지만 예제가 안 나왔다. 생각해보니 아주 기초적인 조건부터 엇나가고 있었다.
다름 팀원들이 거의 다 짜가는 것 같길래, 던지고 그냥 둘이 코딩하는 거나 지켜봤다.
이후, 준서가 O(N^3 + NQ) 풀이를 짜서 맞았다.
02:25 - D가 풀렸다. (junseo)
다섯 문제 올솔브긴 했으나 3등까지가 전부 올솔브 상태였기 때문에 4등이 되었다.
준서는 작년에 이어 또 4등을 하게 생겼다며 울분을 터뜨리고 있었고, 나 역시 '설마 이걸 한 등수 차이로 상금을 못 받나?' 싶어 좀 속상했다.
믿을 건 1 ~ 3위 팀에서 히든 데이터가 터지는 것밖에 기대할 수 없는 상황이었는데, 최종 스코어보드가 대회 종료 직후에 공개되기 때문에 1시간 30분을 추가로 기다려야 결과를 알 수 있었다.
(사실 대회 직후에 공개하는 거면 히든 데이터 있는 대회 치고 빠른 편이긴 하다)
나는 긴장돼서 잠을 못 자고 계속 깨어 있었고, 하이바이도 마찬가지였던 것 같고, 준서는 자러 간다...고 해놓고 잠이 안 온다며 돌아와서는 같이 결과를 기다리고 있었다.
그렇게 대회가 끝나 오전 04:30이 되자마자 사이트를 새로고침했다. 어라? 스코어보드에 변동이 없다.
'아... 그럼 그렇지...'하고 단념을 하려는 순간, 생각해보니 히든 데이터가 맞아서 점수가 올라가야 하는데 순위라면 몰라도 변동이 전혀 없는 건 말이 안 됐다.
그러니까, 아직 스코어보드가 업데이트되지 않은 상태였다.
떨리는 심정으로 3초마다 새로고침을 누르는 것만 2 ~ 3분째, 마침내 스코어보드에 변화가 생겼고, 그 결과는...!
원래 3등이었던 팀인 NobodyCares가 히든 데이터에서 터져 6등으로 내려가고, 우리는 하나도 안 터져서 3등으로 올라왔다!!
이제 상금인 1000유로를 받고 세 명이 나눠 333유로씩 챙겨가면 된다.
글 쓰는 현재 시점의 가치론 각자 46.8만원씩 받아가는 셈인데, 난 사실상 3시간동안 이상한 코드만 짜고 놀았으니 놀면서 시급 15만원을 번 셈이 아닐까? 아니면 말고...
팀원 둘 다 PS를 잘 하는 친구들이라 버스를 타는 게 아닐까 걱정했는데 다행히 내가 충분히 기여를 했고, 결과가 좋아서 만족스럽다.
내년에 한 번 더 Teen에 참가해서 날먹하고 싶지만 조만간 만으로 20대에 접어드는 늙은이라 참가가 불가능하다 흑흑
Standard에 참가해볼까? 싶은데 아무래도 Teen에 비해 훨씬 경쟁이 아주 치열해 보여서 참가한다고 해도 재미로만 할 것 같다.
재밌는 대회 열어준 Reply Challenges에게 고맙다는 말을 남기며 글을 마친다. ;)