Người viết:Reviewer:Mục đích của bài viết này là để giới thiệu cho mọi người về một mô típ đã xuất hiện trong nhiều bài tập trung bình khó tới khó – tối ưu tổng của một số hàm lồi cho trước. Ý tưởng giải chung của các bài toán này thường là như nhau: tham lam trên chi phí tăng của các hàm lồi này (ta sẽ định nghĩa chi phí tăng ở phần tiếp theo).Bài viết này là phần 1 của một chuỗi 2 bài viết; phần 2 của chuỗi bài viết này mình sẽ giới thiệu thuật toán tìm tổng Minkowski của các bao lồi.Mình sẽ sử dụng các khái niệm sau xuyên suốt bài viết.Ta xét bài toán tổng quát sau.Cho nnn hàm lồi f1,f2,…,fnf_1, f_2, \dots, f_nf1​,f2​,…,fn​ được định nghĩa trên tập số nguyên không âm và một giá trị kkk cho trước. Tìm nnn số nguyên không âm x1,x2,…,xnx_1, x_2, \dots, x_nx1​,x2​,…,xn​ sao cho:In ra giá trị nhỏ nhất của f(x1)+f(x2)+⋯+f(xn)f(x_1) + f(x_2) + \dots + f(x_n)f(x1​)+f(x2​)+⋯+f(xn​).Giới hạn: 1≤n,k≤2⋅1051 \le n, k \le 2 \cdot 10^51≤n,k≤2⋅105.Để việc trình bày được thuận tiện hơn, đầu tiên ta xét bài toán với n=2n = 2n=2.Xét thao tác sau: khởi tạo x1=0x_1 = 0x1​=0 và x2=0x_2 = 0x2​=0, ta lặp bước sau kkk lần:Ý tưởng cơ bản của cách làm trên là ở mỗi bước, ta tăng tổng x1+x2x_1 + x_2x1​+x2​ lên 111; ta chọn cách làm mà tăng tổng f(x1)+f(x2)f(x_1) + f(x_2)f(x1​)+f(x2​) lên ít nhất.Để chứng minh cách làm trên là đúng, giả sử đáp án của bài toán là OOO. Ta xét ba dãy sau:Nhận xét là nếu ta sắp xếp dãy AAA theo thứ tự tăng dần rồi lấy tổng kkk phần tử nhỏ nhất, ta sẽ thu được một số SSS mà chắc chắn là O≥SO \ge SO≥S.Ngoài ra, ta cũng có thể chứng minh được là thao tác trên sẽ thu được tổng f(x1)+f(x2)f(x_1) + f(x_2)f(x1​)+f(x2​) đúng bằng SSS. Để ý rằng khi sắp xếp dãy A1A_1A1​ tăng dần, ta sẽ có A1=[f1(1)−f1(0),f1(2)−f1(1),f1(3)−f1(2),… ]A_1 = [f_1(1) - f_1(0), f_1(2) - f_1(1), f_1(3) - f_1(2), \dots]A1​=[f1​(1)−f1​(0),f1​(2)−f1​(1),f1​(3)−f1​(2),…] vì f1f_1f1​ là hàm lồi. Tương tự, với dãy A2A_2A2​, A2=[f2(1)−f2(0),f2(2)−f2(1),f2(3)−f2(2),… ]A_2 = [f_2(1) - f_2(0), f_2(2) - f_2(1), f_2(3) - f_2(2), \dots]A2​=[f2​(1)−f2​(0),f2​(2)−f2​(1),f2​(3)−f2​(2),…] sau khi sắp xếp các giá trị của A2A_2A2​ tăng dần. Nói cách khác, dãy A1A_1A1​ và A2A_2A2​ được sắp xếp theo ttt. Bởi vì AAA chẳng qua là dãy ghép của A1A_1A1​ và A2A_2A2​, dễ dàng nhận thấy qua thuật toán merge sort rằng khi thao tác trên dừng, ta thu được kkk giá trị nhỏ nhất của AAA.Với nnn lớn hơn, ta có thuật toán tương tự: khởi tạo mọi xi=0x_i = 0xi​=0, lặp bước sau kkk lần:Ta có thể sử dụng heap để cài đặt thuật toán trên với độ phức tạp là O((n+k)log⁡n)O((n + k) \log n)O((n+k)logn).Link bài: CF - 1428E.Có nnn củ cà rốt có độ dài a1,a2,…,ana_1, a_2, \dots, a_na1​,a2​,…,an​. Người chủ muốn cắt các củ cà rốt này các phần có độ dài nguyên dương cho kkk chú thỏ. Một phần cà rốt có độ dài xxx sẽ mất x2x^2x2 giây để ăn. Người chủ này muốn cắt cà rốt thành kkk phần sao cho tổng thời gian ăn hết kkk phần này là nhỏ nhất có thể.Giới hạn:Xét hàm fi(p)f_i(p)fi​(p) là tổng thời gian ăn nhỏ nhất nếu ta chỉ xét củ cà rốt aia_iai​, và củ cà rốt này được chia thành đúng ppp phần.Nhận xét rằng ta có thể tính fi(x)f_i(x)fi​(x) trong độ phức tạp O(1)O(1)O(1) với mọi xxx: để ý rằng khi chia củ cà rốt iii thành xxx phần, các phần này cần có độ dài cách nhau tối đa là 111 (ta có thể chứng minh bằng việc nhận xét rằng fi(x)f_i(x)fi​(x) là tổng t12+t22+⋯+tx2t_1^2 + t_2^2 + \dots + t_x^2t12​+t22​+⋯+tx2​ với t1+t2+⋯+tx=ait_1 + t_2 + \dots + t_x = a_it1​+t2​+⋯+tx​=ai​, từ đó ta có thể dùng cách lập luận tham chi phí tăng để chứng minh điều này, chi tiết xin để dành cho bạn đọc).Quan trọng hơn, ta nhận thấy là mọi fif_ifi​ là hàm lồi. Để chứng minh điều này với mọi iii, ta giả sử củ cà rốt n+1n + 1n+1 có độ dài là 2ai2a_i2ai​. Nhận xét rằng với mọi ppp, 2fi(p)=fn+1(2p)2f_i(p) = f_{n + 1}(2p)2fi​(p)=fn+1​(2p). Đây là vì nếu củ cà rốt thứ n+1n + 1n+1 được chia thành các phần có độ dài xxx và x+1x + 1x+1, thì số lượng đoạn cà rốt có độ dài xxx là chẵn, và tương tự với x+1x + 1x+1; vì thế, ta luôn có thể chia củ cà rốt thứ n+1n + 1n+1 làm đôi, rồi cắt mỗi phần giống nhau. Ngoài ra, fn+1(2p)≤fi(p−1)+fi(p+1)f_{n + 1}(2p) \le f_i(p - 1) + f_i(p + 1)fn+1​(2p)≤fi​(p−1)+fi​(p+1), bởi vì một cách cắt một củ cà rốt có độ dài 2ai2a_i2ai​ thành 2p2p2p phần là cắt đôi củ cà rốt, rồi cắt nửa đầu thành p−1p - 1p−1 phần và nửa sau thành p+1p + 1p+1 phần. Bởi thế, 2fi(p)≤fi(p−1)+fi(p+1)2f_i(p) \le f_i(p - 1) + f_i(p + 1)2fi​(p)≤fi​(p−1)+fi​(p+1), từ đó ta có fi(p+1)−fi(p)≥fi(p)−fi(p−1)f_i(p + 1) - f_i(p) \ge f_i(p) - f_i(p - 1)fi​(p+1)−fi​(p)≥fi​(p)−fi​(p−1).Bởi thế, ta có thể dùng ý tưởng tham lam được đề cập ở phần bài toán tổng quát để cài đặt bài này với độ phức tạp là O((n+k)log⁡n)O((n + k) \log n)O((n+k)logn).Link bài: CF - 1344D.Cho mảng aaa gồm nnn số nguyên dương và một số kkk, bạn cần tìm mảng bbb gồm nnn số nguyên thỏa mãn:In ra mảng bbb thỏa mãn 3 điều kiện này.Giới hạn:Nếu ta đặt fi(x)=x(ai−x2)f_i(x) = x(a_i - x^2)fi​(x)=x(ai​−x2), thì ta nhận thấy là fi(x)f_i(x)fi​(x) là hàm lõm (hay nói cách khác, −fi(x)-f_i(x)−fi​(x) là hàm lồi). Để chứng minh điều này, với mọi xxx ta cófi(x+1)−fi(x)=−3x2−3x−1+aif_i(x + 1) - f_i(x) = -3x^2 - 3x - 1 + a_i fi​(x+1)−fi​(x)=−3x2−3x−1+ai​và vế phải giảm dần khi xxx tăng dần. Vì thế, ta có thể dùng ý tưởng tổng quát như trên. Tuy nhiên, với k∼1014k \sim 10^{14}k∼1014 ở bài toán này, ta không thể trực tiếp sử dụng thuật toán trên. Để tối ưu, ta có thể chặt nhị phân chi phí tăng lớn thứ kkk. Khi đang xét chặt nhị phân với giá trị mmm, ta cần tìm với mọi iii giá trị bib_ibi​ lớn nhất sao cho fi(bi+1)−fi(bi)≥mf_i(b_i + 1) - f_i(b_i) \ge mfi​(bi​+1)−fi​(bi​)≥m; thao tác này có thể được thực hiện với độ phức tạp O(1)O(1)O(1) nếu sử dụng công thức phương trình bậc hai, hoặc với độ phức tạp O(log⁡ai)O(\log a_i)O(logai​) nếu sử dụng thêm 1 vòng chặt nhị phân. Vì thế, ta có thể giải bài trên với độ phức tạp là O(nlog⁡2A)O(n \log^2 A)O(nlog2A) hoặc O(nlog⁡A)O(n \log A)O(nlogA) với A=∑i=1naiA = \sum_{i=1}^n a_iA=∑i=1n​ai​.Một số lưu ý khi cài đặt thuật toán trên: sẽ có thể tồn tại giá trị mmm mà số lượng chi phí tăng <m< m<m bé hơn kkk, nhưng số lượng chi phí tăng ≤m\le m≤m thì lại lớn hơn kkk (vì có thể có nhiều chi phí tăng đúng bằng mmm). Ta cần phải cẩn thận khi cài đặt trường hợp này.Link bài: SEERC 2022 - M.Jerry có một cái cây vô hướng có nnn đỉnh, trong đó mỗi đỉnh được đặt cic_ici​ miếng phô mai.Có một chú chuột hiện đang đứng ở đỉnh 111 và muốn đi tới đỉnh nnn để thoát khỏi cái cây này. Ở mỗi bước, chú chuột này sẽ dùng mũi đánh hơi số lượng phô mai ở những đỉnh kề đỉnh chú chuột đang đứng, rồi di chuyển tới một đỉnh kề ngẫu nhiên với xác suất tỉ lệ thuận với số lượng phô mai hiện có ở đỉnh này. Lưu ý rằng chú chuột này sẽ không bao giờ quay trở lại những đỉnh chú chuột đã đi trước đó. Nếu không còn đỉnh kề nào hợp lệ để di chuyển, chú chuột sẽ bị kẹt ở đỉnh này mãi mãi.Jerry muốn giúp chú chuột này thoát khỏi mê cung (tức là đi tới đỉnh nnn) với xác suất lớn nhất có thể. Để làm được điều này, Jerry có thể đặt thêm một vài miếng phô mai vào các đỉnh ở trong cây. Tuy nhiên, Jerry chỉ có thể sử dụng tối đa xxx miếng phô mai, và Jerry phải đặt một số nguyên các miếng phô mai vào mọi đỉnh.In ra một cách đặt phô mai để Jerry tối đa hóa xác suất chú chuột kia có thể tẩu thoát.Giới hạn:Đầu tiên ta nhận thấy là ta chỉ nên đặt phô mai ở những đỉnh trên đường đi từ 111 tới nnn không bao gồm 111. Ngoài ra, với mỗi đỉnh uuu trên đường đi từ 111 tới nnn, ta có thể tính được bub_ubu​ là tổng số lượng phô mai ở những đỉnh là con của cha của uuu — nói cách khác, cubu\frac{c_u}{b_u}bu​cu​​ là xác suất đi tới đỉnh uuu từ đỉnh cha của uuu trước khi thao tác. Sau khi thêm xux_uxu​ miếng phô mai vào đỉnh uuu, xác suất này trở thành cu+xubu+xu\frac{c_u + x_u}{b_u + x_u}bu​+xu​cu​+xu​​. Vì thế, xác suất đi tới nnn sẽ là là ∏u∈{1→n}cu+xubu+xu\prod_{u \in {1 \to n}} \frac{c_u + x_u}{b_u + x_u}∏u∈{1→n}​bu​+xu​cu​+xu​​. Để thuận tiện hơn, ta xét logarit của hàm này: ∑u∈{1→n}log⁡(cu+xu)−log⁡(bu+xu)\sum_{u \in {1 \to n}} \log(c_u + x_u) - \log(b_u + x_u)∑u∈{1→n}​log(cu​+xu​)−log(bu​+xu​).Nhận xét rằng nếu ta đặt fu(t)=log⁡(cu+t)−log⁡(bu+t)f_u(t) = \log(c_u + t) - \log(b_u + t)fu​(t)=log(cu​+t)−log(bu​+t), thì fuf_ufu​ là hàm lõm. Vì thế, ta có thể đưa về bài toán quen thuộc sau: chọn xux_uxu​ sao cho:Ta có thể áp dụng kĩ thuật ở trên: chặt nhị phân chi phí tăng cuối cùng ttt, rồi ở mỗi đỉnh uuu ta chặt nhị phân xux_uxu​ nhỏ nhất sao cho fu(xu+1)−fu(xu)<tf_u(x_u + 1) - f_u(x_u) < tfu​(xu​+1)−fu​(xu​)<t. Tuy nhiên, độ phức tạp của cách làm này là O(nlog⁡xlog⁡ϵ−1)O(n \log x \log \epsilon^{-1})O(nlogxlogϵ−1) với ϵ\epsilonϵ là độ chính xác cần đạt được; với bài toán này, cách làm này sẽ bị vượt quá thời gian cho phép (ϵ\epsilonϵ có thể xuống tới 10−1910^{-19}10−19).Một ý tưởng cho bài toán này là bỏ giới hạn rằng xux_uxu​ là số nguyên, rồi từ nghiệm thực x^u\hat{x}_ux^u​ nhận được, ta chuyển về xux_uxu​ bằng cách nào đó (kĩ thuật này được gọi là integer program relaxation). Nói cách khác, xét bài toán sau: cho fu(t)=log⁡(cu+t)−log⁡(bu+t)f_u(t) = \log(c_u + t) - \log(b_u + t)fu​(t)=log(cu​+t)−log(bu​+t), chọn x^u\hat{x}_ux^u​ sao choỞ đây, hàm ggg trên tập số thực là hàm lõm nếu g′(t)≤0g’(t) \le 0g′(t)≤0 với mọi ttt. Tương tự, hàm ggg trên tập số thực là hàm lồi nếu g′(t)≥0g’(t) \ge 0g′(t)≥0 với mọi ttt. Nhận thấy là hàm fuf_ufu​ được định nghĩa ở trên cũng là một hàm lõm trên tập số thực.Để giải bài toán trên với nghiệm thực, ta xét ý tưởng tham chi phí tăng nhưng với bước tiến nhỏ. Nói cách khác, ta chọn một hằng số nhỏ dxdxdx nào đó, rồi thực hiện thao tác sau xdx\frac{x}{dx}dxx​ lần:Ta nhận thấy là với nghiệm nguyên, ta lặp thao tác trên với dx=1dx = 1dx=1. Với nghiệm thực, ta lặp thao tác trên nhiều lần với dxdxdx tiến tới 000. Nhận thấy rằng khi dx→0dx \to 0dx→0, fu(x^u+dx)−fu(x^)dx=fu′(x^u)\frac{f_u(\hat{x}_u + dx) - f_u(\hat{x})}{dx} = f’_u(\hat{x}_u)dxfu​(x^u​+dx)−fu​(x^)​=fu′​(x^u​). Từ nhận xét trên và bởi vì fu′f’_ufu′​ là hàm liên tục, ta có thể kết luật rằng nghiệm x^\hat{x}x^ thỏa mãn điều kiện sau với mọi uuu:Vì thế, ta có thể tìm nghiệm thực của bài toán trên như sau: ta chặt nhị phân giá trị ttt; ở mỗi vòng chặt nhị phân và với mỗi uuu, ta giải x^u\hat{x}_ux^u​ sao cho fu′(x^u)=tf’_u(\hat{x}_u) = tfu′​(x^u​)=t (hoặc gán x^u=0\hat{x}_u = 0x^u​=0 nếu f′(x^u)≤tf’(\hat{x}_u) \le tf′(x^u​)≤t). Độ phức tạp của phần này là O(nlog⁡ϵ−1)O(n \log \epsilon^{-1})O(nlogϵ−1) vì ta có thể trực tiếp giải x^u\hat{x}_ux^u​. Ta biết rằng $f’_u(\hat{x}_u) = \frac{1}{c_u + \hat{x}_u} - \frac{1}{b_u + \hat{x}_u}$. Giả sử $c_u < b_u$ (nếu không thì ta không cần phải thêm phô mai vào đỉnh này), thì $f’_u(\hat{x}_u) = t$ là phương trình bậc hai, nhận nghiệm $\hat{x}_u = \frac{\sqrt{\frac{4(b_u - c_u)}{t} + (b_u - c_u)^2} - b_u - c_u}{2}$. Ta nhận được nghiệm thực x^u\hat{x}_ux^u​ của bài toán thực trên; bây giờ ta phải chuyển đổi nghiệm thực này thành nghiệm nguyên xux_uxu​ của bài toán ban đầu. Ta có nhận xét cuối cùng: nghiệm dương phải thỏa mãn xu≥⌊x^u⌋x_u \ge \lfloor \hat{x}_u \rfloorxu​≥⌊x^u​⌋ với mọi uuu, hoặc xu≤⌈x^u⌉x_u \le \lceil \hat{x}_u \rceilxu​≤⌈x^u​⌉ với mọi uuu. Gọi $\hat{x}_u$ là nghiệm thực của bài toán và $x_u$ là nghiệm nguyên của bài toán. Ta chứng minh mệnh đề trên bằng phản chứng. Giả sử tồn tại uuu và vvv sao cho xu≤⌊x^u⌋−1x_u \le \lfloor \hat{x}_u \rfloor - 1xu​≤⌊x^u​⌋−1 và xv≥⌈x^v⌉+1x_v \ge \lceil \hat{x}_v \rceil + 1xv​≥⌈x^v​⌉+1. Để ý rằng bởi vì xu≥0x_u \ge 0xu​≥0, điều này nghĩa rằng x^u≥1\hat{x}_u \ge 1x^u​≥1, tức là fu′(x^u)=tf’_u(\hat{x}_u) = tfu′​(x^u​)=t. Tuy nhiên, ta có:fu(xu+1)−fu(xu)>fu′(xu+1)≥fu′(x^u)=t≥fv′(x^v)≥fv′(xv−1)≥fv(xv)−fv(xv−1).f_u(x_u + 1) - f_u(x_u) > f’_u(x_u + 1) \ge f’_u(\hat{x}_u) = t \ge f’_v(\hat{x}_v) \ge f’_v(x_v - 1) \ge f_v(x_v) - f_v(x_v - 1). fu​(xu​+1)−fu​(xu​)>fu′​(xu​+1)≥fu′​(x^u​)=t≥fv′​(x^v​)≥fv′​(xv​−1)≥fv​(xv​)−fv​(xv​−1).Bởi thế, theo thuật toán tham chi phí tăng, ta phải chọn tăng xux_uxu​ lên xu+1x_u + 1xu​+1 trước khi chọn tăng xv−1x_v - 1xv​−1 lên xvx_vxv​. Vì thế, xxx không phải nghiệm nguyên của bài toán trên.Từ hai nhận xét này, ta nhận thấy nghiệm nguyên có thể được tạo nên từ nghiệm thực bằng một trong hai cách sau:xu=⌊x^u⌋x_u = \lfloor \hat{x}_u \rfloorxu​=⌊x^u​⌋Trên thực tế, với riêng bài toán này, ta chỉ cần sử dụng cách thứ nhất. Mình không biết cách chứng minh điều này, tuy nhiên kể cả khi ta thực hiện cả 2 cách thì độ phức tạp của phần này là O(nlog⁡n)O(n \log n)O(nlogn).Vì thế, bài toán có thể được giải với độ phức tạp O(n(log⁡n+log⁡ϵ−1))O(n (\log n + \log \epsilon^{-1}))O(n(logn+logϵ−1)).Ở đây mình không sử dụng ϵ\epsilonϵ; thay vào đó, điều kiện thoát của mình là khi tổng của x^u\hat{x}_ux^u​ cách xxx tối đa là nnn.