Algo Talk: Railroads from Facebook Hacker Cup
Errichto Algorithms · 27:08 · Watch on YouTube
문제는 Facebook Hacker Cup Round 3의 "Railroad Reconstruction"입니다. 동적 프로그래밍으로 대략 O(n³) 또는 O(n³ log n)에 풀 수 있습니다. 핵심은 관찰을 시간상에서 이동하는 것이 오직 맨 처음이나 맨 끝으로 이동할 때만 도움이 된다는 것입니다. 따라서 "최대 k개의 이벤트를 재배열"은 실제로 "최대 k개의 이벤트를 건너뛰기"를 의미...