Google Hash Code 2020 후기

Google Hash Code 2020 (https://codingcompetitions.withgoogle.com/hashcode) 후기.

ICPC 같이 뛰었던 팀 Little-Piplup에 현재 병특 중인 dlwocks31을 영입(?) 해서 4인팀인데, Dlwocks31이 3명보다 구현이 훨씬 좋아서 확실히 팀 전력이 보강된 느낌이 들었다. 4인 팀으로 ICPC 같은걸 뛰었으면 더 잘 했을것 같기도...

 

Team Little Piplup : Coffeetea Diordhd Dlwocks31 Gratus907 

 

Hash code는 일반적인 ICPC / OI 류 대회와는 다르게, NP 문제 같은 뭔가를 가지고 최대한 많은 점수를 긁는 방식으로 치뤄지는 대회이다. 유사한 걸로는 Marathon Match 같은게 있다던거 같은데 이쪽은 해본적이 없어서 사실 어떤 식인지 잘 모르겠다. 

 

데이터의 특징을 파악하는 것도 중요하고 (미리 입력 데이터가 모두 공개되어 있어서, 데이터의 특징을 Exploit 할 수 있다) 적당한 상수 조절 / Simulated Annealing 같은 소위 PS의 '추한 테크닉' 들이 약간 정석인 대회라고도 할 수 있을듯.

 

작년보다 2배 정도 Participant 숫자가 늘어났는데, 1만여 팀 중 468등 (한국 13등) 의 성적을 거뒀다. 연습할때에 비해 성적이 막 잘 나온 것은 아니지만, 솔직히 뭔가 이보다 더 잘했을 방법이 있는거같지는 않고 우리는 할 수 있는 만큼은 했다는 느낌이 든다.

---

문제 설명

• 몇 개의 '도서관' 이 있고, 각각에는 어떤 '책' 들이 잔뜩 들어 있다. 예를 들어, 3번 도서관에는 19번, 20번, 102번, 301번 책이 들어 있다는 식의 정보가 주어진다.
  
• 각 책 별로 이 책을 '스캔' 하는데 성공했을 때 점수가 몇 점인지, '책의 점수' 가 주어진다.
  
• 도서관에서 책을 '스캔' 하기 위해서는, '도서관 등록' 을 먼저 해야 한다. '도서관 등록' 에 걸리는 날의 수는 각 도서관마다 다르며, 입력으로 주어진다.
  
• 한번에 한 도서관만 '등록 작업' 을 수행할 수 있다. 즉, 0~2일차에 0번 도서관을 등록하고 있다면 그 다음에 2번 도서관을 등록하고 싶다고 할 때, 3일부터 등록을 시작할 수 있다. 
  
• 도서관은 '등록' 한 다음 날부터 하루에 $M$권씩 ($M$은 도서관마다 주어진다) 책을 스캔할 수 있다. 당연히 그 도서관이 가지고 있는 책만 스캔할 수 있다. 즉, 0~2일차에 0번 도서관을 등록했다면 3일차부터 0번 도서관은 $M_0$ 권씩 책을 스캔할 수 있다.
  
• 한 책을 중복해서 여러번 스캔하더라도 점수는 한 번만 계산된다.
  
• $D$일이 지나서 등록되는 책은 점수에 반영되지 않는다.
  

---

시작하고 나서 바로 생각나는 관찰들을 몇 개 생각해 보면,

• 일단은 도서관의 등록 순서를 먼저 어떤 기준에 따라 정해야 한다. 즉, 도서관의 점수를 정적으로든 동적으로든 계산하는 방법이 필요하며, 도서관을 어떤 기준에 의해 정렬해서 가지고 있어야 한다.
• 각 도서관별로 책을 어떤 순서로 등록할지에 대한 기준을 정해야 한다. 
• 이때, 점수를 받을 수 있는 날짜가 모자라서 최대한 점수를 뽑아내고 싶은 상황이라면 점수가 높은 책부터 밀어넣고 싶다는 것은 당연하고,
• 다른 도서관에서 이미 등록한 책은 중복해서 등록하고 싶지 않다. 전혀 도움이 되지 않으니까. 

이정도 관찰을 가지고, 일단은 시간에 따라 각 도서관의 행동들을 시뮬레이션하는 방법으로 가기로 했다. B 데이터의 특징상 무조건 등록시간만 고려하는게 이득이었다는게 확실했으므로, 일단 Sorting 하는 함수만 바꾸면서 시도할 수 있게 Generic한 그리디 알고리즘을 먼저 구현하려고 시도했고, 구현력이 가장 좋은 dlwocks31이 이 구현을 맡았다.

 

여러번 채점을 받는 오버헤드가 엄청 크고, 후반에 Simulated Annealing 이나 상수 조정 (Hyperparameter Tuning) 같은걸로 몇만점 더 뽑으려면 채점을 즉시 받고 싶으므로, 나는 일단 문제 이해도도 높일겸 grader를 파이썬으로 구현하기 시작했다. Grader 구현을 우리가 할것인지는 문제 복잡도나 여러 요인들에 맞춰 정하기로 했었고, 지난 해시코드 문제들 중 단순 그리디 구현이 끔찍하게 어려운 문제들의 경우 Fallback을 위해 나랑 dlwocks31이 같은 그리디를 따로 짜는 방법도 고려했었는데 이번 문제의 경우 그럴 필요는 없어 보였다. 그동안 diordhd 랑 coffeetea가 문제에서 유용한 관찰을 더 뽑아내고, 특히 data의 특징을 찾는 작업을 coffeetea가 맡았다. 

 

구현에 대한 고민 + 실제 구현 + 체커 돌려보기 + 등등을 해서 첫번째 유의미한 제출을 시도한게 대략 4시 쯤 (시작 1시간 15분 후) 였고, 이때 E에서 점수가 박살났다. (188만 점) 상위권 팀들이 2500만~2700만점 정도를 받는걸 보면 일단 B~F는 500만점 이상씩 뽑아낼 수 있는게 맞는거 같아 보였고, 왜 E가 박살났는지 전혀 이해를 못 했지만 아무튼 코드 튜닝을 시작했다. 

 

• 남은 책들 중, 오늘 당장 이 도서관을 등록했을 때 앞으로 뽑을 수 있는 점수가 가장 큰 도서관을 매번 Dynamic하게 찾아 가면서 등록한다.
• 책의 희소성을 고려해야 하지 않을까?
• 점수가 큰 도서관이라도 등록시간이 너무 길면 손해니까, 등록시간 $T$에 대해 $T^{0.5}$ 같은걸로 나눠주면 좋지 않을까?

대충 이런 대화들 / 제출들이 오가면서 이후로 5시까지 1시간 동안 3~4백만점 정도를 더 뽑았다. 그래도 E의 점수가 260만점 정도로 망한 상황에서 약간 멘탈이 흔들렸는데, 내가 상수조정 하다가 정렬에 이상한 점을 발견했다. 

 

정렬하는 기준에서 양쪽의 score / (책 희소성 의 k제곱) 을 비교하고 $k$를 조정하려고 했는데, 실수로 양쪽에 다른 $k$를 썼는데 점수가 100만점정도 높아지는걸 보고 뭔가 이상하다는 생각을 했고, 그제서야 diordhd가 책을 반대로 정렬하고 있다는 사실을 찾았다. (어차피 도서관을 등록하고 나면 책을 다 스캔할 수 있는 다른 테캐에서는 도서관에 있는 책을 어떻게 정렬해도 티가 안 났었다) 이걸로 E 점수를 470만 점 정도까지 올리고, 이후로는 1시간 동안 미친 상수조정만 반복했다. 

 

마지막에 F와 E에서, 구현에 뭔가 실수가 있는지 숫자를 잘못 썼는데 점수가 오르는 현상을 발견했다. 막 큰 차이는 아니고, 그 숫자를 1정도 더 바꾸면 점수가 반토막나는걸 보면 이상한 특징이 있거나 구현에 약간 실수가 있는 것 같은데 뭔지 찾을 시간은 없어서 아무튼 틀린게 확실해 보이지만 점수가 높은 코드를 반복 제출해서 한 5만점정도를 더 벌었다. 이게 대회냐;;;

---

ICPC보다 (시간이 훨씬 이상하지만) 오히려 재밌었던 점도 있는 것 같다. 점수 긁는것도 재밌었고... 가끔 마라톤매치에 참여해 보는것도 괜찮겠다는 생각이 들었다. 머신러닝 / 최적화 / SA 같은 배울 것도 많고...

약간 단점이라면, 코드를 짜는 우리도 잘 이해를 못하는 상수튜닝 (왜 1.2가 1.5보다 낫고, 1.1은 다시 점수가 떨어지는지 등등...) 에 의해 점수가 달라지는 대회라는건...흠... 어떤 수학적인 납득할만한 근거를 가지고 (그게 데이터에 의한 것이든, 문제 자체의 조건에 의한 것이든) 상수 결정이 가능하고 그 근처로 (+- 얼마 정도) 조정하는 그런 느낌으로 대회를 치를 수 있었으면 더 좋았을 것 같다. 아마 뭔가 근거가 있는데 우리가 모르는 거겠지만 ㅋㅋㅋ

 

별개로, 우리가 생각하지 못한 두가지가 더 있음을 끝나고 다른 사람들을 통해 알게 되었다.

• D번의 경우, 우리는 '책이 조금 겹친다' 라고만 생각했는데, 이걸 정확하게 분석하면 2권씩 있는 책이 몇개~3권씩 있는 책이 몇개 이런 식으로 분석할 수 있다고 한다. 이를 이용해 3-SAT 문제로 환원하고, 이걸 이용해서 뭔가 근사 3SAT 알고리즘 같은걸로 긁을 수 있는 것 같다. 잘 모르겠다 (1)
• E번에서 겹치는 책들을 단순 그리디가 아닌 MCMF로 최적화하면 20~25만점 정도를 더 얻는 것 같다. 이 점수가 대략 우리랑 진출권레벨 팀들 간의 차이인 걸 보면, MCMF 최적화가 정말 진출을 위해 요구되는 능력이었던것 같은데 일단 우리팀은 이것도 이해하는데 실패했다. :( 잘 모르겠다 (2)

이런 요소들을 생각하면 뭐 그냥...딱히 앞서 Whining 했던 부분은 별로 의미가 없는 것 같다. 저런 상수조정 등등이 500등인지 1000등인지를 가를 수는 있지만 그걸로 최상위권이 결정되는 그런 느낌은 딱히 아닌 것 같고, 어차피 약간 Special something 이 필요한 거라고 생각하면 좋은 대회라고 생각한다. :) 아무튼 재밌는 경험인듯.