Hacker Cup 2017 Round 1 후기 & solution
live 때 작성하고 그 후 조금 수정한 python 3 기준 hacker cup 2017 round 1 source와 Facebook solution
총 4 문제였고 4 문제 다 열심히 풀었는데…
4 문제 다 풀기는 풀었는데 2 문제만 맞추고 2문제는 못 맞춤.. 다음 Round 를 가기는 가는데 영 찝찝하네.
Pie Progress
전형적인 greedy algorithm으로 해결할 수 있는 문제.
결국 전체 N * M 개의 pie 중 가장 싼 N 개의 pie 를 고르면 되는건데, 두가지 제약이 있음.
a) 미래에 나올 빵을 미리 살 수는 없음.
b) 같은 날 빵을 여러개 사면 살수록 빵의 가격이 올라감.
a) 는 1 일부터 N 일까지 가면서 그 시점을 기준으로 pie 를 고르면 되고, b) 는 세금을 빵 가격에 붙여 버리면 됨. 어떤 날 가장 싼 빵 가격은 c+1, 두번째로 싼 빵 가격은 c+3, 세번째로 싼 빵 가격은 c+5,… 이렇게 추가되는 세금의 가격을 미리 빵 가격에 붙여두면 해결.
N day 동안 새로운 M 개의 pie 를 취하면 전체 개수는 N*M, 이것을 priority queue에 집어 넣고 빼면 O(N*M log(N*M))이 된다. 근데 저걸 구현하기는 너무 귀찮아서 매번 정렬을 해줬더니 O(N²*M log(N*M))이 되었…
위와 같이 구현.
Facebook 에 있는 solution 에는 dynamic programming을 이용한 solution도 있음. 구현은 훨씬 복잡하니.. 생략.
Fighting the Zombies
처음에는 쉬운 문제인 줄 알았음.. 그러나 풀다보니 그렇지 않다는 걸 깨달..
다행히 원은 어떤 크기든 될 수 있으니 원에 대해서는 고려하지 않아도 되고 두개의 사각형이 합쳐져서 하나의 사각형이 되니 내부에 가장 많은 좀비를 포함하는 두개의 사각형을 구하면 됨.
사각형은 좀비가 있으면 그 위치로부터 시작하면 되는데, 그 좀비 위치를 기준으로 오른쪽으로 사각형이 있을 수도 있고 아래쪽으로 사각형이 있을 수도 있음. (반대쪽으로도 있을 수 있는데, 그렇게 해서 다른 점이 포함되는 경우는 그 다른 점을 기준으로 한 시작 위치에 포함될 수 있으므로 중복이 되다.)
그렇게 하면 시작점을 각 점의 왼쪽 끝 위쪽끝 모두 조합해야 하니 N², 그리고 그 경우에 대해 다른 삭형을 모두 고려하면 N²*N², 그 상태로 점들의 포함 여부를 계산하면 N²*N²*N 해서 N⁵ 이 된다. N 이 50 인데 그렇게 하면 너무 크니까…
N²*N 으로 set 을 구성, 그리고 그 set 간에 비교를 해서 또 set 을 구성하는 방식을 취하니 속도가 훨씬 빨라지지 않았을까 기대는 되긴 하는데.. 최악의 경우는 변함은 없었을듯.
Facebook solution 으로는
This time complexity can be improved to O(N³ log N) by trying to fix M to be each of the O(N²) candidate squares, and finding the corresponding optimal D square in O(N log(N)) time using a combination of a line sweep and a segment or interval tree.
라는데, line sweep 과 segment tree나 interval tree 가 뭔지는 추후에 봐야겠다.
Manic Moving
Graph + dynamic programming 문제.
그래프에서 각 node간 최단거리를 모두 구해놓은 상태에서 순차적으로 짐을 옮기면서 1개만 옮기고 마무리를 할지 아니면 2개를 동시에 나르는지 각 상태를 기술해 놓은 상태에 따라 해결하면 된다고 생각을 해서 최단거리는 floyd-warshall algorithm으로 해결하고 (까먹어서 찾아봤…) 그 후 dynamic programming을 했는데 두개를 가지고 있을 때 하나를 내려놓고 다음껄 가지고 가는 경우를 고려 안해서 망…
여튼 제출 후 망했다는 걸 깨달았고 그 후 친구의 도움으로 다시 짜보았다.
f(a, b) 를 정의하는데, a 는 현재의 task (1~k), b 는 가지고 있는 짐의 숫자 (0~1) 이라 하고 a task를 완료한 시점에 b 개의 짐을 가지고 있을 때 최소값을 f(a,b) 라 하자. x~y는 x에서 y까지의 최소값이라고 하자. s와 d는 각 task의 시작점과 끝점. pre와 next는 이전 task, 그리고 다음 task이다.
f(a, 0) = min(f(a-1, 0)+pre d~s+s d, f(a-1, 1)+pre d~d
f(a, 1) = min(f(a-1, 0)+pre d~s+s~next s+next s~d, f(a-1,1)+pre d~next s+next s~d
위와 같이 쓸 수 있는데 f(a, 0)과 같은 경우에는 task를 남겨둘 필요가 없기 때문에 f(a-1, 0)에서 오는 경우 이전 도착지에서 현재의 출발지, 그리고 현재의 출발지에서 현재의 도착지로만 가면 된다. f(a-1, 1)에서 오는 경우에는 현재 출발지를 전단계에서 거쳤기 때문에 현재는 갈 필요가 없다. f(a, 1)과 같은 경우에는 현재의 도착지를 가기 전에 미래의 출발지를 가둔다는 차이점이 있다.
초기값 처리 등은 적당히 하면 된다. 구현은 아래와 같다.
Facebook 공식 solution은 좀 다른데 시간 나면 읽어봐야겠다..
Beach Umbrellas
크기가 m인 우산을 꽂을 수 있는 구멍이 있다. 그리고 우산의 반지름은 r이며 우산끼리는 겹칠 수 없다. 이것을 바꿔서 생각하면 크기가 m-1의 크기인 칸이 있고 그곳에 우산을 겹치지 않게 채워넣어야 한다. 그리고 공백도 존재할 수 있다. 라고 해석할 수 있다.
반지름이 r인 우산은 실질적으로 2*r의 칸을 차지한다. 첫번재 칸과 마지막 칸의 우산의 반쪽은 다른 우산과 겹칠 수가 없기에 실질적으로 r칸만을 차지한다. 첫번째 우산과 두번째 우산은 r1, r2, 나머지 우산을 r3… rn이라고 하면 전체 차지하는 칸의 수는 t = sum(r1…rn)*2-r1-r2가 된다. m-1 칸 중 t 를 제외한 칸 수 blank = m-1- t 는 r1과 r2 사이 그 어떤 곳에도 들어갈 수 있다. 이는 r1과 r2가 고정되어 있을 때 r3… rn과 blank 개의 공백이 공백만 중복을 허용하는 순열과 마찬가지이므로 f(r1, r2) = (n+blank)!/(blank!*(n*(n-1)))이 된다. (n+blank)!인 이유는 전체 요소의 수가 n+blank이기 때문이고 blank!로 나눠준 이유는 공백은 중복을 허용하기 때문인데 공백이 blank개수만큼 있기 때문이다. n과 n-1로 나눠준 이유는 첫번째와 마지막 요소는 고정이 되어 있기 때문이다.
따라서 풀이는 아래와 같다. 몇 가지 트릭을 첨가하였는데, ri와 rj는 대칭형이므로 반만 돌고 2를 곱해주었다. 또 cache를 사용하여 기존에 구한 해에 대해서는 다시 계산을 하지 않았다.