Aliens Optimization

• Introduction to Aliens Optimization
  • Preface: DP Optimizations & Techniques
  • Backgrounds: WQS binary search & IOI 2016 Aliens
  • Overview: Properties of the related problem
• Analysis of the technique (Based on a problem)
  • Comparison of Greedy and DP approches
  • Transform into a concave function & binary search
  • Proof and Analysis
  • Implementation & Conclusion
• Problem
  • https://codeforces.com/problemset/gymProblem/102059/M
  • https://tioj.ck.tp.edu.tw/problems/2039
  • https://www.luogu.com.cn/problem/P2619
  • https://codeforces.com/problemset/problem/1279/F
  • https://ioinformatics.org/files/ioi2016problem6.pdf

Reference

• https://soi.ch/wiki/alien-optimization/
• https://pufanyi.github.io/%E7%94%9F%E6%88%90%E6%A0%91%E5%85%A5%E9%97%A8/Train2012-sol-wqs.pdf
• https://tioj.ck.tp.edu.tw/uploads/attachment/5/51/10.pdf
• https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-aliens
• https://medium.com/@bluezebragames/dynamic-programming-optimization-the-aliens-trick-9138176287cf
• https://prutekoi.github.io/post/xue-xi-bi-ji-wqs-er-fen-tu-you-hua/
• https://blog.csdn.net/emm_titan/article/details/124035796
• https://www.cnblogs.com/CreeperLKF/p/9045491.html
• IOICamp 2022 handout