8VC Venture Cup 2016 - Elimination Round

• 
• virtual participation..을 했는데 망했다ㅡㅜ.. C에서 3-block을 먼저 놓아버린다는 greedy로 방향을 잡아버려서 삽질을 했고, D는 접근이 잘 되지 않아서 이전에 해설을 들었던 E를 코딩했는데, ternary search에 대한 에러인지 계속 WA가 뜨더라.. 다 풀어봐야지. 1페이지에 한국사람, 그것도 서울대 사람이 다섯이나 있더라ㅋㅋㅋㅋ사람들 왜케잘함!
• A : \(O(N^3)\) 구현문제.. 메모리를 \(O(N^2)\)를 써서 \(O(N)\)으로 풀 수도 있을 것 같다.
• B : \((r,g,b)\)에 대한 공간탐색을 진행하면 된다. \(O(RGB)\)
• C : 6의 배수에서 겹치게 되고 이를 2-block 혹은 3-block 어디로 배분하는가가 키포인트. 순서는 상관이 없으므로 결국 둘 중 하나를 \(k\)개까지의 6의 배수를 먹고 그다음부터는 안먹는다!고 정해놓고 열심히 계산해서 maximum height를 구하면 된다. \(O(N)\)
• D : 왜 이걸 못풀었지.. 다시 들여다보니 금방 풀림. 결국 승패는 결정되어 있으므로 pair를 세 번 뽑는 것이 전체 경우의 수(분모)이고, 이것중에서 조건을 만족하는 경우의 수를 세야 한다. 여기서 중요한 것은 Andrew와 Jerry의 점수차이이고, 각 difference에 대해 1회 라운드에서는 \(O(n^2)\), 2회 라운드까지는 \(O(d^2)\)로 세줄 수 있다. 여기서 \(d\)는 1회에서 발생할 수 있는 difference의 상한으로, 문제에선 5000이 안된다. 1회까지 진행했을 때 \(i\)만큼 차이가 발생할 경우의 수를 \(B[i]\), 2회까지 진행했을 때는 \(C[i]\)라 한다. 이제 마지막 round에서 difference \(k\)에 대해 앞선 2회까지의 차이가 \(k\)를 넘지 않아야 하고, 따라서 \(B[k] * \sum_{j<k}C[j]\)를 더해주면 된다.
• E : 문제는 \(n \le 200,000\)개의 수가 주어지고, 여기서 (평균-중간값)이 최대가 되는 subset을 구하는 것이다. 중간값은 짝수개의 subset일 경우 가운데 두 수의 평균으로 정의된다. 중간값을 정해놓고 평균의 maximum을 구하는 전략을 자연스럽게 떠올릴 수 있다. 문제를 좀 더 간단하게 만드는 건 사실 짝수개 subset은 답이 될 수 없다는 사실이다-,- 짝수 subset이 최댓값이라고 가정하고, 가운데 두 수 A,B(A<B)중에 larger element를 제외할 경우 평균 \(e\)는 \(\frac{ne-B}{n-1}\)로 변화하고, 중간값 \(\frac{A+B}{2}\)는 \(A\)로 변화한다. 두 개의 변화량을 따져보면 기존에 평균<중간값일 경우 중간값이 감소량이 더 크다. 따라서 larger element를 제외한 subset이 더 optimal하다.
• 따라서 \(i\)번째 element를 중간값으로 정해놓을 경우 평균이 최대가 되게끔 선택하려면, sorted array에서 \(i\)의 좌, 우측으로 동일한 \(k\)개만큼 선택하는데 zero-index기준 \([i-k, i)\)와 \([n-k,n)\)의 범위를 선택하는 것이 최대가 됨이 당연하다. 하지만 어떤 \(k\)가 최대 평균을 가져올지 문제가 된다. 이를 각각 계산하려면 \(O(n^2)\)이 필요하기 때문. 하지만 \(k\)에 대한 변화량(더해지는 요소들)은 decreasing function이므로, \(i\)번째 요소를 희석시키면서 올라간 평균이 언젠가는 감소하게 된다는 걸 알 수 있다.. 즉 \(k\)에 대한 평균 함수는 증가하다가 감소하는 unimodal function인 것. 따라서 삼분검색이 가능하고, \(O(n\log n)\)으로 각각의 최대 \(k\)를 따져보면서 maximum을 구해볼 수 있다!!
• 문제를 처음 봤을 때는 median을 정해놓고 sorted array에서 greedy하게 선택해본다~는 아이디어까진 갔는데 이게 unimodal하다는 건 꿈에도-,-생각하지 못했다. 평균의 변화량을 살펴야 하고, 평균은 식이 더럽기 때문에... 정확한 증명보다 어느정도 직관이 필요한 부분인 것 같다. 이에 더해 해법을 알고나서도 구현에 힘이 들었는데 integer에 대한 삼분검색은 form을 기억해둬야 할 것 같다. \(lo\)를 \(-1\)로 빼버리고, \(hi\)는 마지막 요소의 index를 넣는다. \(x\)를 검사할 때 \(f(x), f(x+1)\)을 살피므로 결국 \(lo, hi\)둘다 valid한 function정의를 갖진 않으나, \(lo\)는 무조건 true, \(hi\)는 무조건 false로 보는 것. 재구현해서 한번에 AC를 받았다.
• F : 정말 신박한 dp문제.. tutorial을 읽고 감동받았다..ㅠㅠ 이런걸 스스로 풀어내면 참 좋겠는데. 문제는 \(n \le 200\)개의 숫자가 주어지고 이들 숫자들을 적절히 분할하는데, 각 그룹의 imbalance = (최댓값-최솟값)의 합들이 \(k\)를 넘지 않는 경우의 수를 세는 것이다. 각 그룹의 최대, 최소 요소만 고려하면 된다는 것은 당연하나, 중요한 observation은 각 그룹들의 imbalance를 delta function \(a[i]-a[i-1]\)의 range sum으로 전환해서 생각할 수 있다는 점이다!!
• sorted array상에서 DP를 돌린다. \(dp[i][j][k]\)를 \(i\)번째까지 고려하고, \(j\)개의 open구간이 있으며, \(k\)만큼의 imbalance를 사용한 가짓수로 정의한다. 각 그룹을 sorted array상에서 maximum과 minimum 두 수를 잇는 연결로 생각하는데, \(j\)개만큼의 그룹이 maximum에 닿지 않았다는 말이다. \(k\)를 \(j*(a[i]-a[i-1])\)만큼 증가시키고 \(i\)번째 요소의 처분을 결정한다. 물론 \(k\)는 아직 완전히 계산되지 않은 상태로, 각 연결들이 종료될 때에야 해당 그룹의 imbalance가 완전히 반영된다. \(j\)의 사용으로 각 그룹의 imbalance를 따로 고려할 필요가 없어지는 것..
• 네 가지 경우를 생각할 수 있다. 1) 자기자신만의 그룹을 만드는 것, 2) 기존 연결에 종료하지 않고 포함되는 것, 3) 새로운 연결을 시작하는 것, 4) 기존 연결 중 하나를 종료시키는 것. 이 모든 경우를 위의 \(dp[i][j][k]\)의 상태로 아름답게 관계지을 수 있다ㅠ.ㅠ
• 
• Stanford Local이후로 이런 신박한 dp는 처음보는 것 같다. 어떻게 imbalance의 고려를 저런식으로 할 생각을 했을까!
• G : N개의 래플이 있고, T개의 티켓을 가지고 있다. 각 래플은 \(P_i\)라는 상금을 가지고, 기존에 \(A_i\)개 만큼의 티켓이 들어있다. 티켓을 적절히 분배해서 최대 기댓값을 얻기 위해서는 티켓을 넣을 때마다 더 생기는 marginal value를 구해 최댓값을 greedy하게 선택하는 전략이 있을 수 있다. 여기까진 생각할 수 있었는데, 문제는 래플의 티켓 \(A_i\)가 +1, -1씩 변화할 때 기댓값의 변화를 출력해야 한다는 점이었다.
• 
• 그런데 분모가 +1, -1만큼 변화할 경우, 그곳에 넣는 나의 티켓수도 기껏해야 +1, -1로 변화한다는 것을 증명할 수 있다. 위의 그림과 같이 증명가능한데, 지금까지 선택된 상황을 가정해보면 그것보다 큰 marginal value를 선택하지 않을 수 없고(a증가의 경우) 그것보다 작은 marginal value를 선택할 리 없게 된다(a감소의 경우). 문제 제약조건인 \(b \le a\)를 고려하더라도 마찬가지이고, 따로 처리해주면 된다.
  
• 난 이 문제의 구현도 어려웠다..ㅜㅜ heap을 두 개 유지한다. 추가할 경우 최대 marginal value를 주는 곳부터 추가해야 하고, 삭제할 경우 최소의 marginal value를 줬던 선택을 취소해야 한다. 이걸 서로 consistent하게 유지시켜줘야 하고, a가 변화할 때 change update도 해줘야 한다.