1 of 101

Advanced

Dynamic Programming

Tossaporn Saengja

SiData+, Faculty of Medicine, Siriraj Hospital

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

2 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

3 of 101

AI tricks

Donโ€™t believe every output from LLM โ€“ always verify, you should be smarter than an LLM

​

  • ChatGPT 4o โ€“ general concept
  • Claude Sonnet 3.7 โ€“ better at Thai
  • Perplexity โ€“ better at search (new, current information)

Tossaporn Saengja

Advanced DP

4 of 101

ChatGPT 4o

Tossaporn Saengja

Advanced DP

5 of 101

ChatGPT 4o

โ€“ personalized

Tossaporn Saengja

Advanced DP

6 of 101

ChatGPT 4o

โ€“ clarification

Tossaporn Saengja

Advanced DP

7 of 101

ChatGPT 4o

โ€“ clarification

Tossaporn Saengja

Advanced DP

8 of 101

Claude Sonnet 3.7

โ€“ translation

https://claude.ai/share/0a183c78-af9c-416c-acc6-8b1fa5b54afe

Tossaporn Saengja

Advanced DP

9 of 101

Perplexity

โ€“ search

https://www.perplexity.ai/search/suggest-me-a-codeforces-proble-2CJDri1ZSDWJitqZ5laY.A

Tossaporn Saengja

Advanced DP

10 of 101

AI tricks

Donโ€™t believe every output from LLM โ€“ always verify, you should be smarter than an LLM

​

  • ChatGPT 4o โ€“ general concept
  • Claude Sonnet 3.7 โ€“ better at Thai
  • Perplexity โ€“ better at search (new, current information)

​

We might be at the point of generating content is easier than verifying content โ€“ be extra careful with content on the internet

Tossaporn Saengja

Advanced DP

11 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

12 of 101

AlphaGeometry

from https://www.youtube.com/watch?v=TuZhU1CiC0k

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

13 of 101

AlphaGeometry

from https://www.youtube.com/watch?v=TuZhU1CiC0k

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

14 of 101

AlphaGeometry

from https://www.youtube.com/watch?v=TuZhU1CiC0k

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

15 of 101

AlphaGeometry

from https://www.youtube.com/watch?v=TuZhU1CiC0k

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

16 of 101

AlphaGeometry

from https://www.youtube.com/watch?v=TuZhU1CiC0k

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

17 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

18 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

19 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

20 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

21 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

22 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

23 of 101

Convex Hull

Tossaporn Saengja

Advanced DP

from https://www.youtube.com/watch?v=qTE1OSUNR3w

Tossaporn Saengja

Advanced DP

24 of 101

Convex Hull

from https://codeforces.com/blog/entry/63823

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

25 of 101

Li Chao Tree

  • essentially a toolbox that lets you maintain a set of linear functions and answer queriesโ€”like โ€œwhat's the maximum (or minimum) value at x?โ€โ€”in O(logโก n) time.
  • This efficiency is achieved by partitioning the x-axis into segments and keeping track of which function is optimal over each segment.

​

  • Segment tree that maintain lines f(x) = mx+c
  • Answer max/min f(x) at any x
  • storing only the โ€œupperโ€ (or โ€œlowerโ€) envelope of the lines

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

26 of 101

Li Chao Tree

The Intuition

  • Interval Partitioning:๏ฟฝ The x-axis is split into segments, where each node in the tree represents an interval.
  • Local Optimality:๏ฟฝ Each node holds the line that provides the optimal (e.g., maximum) value at the midpoint of its interval.
  • Dynamic Updating:๏ฟฝ As new lines are added, the tree updates the envelope (similar to maintaining a convex hull) to ensure fast queries.

Tossaporn Saengja

Advanced DP

27 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

28 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

29 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

30 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

31 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

32 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

void insert(int l, int r, Line seg, int o=0) {

if(l + 1 == r) {

if(seg(l) > a[o](l)) a[o] = seg;

return;

}

int mid=(l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;

if(a[o].m > seg.m) swap(a[o], seg);

if(a[o](mid) < seg(mid)) {

swap(a[o], seg);

insert(l, mid, seg, lson);

}

else insert(mid, r, seg, rson);

}

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

33 of 101

Li Chao Tree

from https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

34 of 101

Tossaporn Saengja

Advanced DP

35 of 101

(2, 3)

Tossaporn Saengja

Advanced DP

36 of 101

(2, 3)

void insert(int l, int r, Line seg, int o=0) {

if(l + 1 == r) {

if(seg(l) > a[o](l)) a[o] = seg;

return;

}

int mid=(l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;

if(a[o].m > seg.m) swap(a[o], seg);

if(a[o](mid) < seg(mid)) {

swap(a[o], seg);

insert(l, mid, seg, lson);

}

else insert(mid, r, seg, rson);

}

Tossaporn Saengja

Advanced DP

37 of 101

(2, 3)

void insert(int l, int r, Line seg, int o=0) {

if(l + 1 == r) {

if(seg(l) > a[o](l)) a[o] = seg;

return;

}

int mid=(l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;

if(a[o].m > seg.m) swap(a[o], seg);

if(a[o](mid) < seg(mid)) {

swap(a[o], seg);

insert(l, mid, seg, lson);

}

else insert(mid, r, seg, rson);

}

Tossaporn Saengja

Advanced DP

38 of 101

(2, 3)

void insert(int l, int r, Line seg, int o=0) {

if(l + 1 == r) {

if(seg(l) > a[o](l)) a[o] = seg;

return;

}

int mid=(l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2;

if(a[o].m > seg.m) swap(a[o], seg);

if(a[o](mid) < seg(mid)) {

swap(a[o], seg);

insert(l, mid, seg, lson);

}

else insert(mid, r, seg, rson);

}

Tossaporn Saengja

Advanced DP

39 of 101

(2, 3)

Tossaporn Saengja

Advanced DP

40 of 101

Tossaporn Saengja

Advanced DP

41 of 101

Tossaporn Saengja

Advanced DP

42 of 101

Tossaporn Saengja

Advanced DP

43 of 101

Tossaporn Saengja

Advanced DP

44 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

45 of 101

Slope Trick

  • Representation of piecewise functions that are
    • Continuous
    • Segments with integer slopes
    • convex/concave
  • Instead of representing the entire function, it maintains only the breakpoints where the slope changes.

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

46 of 101

Slope Trick

The Intuition

  • Focus on Breakpoints:๏ฟฝ For convex functions, the key information lies at the points where the slope changes.
  • Efficient Updates:๏ฟฝ When modifying the function (e.g., adding an absolute value term), update only these breakpoints.
  • Data Structure:๏ฟฝ A balanced tree or multiset is typically used to store breakpoints along with their slope changes.

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

47 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

48 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

49 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

50 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

f(x) = x-3 , x >= 3 , m=1

3-x , x < 3 , m=-1

f(3) = 0

f(x) = mx + c, f(3) = -3 + c = 0, c=3

Tossaporn Saengja

Advanced DP

51 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

52 of 101

Slope Trick: WHY?

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

53 of 101

Slope Trick

from https://www.youtube.com/watch?v=p8RxN6Y9OOA

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

54 of 101

Increasing Array II

https://codeforces.com/contest/713/problem/C

Tossaporn Saengja

Advanced DP

55 of 101

Tossaporn Saengja

Advanced DP

56 of 101

https://codeforces.com/blog/entry/47821

Tossaporn Saengja

Advanced DP

57 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

58 of 101

Plug DP / DP on broken profiles

from https://codeforces.com/blog/entry/90841

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

59 of 101

Plug DP / DP on broken profiles

from https://codeforces.com/blog/entry/90841

๐‘‘๐‘[๐‘–][๐‘—][๐‘š๐‘Ž๐‘ ๐‘˜]: represent the number of possible full tilings of all cells in rows ๐‘–โˆ’1 and earlier, and the first ๐‘— cells in row ๐‘–, with a plug mask of ๐‘š๐‘Ž๐‘ ๐‘˜

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

60 of 101

Plug DP / DP on broken profiles

from https://codeforces.com/blog/entry/90841

The plug will be 1 (toggled) if there is a domino laid over it, and 0 otherwise.

​

plugs with states [1,0,1,0,1,0,0,1,0] is ->

​

So this is ๐‘‘๐‘[3][4][1010100102]

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

61 of 101

Tossaporn Saengja

Advanced DP

62 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

63 of 101

Divide and Conquer Optimization

Tossaporn Saengja

Advanced DP

from https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html

Tossaporn Saengja

Advanced DP

64 of 101

What It Does

This technique speeds up DP recurrences by narrowing the search space for the optimal decision index. It leverages the monotonicity of the optimal decision opt(i,j) in the recurrence dp(i,j).

The Intuition

  • Optimal Decision vs. Cost:๏ฟฝ dp(i,j) is the optimal cost up to index j using i segments, while opt(i,j) denotes the decision index achieving this cost.
  • Monotonicity:๏ฟฝ The property that opt(i,j) is monotonic (non-decreasing as j increases) reduces the number of choices to check.
  • Recursive Division:๏ฟฝ The problem is divided into subranges, each leveraging previously computed optimal indices.

Tossaporn Saengja

Advanced DP

65 of 101

Tossaporn Saengja

Advanced DP

66 of 101

Tossaporn Saengja

Advanced DP

67 of 101

Tossaporn Saengja

Advanced DP

68 of 101

Tossaporn Saengja

Advanced DP

69 of 101

Tossaporn Saengja

Advanced DP

70 of 101

Tossaporn Saengja

Advanced DP

71 of 101

Tossaporn Saengja

Advanced DP

72 of 101

Tossaporn Saengja

Advanced DP

73 of 101

Tossaporn Saengja

Advanced DP

74 of 101

Tossaporn Saengja

Advanced DP

75 of 101

Tossaporn Saengja

Advanced DP

76 of 101

Tossaporn Saengja

Advanced DP

77 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

78 of 101

WQS Binary Search

Tossaporn Saengja

Advanced DP

from https://www.serbanology.com/vault/The%20Trick%20From%20Aliens

Tossaporn Saengja

Advanced DP

79 of 101

What It Does

WQS Binary Search tackles DP problems with extra constraints (like partitioning an array into exactly K segments) by introducing a penalty ฮป for each segment. Tuning ฮป through binary search guides the DP solution toward using exactly K segments.

The Intuition

  • Penalty Relaxation:๏ฟฝ Instead of enforcing the constraint directly, add a penalty ฮป for every segment used.
  • Binary Search Tuning:๏ฟฝ Adjust ฮป until the DP solution naturally yields exactly K segments.
  • Continuous Adjustment:๏ฟฝ Transform a discrete constraint into a continuous optimization problem.

Tossaporn Saengja

Advanced DP

80 of 101

Tossaporn Saengja

Advanced DP

81 of 101

Tossaporn Saengja

Advanced DP

82 of 101

Tossaporn Saengja

Advanced DP

83 of 101

Tossaporn Saengja

Advanced DP

84 of 101

Outline

  • (AI tricks)
  • (AlphaGeometry)
  • Convex Hull & Li Chao Tree
  • Slope Trick
  • Plug DP
  • Divide and Conquer DP Optimization
  • WQS Trick

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

85 of 101

https://vjudge.net/contest/700721

https://vjudge.net/contest/700742

https://vjudge.net/contest/700730

Tossaporn Saengja

Advanced DP

86 of 101

Li Chao Tree: CF923F - Escape Through Leaf

https://codeforces.com/problemset/problem/932/F

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

87 of 101

Li Chao Tree: CF923F - Escape Through Leaf

https://codeforces.com/problemset/problem/932/F

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

88 of 101

Li Chao Tree: CF923F - Escape Through Leaf

https://codeforces.com/problemset/problem/932/F

​

https://robert1003.github.io/2020/02/06/li-chao-segment-tree.html#a-hrefhttpscodeforcescomproblemsetproblem932fcf923f---escape-through-leafa

​

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

89 of 101

Convex Hull Optimization

https://codeforces.com/contest/631/problem/E

https://codeforces.com/contest/660/problem/F

https://codeforces.com/contest/311/problem/B

https://codeforces.com/contest/673/problem/E

https://codeforces.com/contest/455/problem/E

https://codeforces.com/contest/1179/problem/D

​

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

90 of 101

Convex Hull Optimization: Solutions

DP optimization - Convex Hull Optimization | A Simple Blog

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

91 of 101

Slope Trick: C. Sonya and Problem Wihtout a Legend

https://codeforces.com/contest/713/problem/C

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

92 of 101

Plug DP: Counting Tilings

https://cses.fi/problemset/task/2181

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

93 of 101

Divide and Conquer Optimization: E. Ciel and Gondolas

https://codeforces.com/contest/321/problem/E

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

94 of 101

Divide and Conquer Optimization: F. Yet Another Minimization Problem

https://codeforces.com/contest/868/problem/F

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

95 of 101

E. Gosha is hunting

https://codeforces.com/contest/739/problem/E

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

96 of 101

Li Chao Tree: links

A Simple Introduction to Li-Chao Segment Tree

[Tutorial] Li Chao Tree Extended - Codeforces

Convex Hull Trick Visualisation

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

97 of 101

Convex Hull: links

Convex Hull Trick Visualisation

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

98 of 101

Slope Trick: links

​

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

99 of 101

Plug DP / DP on broken profiles: links

An Introduction to Plug DP - Codeforces

Additional DP Optimizations and Techniques ยท USACO Guide

​

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

100 of 101

Divide and Conquer Optimization: link

DP optimization - Divide and Conquer Optimization | A Simple Blog

DP optimization - Knuth Optimization | A Simple Blog

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP

101 of 101

WQS Binary Search: links

DP optimization - WQS Binary Search Optimization | A Simple Blog

Incredibly beautiful DP optimization from N^3 to N log^2 N - Codeforces

Intuition or Motivation Behind Alien's DP Trick - Codeforces

https://www.serbanology.com/vault/The%20Trick%20From%20Aliens

Tossaporn Saengja

Advanced DP

Tossaporn Saengja

Advanced DP