Distributed Code Jam 연습 셋을 돌았다. 일반 Code Jam Round 3이상에 진출해야 DCJ에 참가할 수 있기 때문에, koosaga의 계정을 빌려 썼다.

DCJ는 일반적인 PS문제들과는 다르게, 분산 컴퓨팅을 하는 것이 주 목적이다. 즉, 독립적으로 돌아가는 노드 여러개 (보통 100개)를 주고, 일반적으로 처리할 수 없을 정도로 큰 데이터(대략 10^9정도) 에 대해서 주어진 문제를 해결하는 것이다.
물론 데이터가 너무 크기 때문에 표준 입출력은 사용하지 않으며, interactive형식으로 함수를 include해서 사용한다.
이 때, 노드 사이의 상호작용이 가능하다. 그러나 상호작용은 상당한 비용(시간)과 제한을 가지고 있는데, 보통 노드당 최대 1000회 신호를 보낼 수 있으며(버퍼를 비우는 것), 네트워크를 지나는 데이터가 전부 8MB 이하여야 한다. 그리고 한번 버퍼를 비우고 받을 때마다 대략 5ms의 시간이 걸린다.
채점은 당연하게도, 모든 노드가 수 초 이내에, 그리고 노드당 메모리 제한을 가지고 실행되는지, 그리고 올바른 답이 나오는지, 그리고 노드 사이의 신호 제한을 맞추었는지를 체크한다.

아무튼, 전부터 한번쯤 해보고 싶었는데, 서버가 항상 열려있지 않고, 가이드 읽기도 귀찮고, 참가도 못하고 해서 시도해보지 않고 있었다. 이번에 해보니까 역시 새로워서 재밌다.

생각해보면 노드당 1GiB의 메모리를 주는 문제도 있고, 노드가 100개인데, 이러면 아무튼 자원 소모가 엄청나다. 시간을 단축시키기 위해서 자원을 곱절로 사용하는 격이지만, 아무튼 빠르게 해결할 수 있다면 장점이 생긴다. 그리고 분산 컴퓨팅에는 일반적인 알고리즘을 사용할 수 없기 때문에, 또 다른 테크닉이 필요하다. 아무튼 재미있었다.

17 R1 Pancakes, 17 R2 Flagpoles
그냥 적당히 노드당 10^7개씩 나눠서 선형에 해주면 된다.

17 R1 weird editor
큰 수를 많이 사용하는 것이 항상 이득이다. 9부터 1까지 마지막 x뒤에 x+1이 몇개 있는지를 세주면 된다. 대략 시간은 O(N/D + 10DlogN)정도에 했고, 통신은 일반 노드가 30, 마스터 노드는 추가적으로 10D, 메모리는 노드당 O(N/D)에 했다. 나는 통신 수가 위험해서 노드 몇개를 버렸다.

17 R1 todd and steven
적당히 merge해주면 되는데, 노드당 시작점을 알기가 힘들다. 그러니 시작점만 미리 계산해놓는 것을 빠르게 해 주어야 하는데, 이는 적당한 이분탐색으로 노드당 O(log^2N)에 해줄 수 있다. 이 때 한 노드는 이전 노드의 결과가 필요하므로, 대기 시간이 발생한다. 그래도 O(Dlog^2N)으로, 용인할 수 있는 범위이다.
이후, 그냥 노드당 독립적으로 merge하고, 답을 전부 마스터 노드에 전해주면 된다.

17 WF baby blocks
부분 합을 전부 가지고 있을 수가 없다. 메모리도 힘들고, 시간도 빡빡하며, 결정적으로 통신 수의 제한 때문에 필요할 때마다 불러올 수가 없다.
배열을 50조각으로 나누고, 정방향 부분합과 역방향 부분합을 생각한다. 100개의 값을 정렬하고 나면, 내가 봐야 하는 구간을 100개로 나눌 수 있다. 각 노드당 구간을 찾는 데 한번 미리 훑어야 하지만, 10^7정도일 것이므로 아무래도 상관없다.

17 WF lemming
결국 functional graph(에서 정점 하나가 outdeg이 0인거)에서 component 수를 찾으면 된다. 그리드를 세로로 100조각으로 나누고, 조각 안에서 끝나는 component는 전부 셀 수 있다. 조각을 넘나드는 component에 대해서는, 어자피 모서리 수가 적으므로 전부 모아서 마스터에 보내주고, 마스터에서 한번에 처리한다.

Image result for lemming<figcaption>긔여운 레밍</figcaption></figure>

새로운 문제들이 많아서 재미있었다. 이번 셋은 구현하기도 바빴고, 여러 가지 생각을 하느라 분주했던 것 같다. 세팅이 익숙하지 않은 것도 있었지만, 아무튼 재미있었다. 생각해보면 문제들의 아이디어는 크게 복잡하지 않은데, 얼마나 깔끔하게 생각하고 제한을 잘 고려하느냐가 중요한 것 같다. 시간이 한정되어 있으니, 너무 정교하게 생각해도 손해고, 다양한 제한을 실수로 체크를 안하고 생각하면 손해가 막심하다. 내년에는 가능하면 풀세팅하고 참가해봐야겠다.