Google Hash Code 2020 대회 (간단한) 후기!

작년의 파이널 라운드 진출팀이었지만, 올해는 예선 121등, 한국 4등으로 대회를 마무리하게 되었습니다. ㅠㅠ

새벽이라 좀 정신 없긴 하지만, 데이터별 공략을 간단히 적어보도록 할게요!

(혹시 나중에 더 풀어보실 생각이 있으시다면 미리 spoiler alert!)

 

A. example

pdf 파일에 있는 데이터를 그대로 출력하면 16점이 나오지만, 4번 책이 포함되도록 순서를 잘 조정하면 이 데이터에서 얻을 수 있는 최대 점수인 21점을 받을 수 있습니다. 

 

B. read on

데이터가 매우 단순합니다! 겹치는 책도 없고, 도서관마다 책 수도 똑같고, 다른 것은 signup time 뿐입니다. 그러므로 signup time이 작은 순서대로 출력하면 가능한 최고점인 5,822,900점을 받을 수 있습니다.

 

C. incunabula

이 데이터는 shipping size가 터무니없이 커서, signup만 하면 모든 책을 챙길 수 있습니다. 적절한 기준에 따라 Greedy하게 library를 고르는 것만으로도 5,689,502점을 받을 수 있었습니다. 대부분의 최상위권 팀들도 이 근처의 점수를 받았습니다. 저희 팀이 쓴 기준은 (추가되는 점수)/(signup time)이었고, 다른 library를 추가할 때마다 추가되는 점수를 실질적으로 반영하여 다시 산정하였습니다. 이러한 update의 관리는 c++의 priority_queue 등으로 깔끔하게 처리할 수 있습니다.

 

D. tough choices

데이터 이름이 암시하듯, 사실 이 데이터는 두 library 중 하나를 고르는 선택의 연속입니다. 데이터를 잘 관찰해보면, 2k번 library와 2k+1번 library가 책을 하나씩 공유합니다. 그리고 이 책들은 그 둘에서만 등장하죠. 나머지 책들은 모두 세 번씩 등장합니다. 30000개의 library, 각각의 signup time 2, 그리고 deadline 30001. 이 수들이 갖는 의미는, library를 15000개 고를 수 있다는 것이고, 만약 만점을 받을 수 있다면, 그 데이터는 2k번 library와 2k+1번 library 중 정확히 하나만을 포함할 것입니다. 그래서 2k번 library와 2k+1번 library 중 책이 더 많은 쪽을 일단 골라봤습니다. 그 자체로는 만족할 만한 점수가 나오지 않았지만, 상태를 flip하며(2k번이 골라졌었다면 그걸 해제하고 2k+1번을, 반대쪽도 비슷하게) 더 좋은 쪽으로 선택하도록 했습니다. 그 결과 5,043,025점을 받았습니다. 참고로 이 문제의 이론상 만점은 65*78600=5,109,000점입니다. 최상위권 팀들 중에는 510만점을 넘긴 팀들이 몇 있었고, 이 팀들은 데이터의 특징으로부터 추가적인 관찰을 했습니다. 둘 중 하나를 고른다는 것을, p나 ~p 중 하나를 고른다는 걸로 생각하는 거죠. 그러면 이 문제는 78600-15000=63600개의 clause와 15000개의 variable로 이루어진 3-SAT 문제입니다. 3-SAT solver를 이용하면 510만점 이상의, 거의 만점에 가까운 점수를 얻을 수 있다고 합니다.

 

E. so many books

이 데이터가 최상위권과 상위권을 가르는 데이터가 되지 않았나 싶습니다. 정말 별 방법이 다 있었고, MCMF부터 이상한 hyper-parameter 조작까지(<-이게 저희 팀이었습니다) 다양한 방법과 다양한 점수가 있었습니다. 최상위권의 점수는 520만점 정도였지만 저희 팀은 이 데이터에서 5,095,422점을 내는 데 그쳤습니다. 이 부분이 가장 아쉽네요.

 

F. libraries of the world

이 데이터도 E만큼은 아니지만 팀별로 점수 차이가 조금 났었습니다. 넣을 수 있는 library의 수가 그렇게 많지 않다는 사실로부터 접근하면 여러 경우들을 잘 시도해보는 것으로 다수의 팀들이 5,348,248점을 받았습니다. 저희 팀은 5,317,660점을 받았네요.

 

이렇게 저희 팀은 26,968,350점을 받았습니다. 한국에서는 78-9 팀이 27,070,220점으로 가장 높은 점수를 받았고, 전체 순위도 38등이라 사실상 월드 파이널 진출이신 것 같습니다! 아직은 모르긴 하지만 미리 축하드리고, 4월 25일(한국 시간으로는 하루 뒤일 수도 있습니다만)에 있을 월드 파이널에도 많은 관심 가져주시면 좋겠습니다! 또, 앞으로도 한국 팀들이 더 선전하여 내년에는 더 많은 한국 팀을 월드 파이널에서 볼 수 있었으면 좋겠네요!