one day left
요즘 내 멘탈청량제의 역할을 맡아주는 ..ㅠㅠ 26일은 CERC 2010을 돌았는데, 괜찮은 문제가 많아서 좋았다. 하지만 이것들을 나대로 풀어내야 내것으로 만들어낼 수 있을텐데ㅠ_ㅠ..
domination에 관련한 굉장히 깔끔하게 정리된 사이트를 발견했다. wow..예전 KTU camp Day5의 문제는 결국 Biclique를 구하는 문제였는데, 이건 결국 complement graph상에서의 maximum independent set을 구하는 문제로 변환이 가능하다! 이건 König's Theorem에 따라 bipartite graph가 perfect하고, perfect한 그래프는 그것의 complement도 perfect하기 때문에 maximum clique를 쉽게 구할 수 있는 것.minimum vertex cover를 구하는 알고리즘 = 반전시키면 maximum independent set을 구하는 알고리즘도 새롭게 알았다. 엣지들에 방향성을 부여해서, 매칭에 포함된 간선은 오른..
SRM 338 Hard의 editorial에서 가져옴.. "winning position"이라는 것이 정말 광역으로 쓰일 수 있구나.. 와.. 문제상에서 어떤 한 특성을 잡고 그것의 여집합과의 관계를 생각해서 winning position을 창조해 낼 수도 있다니 정말 신박하다.. algorithmic game에 정말 자신이 없었는데, matrix game과 저 CakeParty를 풀고 나니 조금 이해가 되는 느낌이다.
KTU Programming Camp Day 5를 돌았다. 맞는 해법을 썼던 E를 틀린 게 아쉽고, 자원을 까다롭게 써야 해서 recursion으로 segment tree를 짰더니 계속 TLE가 났던 G가 아쉽다.