9. 8

• Euler's Formula를 planar graph에서 vertex, edge, face의 관계로만 알고 있었는데 본래는 더 대단한 걸 증명했던 거구나.. polyhedron을 평면상에 투사해서 밑면을 제외하면, 평면상의 그래프로 v-e-f'=1이 성립한다. 결국 polyhedron상에서는 v-e-f=2. 해당 상수는 도형의 종류에 따라 특정된다.
• 어휴 <Bear and Cavalry>가 도저히 코딩이 안된다ㅡ_ㅡ어떡하지 정말.. 꼭 다음에 또 코딩해 봐야지.
• 그저 내 맥에어에 <bits/stdc++.h>가 없길래 homebrew로 gcc4.9 인스톨을 시켰는데 30분째 돌아가고 있다. 이거 언제까지 컴파일이 돌아가는거지-_-;
• CF Div.1을 지금까지 participate하면서 대회 시간 안에 D,E는 읽어본 적도 없다. 이 상태가 몇달이 지나도록 계속되는 걸 보면, C와 D사이엔 뭔지모를 quantum jump같은 게 있는 것 같다. practice를 할 때도, C까지는 코딩에 그렇게 헤매지 않는데, D-E는 어려운 알고리즘 + 복잡한 자료구조가 결합된 문제가 많기 때문에 정확한 구현에도 종종 애를 먹고, 심지어는 저놈의 <Bear and Cavalry>처럼 며칠을 끙끙 앓기도 한다ㅠㅠ 이 구간에서 얼마나 고생을 해야 되는건가..
• <Sign Posts>는 Contest에 어떻게 Randomized Algorithm이 활용되는 지 보여줬다. 지금까지 Random을 활용하는 건 Treap에서 정도, 실제 해를 구해내는 데에는 써보지 않았었다. 하지만 이렇게 선택해야 하는 집단에 비해(5개) 모집단이 굉장히 클 때( \(10^5\) ) 어느정도 증명을 하고나면 쓸만한 확률이 나오게 되는 것 같다.