[IOI 2014 Practice Contest 2] Guardians of the Lunatics

Category:

• DP + Divide and Conquer Optimization
• DP + Knuth Optimization

Problem statement: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14


Solution: https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14/editorial


Knuth Optimization:

• Paper: http://www.cs.ust.hk/mjg_lib/bibs/DPSu/DPSu.Files/p429-yao.pdf
• DP formulation:
• c[i, i] = 0
• c[i, j] = w(i, j) + min_{i
• Quadrangle Inequalities (QI): w(i, j) + w(i', j') ≤ w(i, j') + w(i', j) for all i ≤ i' ≤ j ≤ j'.
• Monotone on the lattice of intervals: w(i, j') ≤ w(i', j) for all i ≤ i' ≤ j ≤ j'.
• Theorem: QI + Monotone => Time = O(n^2).
• Lemma 1: w(i, j) is QI + Monotone => c[i, j] is QI.
• Lemma 2: 
• Define c_k(i, j) = w(i, j) + c[i, k-1] + c[k, j].
• Define K_c(i, j) = max{ k : c_k(i, j) = c[i, j] }.
• c[i, j] is QI => K_c(i, j) ≤ K_c(i, j + 1) ≤ K_c(i + 1, j + 1).