3rd Universal Cup 후기

까먹기 전에 뭐라도 씀

원래 아인타랑 같이 Season 3을 좀 했다. 친구없음 이슈로 거의 다 2인팀이었는데, 세미파이널 때는 잘하는 사람을 한명 데려가고 싶어서 정민찬이랑 같이 나갔다. 처음으로 해 본 3인팀이었다.

Semifinals

UCPC 세미나에서 강연을 하고 참가한 대회였고 뭔가 제대로 기여를 못 한 기억밖에 안 난다. 아마 한시간 넘게 늦참하고 엄청 피곤하게 쳤던 것으로 기억한다. 지금 제출창을 열어보니까 내가 짠 문제가 3개 있는데

• D는 내가 풀었던게 기억난다
• L은 아인타가 Directed MST로 환원하고 난 그냥 그 풀이를 그대로 짰던게 기억난다
• E는 뭔가 내 코드가 있는데 기억이 안 난다.. 내가 풀었을까? 누가 도와줬을까? 흠...

아무튼 난 버스만 탔고, 그래서 커트에 약간 미달했는데, 어쩌다가 추가 슬롯이 나와서 가게 되었다.

UCPC는 항상 새로운 팀을 꾸리고 한번쯤 팀연습을 하고 나갔는데 이번에는 팀연습을 한 적이 없다. 다들 멀리 떨어져 있어서..

5/7 ~ 5/8 - Arrival, Opening Ceremony

상하이 푸동 공항에서 리무진이 대기하고 있었다. 누워서 갈 수 있어서 아주 좋았다. 화웨이 사옥에서 대회를 하는데, 공항에서 2시간 거리에 있는 곳이었다. 시내에서도 아주 멀어서 상하이 관광을 하지는 못했음.

사옥에 딸려있는 호텔은 아침밥이 엄청 잘 나왔다.

Opening Ceremony에서 참가자 대표로 연설을 하지 않겠냐고 해서 했다. 아무 생각 없이 물었는데 당일 9시까지 대본을 달라고 해서.. 침대에서 대충 폰으로 끄적여서 냈다. 별 얘기 없고 짧은 연설이었다. 생각보다 반응이 좋아서 즐거웠다.

Ice-breaking Party는 trivia night 같은 거였는데 재밌었다.

5/9 - Huawei Challenge

ICPC처럼 전날에 Huawei Challenge라는 마라톤 대회를 한다. 마라톤 대회를 너무 싫어해서 주최 합의 하에 불참하는 방법을 알아볼까도 생각했는데, 쉽지 않아 보이기도 하고 어쨌든 상금을 준다고 해서 참가했다. 분위기상 불참하고 싶어하는 사람들이 나 말고도 꽤 되어 보였다. 스폰서 입장에서는 마라톤 대회가 훨씬 직관적이고, 알고리즘 대회 경험이 없어도 준비할 수 있어서 이해가 안 되는 것은 아니지만..

대회 문제는 무슨 ML 컨셉의 스케줄링 문제이고, 자세한 건 복잡해서 기억나지 않는다. 채점 형식이 대충 다음과 같았는데:

• Hidden test 100개가 있다.
• 제출하면 각 Hidden test에서 몇 점을 얻었는지 알려준다.
  • 각 테스트의 중요도가 동일하지 않다. 몇 개의 특정 테스트들이 훨씬 많은 점수를 준다.
• 각 제출의 점수는 100개의 테스트 점수 합이다.
• 최고 점수 제출이 최종 점수이다.
• 제출 간격 5분

단순한 알고리즘도 구현이 많아서 짜는데 오래 걸린다. 거기서 사실 스케줄링 우선순위를 튜닝만 해도 특정 테스트에서 점수 차이가 꽤 생기는데, 각 테스트마다 해당 테스트의 점수가 높은 우선순위가 모두 다르다. 온라인으로 스케줄링을 해야 해서 (즉 작업이 들어오면 당장 승낙/거절을 결정해야 해서), 각 테스트마다 우선순위를 최대화하는 스케줄링 알고리즘을 돌릴 수는 없다. 그리고 최종 점수는 각 테스트 케이스별 최대 점수 합이 아니라 제출별 최대 점수 합으로 계산된다. 그래서...

• 테스트 케이스의 입력을 해시한다.
• TL / ML / AC / WA 4가지 verdict로 해시의 특정 2비트를 채점 사이트에서 얻을 수 있다.
• 해시함수가 좋다는 가정하에 이걸 $O(\log n)$번 반복하면 WHP 모든 테스트케이스의 필요한 해시 비트를 다 얻을 수 있다.
  • 실제로는 6번 반복해서 99개의 서로 다른 해시를 얻었고, 충돌이 있는 두 테스트는 점수가 너무 낮아서 무시했다.
• 다양한 우선순위 함수를 채점 사이트에 제출해서 각 테스트가 각 함수에서 몇 점을 얻는지 시도해 본다. 한 8개 정도 시도했다.
• 채점 사이트를 복붙해서 저 정보들을 다 긁어오고, 긁어온 정보를 파싱해서 각 테스트 케이스마다 최적의 우선순위 함수를 매핑하는 코드를 작성했다.

제출 간격이 5분이라 저 전략을 좀 효율적으로 실행해야 하는 게 까다로웠다.

이거 말고도 여러 사람들이 다른 전략들을 시도해 봤는데, 저걸 유의미하게 이기는 전략이 하나도 없었다. 저 전략으로는 프리즈 전 기준 스코어보드에서 1등에 근접 (이기진 못함) 한 점수를 얻어서 수상권이라고 믿었다. 나는 구현이 많은 단순한 알고리즘을 짜고 도움이 안 되는 전략을 시도해 본 것 말고 한 게 없다. 전략이 고정된 시점부터는 책을 읽을까 하다가 집중이 안 돼서 포기했다.

끝나고는 러시아 사람들이랑 하나비를 했다. 나는 규칙만 아는 초보인데 이 사람들은 많이 해본 사람들인것 같았다. 많은 배움이 있는... 시간이었다.

여담으로 이날은 토요일인데, 오후 9시에 퇴근하는 사람들이 쏟아졌다. 난 996이 그냥 밈인 줄 알았다.

5/10 - Main Contest

메인 대회가 있는 날이었다. 사실 푼 문제 수가 적어서 딱히 쓸 것이 없지만 그래도 타임라인을 써보면:

• 0:00 - 0:17: ABCDE를 봤는데, E가 풀만해 보여서 좀 잡다가 그럴 듯해 보이는 풀이를 짜서 맞았다.
• 0:17 - 1:14: 정민찬이 suffix array가 필요한 K를 잡고, 아인타가 I를 잡았다. 난 그 사이에 다양하게 봤는데, G가 대충 짜면 될 수도 있겠다는 생각 정도를 했다. 일단 정민찬이 K를 먼저 짜서 맞았다 (1분 차이로 퍼솔을 놓쳤다. 엄청 빨리 풀었음). 아인타는 I를 내고 틀린 상태.
• 1:14 - 1:21: I가 틀린 이유가 long long 오버플로우라는 것을 깨닫고 ㄱ- int128으로 고쳐서 맞았다.
• 1:21 - 2:30 정도: 아인타는 H를, 정민찬은 M을 잡고 있었다. 나는 G를 잡고 있었는데, KD tree로 비비면 될 수도 안 될 수도 있겠다 정도로만 생각을 하고 있었다. 일단은 코드를 짜는게 그렇게 어렵지는 않아서 짰는데 WA가 나왔다. 코드 실수가 조금 있어서 고쳤는데 그 이후부터는 그냥 풀이가 틀려서 WA를 받는 것으로 보였다. 사소한 최적화를 할 여지가 많이 있어서 생각보다 오래 붙잡다가 아인타가 다른 문제를 보라고 해서 최종적으로 포기했다. 사실 1시간 넘게 잡는건 뇌절이고 진작에 나왔어야 하는게 맞다. 아인타랑 H를 얘기해보다가, 풀이가 나왔다고 해서 넘겨줬고, 정민찬은 M을 시도해보다가 잘 안 된 상태였다.
• 2:30 정도 - 3:46: 아인타는 H를 좀 잡다가 AC를 받았다. 난 G를 포기하고 나니까 남은 문제가 다 너무 어려워 보여서, 내가 뭘 하려고 하기보단 팀원을 돕는게 나을 거라고 생각이 들었다. 그냥 M을 읽었는데, 풀이가 빨리 나와서 정민찬이랑 얘기를 해보고 내 풀이를 짜기로 했다 (정민찬이 짠 코드가 있어서 코딩은 정민찬이 이어받음). 코드에도 버그가 좀 있고 풀이에도 구멍이 좀 있었는데 서로 왔다갔다하면서 봐주다가 M도 AC를 받았다. 나이스 팀워크였다.
• 3:46 - 5:00: 이 시점에 우리가 풀 가능성이 0 초과라고 생각했던 문제는 A, F, G였다.
  • F는 왜 틀린지 이해가 안되는 아주 간단한 그리디 풀이가 있었다. 이대로라면 0솔일수가 없을 거 같아서 DM을 짜두고 그리디 풀이를 돌렸는데, $m = 0$ 일때는 되는 게 맞지만 $m > 0$ 에서는 확실히 반례가 있는 풀이었다. 그 반례를 어떻게 고칠지는 잘 모르겠어서 금방 포기했다.
  • A는 아인타가 열심히 짜고 있었는데 결국 대회 끝날때까지 WA의 벽을 넘지 못했다. 실제 풀이의 방향은 아예 달랐다. 아인타랑 얘기하면서 비슷한 방향의 얘 기가안 나온건 아닌데, 그래도 돌아보면 대회 시간에 우리가 풀 가능성은 좀 적은 문제였던것 같다.
  • G는 내가 남는 시간동안 hail mary를 몇번 던졌는데 당연히 잘 안됐다.

끝나고 나서 주최랑 인터뷰를 진행했다. G번 문제의 이름이 "Art of Data Structures" 라서 Data structure mania인 내가 이 문제에 대해서 어떻게 생각하는지, 풀 수 있었을 것 같았는지에 대한 질문이 많았다. 흠.. 이게 KD-tree에 대해서 내가 아는게 많았으면 할 말이 많았을 수도 있는데, 아쉽게도 잘 아는게 없어서 재미있는 인사이트를 얹진 못했을 것 같다. 일단 나중에 들은 건 내 풀이는 통과하지 않는 게 맞고 (정해는 $O(\sqrt n)$인데 내 풀이는 $O(\sqrt n \log n)$ 이라고 한다. 난 $O(\sqrt n \log n)$ 인지도 몰랐다) 반례도 있다고 한다. 아오 그러면 왜 물어보는거야!!

반대로 풀 가능성이 0 초과인 문제는 따로 있었는데, 놀랍게도 D번 문제였다. 문제를 읽고 딱 떠오른 나이브한 생각들이 몇개 있었는데, 그냥 그걸 짜면 되고, 그래서 미러에서는 처음 솔브가 뜬 시점 이후 차례로 솔브가 쌓였다고 한다. 확실히 스코어보드에서 솔브가 있었으면 분명히 풀 수 있는 문제인 것 같았지만, 솔브가 없다면 (F처럼) 뭔가 틀릴 것 같아서 잡기 무서운 문제인 것 같다. 어차피 그랬으면 다른 팀도 풀었을 거고.

끝나고는 화웨이 오피스 투어를 시켜 줬다. 뭔가 가이드분이 약간 고압적인.. 이미지를 주셨는데, 그러거나 말거나, 5시간 대회가 끝난 이후라 듣지 않았던 기억이다. 저녁 밥은 뷔페였다. 되게 그럴듯하게 생겼지만 묘하게 실속이 없었다 ㅎㅎ... (그래도 온사이트에서 이 정도면 엄청 잘 준 거긴 하다. 유컵만큼 잘 챙겨준 온사이트가 없었다.)

화웨이 오피스에는 오피스 건물을 오가는 트램(!) 이 있다. 진짜 트램이고 ground crossing도 있다. foamers unite!! 화웨이 오피스의 외부 전경은 옛날 유럽 도시를 따라 해서 되게 특이했다. 약간 파주 영어마을의 느낌? 실제 내부 구성이나 호텔은 옛날에 IOI 국가대표/계절학교 교육을 했던 (지금은 사라진) 삼성전자 인재개발원과 비슷하다고 생각했다. 08년생 정민찬은 영어마을도 이해를 못했고 인재개발원도 이해를 못했다.

어제 러시아 분들이랑 하나비를 더 하고 해산했다. 정민찬은 다다스컵에 참가해서 센트로이드 (aka koosaga brainrot) 똥문제 (...) 를 풀고 있었다.

 

5/11 - Closing

첫 이벤트는 Conference였다. 일종의 세미나같은 거였는데.. 일단 Zac Friggstad가 approximation algorithm 관련해서 준비한건 좋은 발표였다. PS하는 사람들한테 approx algorithm이 어떤 것이고 왜 흥미로운지를 잘 설명한듯. Richard Peng은 shitposting이었는데 그래도 재미는 있었다. 나머지는 shitposting 미만의 무언가... 화웨이 챌린지는 개선이 어렵다는 걸 이해하는데 이건 음.. 난 할 말이 없으면 가만히 있는게 맞다고 생각한다. 스폰서 톡이 아니면 미리 슬라이드를 받아온 다음에 퀄리티가 낮으면 컷하고 빨리 끝내주는게 서로한테 좋지 않나 싶었다.

그 다음에는 화웨이 챌린지 풀이를 발표하는 세션이 있었다. 전략이 크게 다른 팀은 단 하나도 없었고, 최상위 두 팀은 약간의 추가 아이디어가 있긴 했다. 그 두 팀을 제외하고 거의 절대다수의 팀이 (1) 여러 우선순위를 시도해 보고 (2) 중요한 테스트 데이터를 어떻게든 분리해낸 후 그 테스트에 대해서 특별한 우선순위로 정렬하는 식의, 우리가 한 방식과 동일한 형태의 풀이를 시도했다. 다만 우리처럼 대놓고 똥냄새나는 전략과 코드를 짠 팀은 거의 없고 (4등 팀 제외), 나도 그 사실을 숨기지 않고 발표 세션에서 우리 코드의 역겨움을 포장 없이 보여줬다. 음~~ 많은 사람들이 내 풀이 발표를 듣고 웃어줘서 좋았다.

이후 등수 공개 시간이 있었다. 대회 직후 예상은 둘다 동메달 컷 근처 (컷은 챌린지 7등, 알고리즘 12등이다) 였는데 이것저것 알아보면서 메달에 더 가까울 거라고 예상했다. 실제로는 총 23팀 중 챌린지 전체 5등 (동메달, 2000EUR) 및 본대회 전체 10등 (동메달) 을 수상했다. 챌린지는 기대보다 훨씬 좋은 결과였고, 알고리즘은 기대보다 약간 좋은 결과였던 것 같다. 챌린지는 7등 안에만 들면 상금을 주고 본대회는 1등만 상품이 있는데, 이거 맞나... 싶긴 하지만 스폰서는 어쩔 수 없지..

마지막 뷔페는 좀 맛있었다.

진짜 너무 재밌었고 내년에도 또 참가하고 싶다.

쉿

끝!