Google Hash Code 2021 : Global #211 (2%) 후기

이 글은 올해 해시코드 대회 과정에 대한 후기이고, 준비 과정은 앞 글(링크)에 있습니다.

• 결과
• 문제 설명
• 데이터 설명
• 대회 전략의 실패
• Algorithm : Demand - Proportional - Scheduling
  • Fine Tuning
• 결과 / Discussion
• 앞으로를 위해

결과

A - An Example       2,000
B - By the Ocean     4,566,842
C - Checkmate        1,300,355
D - Daily Commute    1,574,469
E - Etoile           716,984
F - Forever Jammed   1,417,038
TOTAL SCORE          9,577,688

Global rank #211 / 9,000+ teams

Korea rank #11

문제 설명

• 교차로, 도로, 차량 들이 주어집니다.
• 도로 들은 그래프에서 방향 있는 간선 입니다. 교차로 에서 교차로 로 이어져 있고, 길이 가 있습니다.
• 교차로 는 그래프에서 정점 입니다. 교차로에는 신호등 이 있는데, 특정 시점(초)에는 정확히 1개의 incoming edge 에만 초록불이 켜져 있어야 합니다.
• Incoming edge 에 초록불이 들어와 있다면, 그 교차로의 그 도로에 서 있는 차량들 중 1초에 1대씩만 그 교차로에서 출발하는 간선들 중 하나로 이동할 수 있습니다.
• 차량 들은 가고 싶은 경로가 주어집니다. 경로는 간선들의 순서로 주어지고, 시작점은 첫 간선의 ending intersection에 서 있는 것으로 주어집니다. 차량들은 1초에 1씩 이동하는데, 교차로를 만나면 내가 지금 서 있는 도로의 초록불이 켜질때까지 기다립니다.

예를 들어, 교차로 A에서 B로, B에서 C로, A에서 C로, C에서 D로 도로가 있다고 가정해 봅시다. 여기서 차량 1이 A-B에서 출발, 차량 2가 A-C에서 출발한다고 생각해 봅시다. 차량 1이 B 앞에 서 있을 때, B교차로는 (A-B) 도로 외의 다른 incoming 도로가 없으므로 여기에 초록불을 켜 주면 됩니다. 이러면 교차로를 바로 지나쳐서 B-C 도로로 올라탈 수 있습니다.

위 예시에서 C 교차로는 B-C 간선과 A-C 간선 두개의 endpoint입니다. 이때, B-C 간선에 초록불이 켜 있다면, 앞에 차가 없더라도 A-C 간선에는 빨간불이 켜 있으므로 A-C간선의 끝에서 C교차로를 바라보는 차량은 통행할 수 없습니다.

또한, 차들은 겹치지 않는다는 점도 (1초에 차량은 1대씩만 통행합니다) 중요합니다.

• 신호등 은 교차로마다 설치되어 있는데, incoming edge들을 도는 사이클 형태로 신호등 스케쥴링이 가능합니다.

• 신호등 스케쥴링 이란, 위 예시를 다시 빌리자면 C교차로에서 다음과 같이 스케쥴링합니다.

  • {B-C, 2} {A-C, 1}
  • 이 표현의 해석은 B-C 간선에 2초간 초록불을 켜주고, A-C 간선으로 1초간 바꿨다가, 다시 B-C 간선을 2초간 켜주는 식으로 반복한다는 뜻입니다.
  • 즉, 사이클로만 돌릴 수 있고, 세부적으로 신호등을 조작할 수는 없습니다. 대충 생각해 보면, 교차로의 각 도로들을 위해 신호를 켜주는 순서와 그 비중을 조정할 수 있는 것입니다.

Hashcode 문제는 여기서 신호등 스케쥴링 사이클 을 만드는 문제입니다. 다른 모든 것은 주어집니다.

점수는, 제한 시간 내에 도착한 차의 개수 에 따라 점수를 받으며, 빨리 도착할수록 보너스 점수가 있습니다. 타임아웃 난 차량은 0점입니다.

데이터 설명

데이터는 총 6개로 구성되어 있습니다. A는 예제고, 나머지 데이터들은..

• B : 그냥 평범한 데이터입니다. 큰 특징은 없습니다.
• C : 격자형태로 도로가 구성된 데이터입니다.
• D : 시간이 굉장히 빡빡해서, 조금만 지체해도 모든 차들이 타임아웃납니다. 몇개의 허브정점들과 다수의 정점들이 포도송이처럼 연결된 형태입니다.
• E : 모든 정점들이 하나의 허브에 연결된 STAR 형태의 그래프입니다. Etoile는 프랑스어로 별이라고 합니다.
• F : 교차로가 매우 많고, 차량들이 교차로에 Stuck하는 데이터입니다.

대회 전략의 실패

• 구현 복잡도가 높아서, 체커를 작성하지 못했습니다. 저 혼자 대략 1시간 정도 시간을 써 보고, 포기하기로 결정했는데, 그 이유는
  • Coffeetea와 DHDroid가 제시한 알고리즘은 기본적으로 차의 운행을 Simulation해야 합니다. 만약 그런 알고리즘을 실제로 코드로 옮긴다면, Simulation을 통해 점수를 연산하는 별도의 체커 없이도, 코드에 시뮬레이션을 내장할 수 있습니다.
  • 더이상 체커를 잡기에는 시간이 너무 아까웠기 때문입니다.
• 마찬가지 이유로, dlwocks31이 시뮬레이션 코드 작성에 실패했습니다. 대회 후반부에는 시뮬레이션 비슷한게 돌아갔는데, 정확히 성공했는지 여부는 잘 모르겠습니다. 예상 점수와 실제 점수 간에 조금의 오차가 있는 것으로 보아 어딘가 문제가 여전히 있는 것으로 보입니다.
• Coffeetea / DHDroid 듀오의 데이터분석 및 구상은 탁월했습니다.
• 결과적으로 거의 이 두명이 대회를 캐리해 버렸습니다. 저랑 dlwocks31은 계속 고통받은 대회였습니다 :(

Algorithm : Demand - Proportional - Scheduling

앞서 신호를 켜주는 순서와 그 비중을 조정할 수 있다 라고 했는데, 저희는 그중 비중에 집중했습니다. 구체적으로는, 시뮬레이션을 돌리면서, 각 차량들이 특정 교차로의 특정 도로에 잡혀있을 때마다, 그 정보를 report 합니다.

이런 정보들을 모아둔다면, 교차로 X에서 도로 a, b의 total jam-time을 계산할 수 있고, 이 total jam-time이 높은 도로의 신호를 더 많이 열어 줄 필요가 있음이 자명해 보입니다. (거기 잡혀있는 차가 많으니까, 더 넉넉하게 열어 주는 것입니다) 따라서 이 DEMAND 에 비례하는 (또는 뭐 적당히 루트라던가…) 시간가중치를 주어 사이클을 돌리는 방식입니다.

Fine Tuning

위 알고리즘에서 튜닝할 수 있는 아이디어는 제가 추가로 들어가고 나서 잠깐씩 Discuss하면서 계속 발전시켜나갔습니다. 대표적으로 이런 것들이 있습니다.

• $t = 1$ 에서의 demand와 $t = 1000$에서의 demand의 가치는 동등하지 않다고 보았습니다. 둘중 하나라면 초반이 빠른 편이 유리하기 때문인데, 똑같이 1초만큼 빨라진다면 초반에 빨라져야 빠르게 차들이 줄어들어서 후반이 덜 막히기 때문입니다.
• 구현하지는 못했지만, 본래 계획에는 실제 시뮬레이션을 거친 다음, 아깝게 시간이 지나 통과하지 못한 차들의 demand에 더 큰 가중치를 부여하는 방안이 있었습니다. 이 방안은 (테스트해보지 못했지만) 충분히 의미가 있었을 것이라고 보입니다.
• 가중치 $w = f(d)$ 는 demand 개수에 대한 함수입니다. $f$를 조금씩 바꾸면서 튜닝할 수 있습니다.

이 모든 튜닝의 결과가 맨 위에 기록된 결과입니다.

결과 / Discussion

대회가 끝나고, 바로 근처에서 대회를 치른, 평소 잘 아는 사이인 서울대학교 @channel 팀과 간단한 Discussion을 했습니다. 그 팀은 2018년도에 Hashcode World Final에 진출했던 팀으로, 이번 대회에서는 저희보다 20만점 정도 높은 점수로 40등의 높은 성적을 거두었습니다. 서로 성적을 보는 순간 놀랐는데,

• @channel 팀은 D에서 240만점 가까이 (저희보다 80만점 높은) 성적을 거두었습니다.
• 반면, F번의 점수는 저희 팀이 60만점 정도 높았습니다. 서로 D와 F를 보며 어떻게 한 거냐고 물으며 디스커션을 진행했는데, 이 팀에게 들은 방법은 (제가 올바르게 이해했다면) 대략 다음과 같습니다.
  • D번의 경우, Degree가 평균적으로 매우 작습니다. 따라서, 굳이 긴 시간동안 한 길을 열어주기보다는, 1초씩 바로바로 바꿔주더라도 특정 도로의 대기시간이 그렇게까지 길지 않으므로, 모든 신호 사이클은 1초로 고정합니다.
  • 그러나, 어떤 순서로 사이클을 돌릴지는 중요합니다. 이를 실제 시뮬레이션을 진행하면서, 해시테이블에 기록하는 식으로 각 intersection마다 어디에 대기가 걸리는지를 파악해서 사이클의 순서를 최적화합니다.
  • 결론적으로, 신호를 켜주는 순서와 그 비중을 조정할 수 있다 에서, 비중 을 버리고 순서 에 집중한 형태의 솔루션으로 보입니다. 일종의 Dynamic Cycle Ordering 이라는 이름을 붙일 수 있겠네요.
• 1등팀의 점수는 1050만 점 정도고, 1000만점을 넘으면 10위권 팀이었습니다. 결과적으로, 저희의 Demand-Proportional Scheduling 과 @channel의 Dynamic Cycle Ordering이 상호 보완적인 방법이며, 저희가 잘 푸는 케이스 (F) 와 @channel팀이 잘 푼 케이스 (D) 의 max점수를 취하면 1030만 점 정도임을 볼 때, 최상위권 팀은 이 두 가지 전략을 각각 코딩해서 제출했거나, 두 전략을 절충한 방안이 있거나, 또는 우리 모두 생각지 못한 Novel한 방법 (있을지는 모르겠습니다만) 일 것으로 보입니다. 두 가지 모두 어떻게 보면 자연스럽기도 해서, 두가지 모두 구현하는데 성공했으면 월클팀이 아니었나 싶습니다.

앞으로를 위해

해시코드류 대회는 사실 저희에게는 매우 재밌기도 하고, 이런 평소에는 생각하기 어려운 것들을 공부하는 기회이기 때문에 나름대로 팀으로써 공부하는 즐거움이 있습니다. 그래서 아마 (적어도 내년에는) 같은 팀으로 나갈 예정인데, 그때를 위해, 또는 다른 프로그래밍 대회를 위해서라도 이번 대회를 통한 교훈을 기록해 두려고 합니다.

• 결국은 구현력이 중요합니다. 특히 Hashcode가 매년 극도로 구현이 빡세지고 있고, 제한시간 4시간 (실제로는 15분동안 스트리밍으로 시간을 날리기 때문에 3시간 45분) 동안 문제의 기본적인 그리디 솔루션을 제시하기조차 어려워지는 현상이 가속되고 있습니다. 결국 이번 대회의 최상위권 전략 중 하나는, Demand-Proportional Scheduling 과 Dynamic Cycle Ordering 이라는 전혀 결이 다른 두가지 방법을 모두 코딩하는데 성공하는 것인데, 이를 위해서는 적어도 2명 이상의 팀원이 안정적으로 솔루션을 코드로 옮기는 능력이 필요합니다.
  • Dlwocks31이 우리 중에서는 구현을 가장 잘하지만, 나머지 3명의 구현력이 현저히 떨어지는 것은 굉장히 큰 결점입니다. 이를 보충하기 위해, 최대한 저희가 (특히 그나마 C++ 구현력이 나은 제가) dlwocks31을 보조해주기 위해 이번에는 파일을 나누어 GIT을 써보기도 했는데, 결국 대회가 끝나고 느낀 것은 이 모든 방법은 부족한 구현력을 메워보려는 시도였고 근본적인 해결책이 되지 않는다는 것입니다.
• 아이디어 캐칭 이후, 이걸 바로 코드로 옮겨서 테스트해봐야 합니다. 실제로 Coffeetea가 제시한 많은 휴리스틱한 방법들의 반도 채 쓰지 못했는데 이것도 결국 시도해봐야 아는 문제입니다.

작년에도 비슷하게 했던 말이지만, 대회 자체는 해보면 정말 재밌습니다. 솔루션 깎는 과정이 뭔가 다른 PS대회랑 굉장히 이질적이면서도 점수 올라갈때 짜릿한 그런 맛이 있는데, 구현보다는 조금더 최적화 맛이 나는 대회가 되었으면 하는 기대가 있지만 반대로 가는것 같습니다.

여전히 작년 Library처럼, 추한 테크닉으로 가르더라도 결국 진출권은 SAT과 MCMF최적화가 가르는 메타가 옳다는 믿음에는 변화가 없습니다. 그에 비하면 이번 대회는 진짜 구현컵인것 같아서 조금… 하지만 작년에도 그랬듯이, 까보면 누군가 이상한 최적화를 들고왔을수도 있으므로 아직 예단하지는 않으려고 합니다.

구체적으로 DEF중 하나에 뭔가 플로우로 최적화할수 있는게 있을거라고 의심하고 있습니다. 그래프에서 뭔가 지나가고 어쩌고 하는게 딱 플로우 냄새가 나서요…

PS를 즐긴다면 그냥 색다른 느낌으로 즐길만한, 그렇지 않고 원래 Data Science 나 Optimization쪽에 관심이 있더라도 한번쯤 해볼만한 대회라고 생각합니다. 내년에도 파이팅!

Little Piplup 수고 많았어요 :) + @channel팀의 월파 진출을 응원하겠습니다 :)