Phân tích: I, O Bot

Không có lợi ích gì khi mang bóng đi qua gốc tọa độ mà không gửi chúng vào kho. Vì vậy, việc thu gom các bóng có \(X_i>0\) và các bóng có \(X_i<0\) là hai bài toán giống nhau nhưng độc lập. Trong phần dưới đây, giả sử mọi \(X_i>0\) và các bóng đã được sắp theo \(X_i\) tăng dần.

Một lời giải gồm nhiều lượt đi hoặc chuyến khứ hồi từ gốc rồi trở lại, mỗi chuyến thu gom một hoặc hai bóng. Thu gom riêng bóng \(i\) tốn \(2X_i\). Thu gom hai bóng \(i,j\) tốn \(2\max(X_i,X_j)\) nếu chúng khác hình, và \(2\max(X_i,X_j)+C\) nếu chúng cùng hình. Ta nói \(i,j\) được ghép cặp, ký hiệu \((i,j)\), nếu được lấy trong cùng chuyến. Thứ tự các chuyến không ảnh hưởng tổng chi phí, nên có thể xem bài toán tương đương với việc tìm một cách ghép bóng tối ưu.

Quan sát sau sẽ được dùng xuyên suốt phần phân tích.

Quan sát 1

Giả sử cần thu gom \(i\) bóng đầu tiên, với \(i\ge2\), và \(S_i\ne S_{i-1}\). Trong một cách ghép tối ưu, bóng thứ \(i\) được ghép với bóng thứ \(i-1\).

Chứng minh. Xét một cách ghép mà bóng \(i\) không được ghép với bóng \(i-1\), và giả sử bóng \(i\) có hình \(0\).

1. Nếu cả hai bóng đều chưa được ghép, ghép chúng với nhau sẽ tiết kiệm \(2X_{i-1}\).
2. Nếu có cặp \((i-1,j)\) với \(j<i-1\), còn bóng \(i\) chưa được ghép, thay bằng cặp \((i-1,i)\) tiết kiệm ít nhất \(2(X_{i-1}-X_j)\); nếu bóng \(j\) hình \(1\) thì tiết kiệm \(2(X_{i-1}-X_j)+C\).
3. Tương tự, nếu có cặp \((i,j)\) với \(j<i-1\), còn bóng \(i-1\) chưa được ghép, ghép \(i\) với \(i-1\) cũng tiết kiệm ít nhất \(2(X_{i-1}-X_j)\).
4. Cuối cùng, nếu có hai cặp \((i,j)\) và \((i-1,k)\) với \(j,k<i-1\), ta có thể sắp lại thành \((i,i-1)\) và \((j,k)\), tiết kiệm ít nhất \(2(X_{i-1}-\max(X_j,X_k))\).

Test Set 1

Quan sát 1 giúp ghép bóng khi hai bóng cuối khác hình. Nhưng nếu chúng cùng hình, chẳng hạn đều là \(0\), thì sao?

Quan sát 2

Giả sử cần thu gom \(i\) bóng đầu tiên, \(i\ge2\), và \(S_i=S_{i-1}=0\). Tồn tại một cách ghép tối ưu thỏa một trong các điều kiện sau:

1. Hai bóng \(0\) cuối cùng, \(i\) và \(i-1\), được ghép với nhau.
2. Có cặp \((i,j)\) với \(S_j=1\), và mọi \(k\in[j+1,i]\) đều có \(S_k=0\). Nói cách khác, bóng \(i\) được ghép với bóng \(1\) gần nhất ở bên trái.
3. Không có bóng hình \(1\), và bóng \(i\) không được ghép.

Chứng minh. Chứng minh đầy đủ là một phép phân tích nhiều trường hợp khá dài nên được lược khỏi bài phân tích chính thức. Ý tưởng là ghép bóng \(i\) với bóng ngoài cùng bên phải của một hình thường không tệ hơn ghép với một bóng khác cùng hình. Chẳng hạn, giả sử \(i\) được ghép với bóng hình \(1\) ở vị trí \(l\), trong khi còn một bóng hình \(1\) ở vị trí \(j\) với \(l<j<i\). Nếu \(j\) chưa được ghép, thay \(l\) bằng \(j\) tiết kiệm \(2(X_j-X_l)\). Nếu \(j\) đã ghép với bóng \(k\), ta có thể đổi vai trò của \(l\) và \(j\), tạo các cặp \((i,j)\) và \((k,l)\), giữ nguyên tổng chi phí khi \(k>j\) hoặc làm chi phí tốt hơn.

Vì vậy, ta có thể thử ghép bóng \(0\) cuối cùng với bóng \(0\) ngay trước nó hoặc với bóng \(1\) ngoài cùng bên phải nếu tồn tại; ít nhất một trong hai lựa chọn sẽ là tối ưu.

Hai quan sát dẫn đến một quy hoạch động. Gọi \(dp[i][j]\) là thời gian tối ưu để thu gom \(i\) bóng hình \(0\) đầu tiên và \(j\) bóng hình \(1\) đầu tiên. Trạng thái cơ sở là \(dp[0][0]=0\). Với \(i+j>0\), giả sử bóng ngoài cùng bên phải trong số này có hình \(0\) và tọa độ \(x\); trường hợp bóng hình \(1\) đối xứng. Để loại các trường hợp biên khác, đặt \(dp[1][0]=2x\), \(dp[i][0]=\min(dp[i-1][0],dp[i-2][0]+C)+2x\) với \(i\ge2\), và \(dp[1][j]=dp[0][j-1]+2x\) với \(j\ge1\). Trong trường hợp tổng quát \(i\ge2,j\ge1\), nếu bóng áp chót có hình \(1\) thì \(dp[i][j]=dp[i-1][j-1]+2x\) theo Quan sát 1. Nếu không, theo Quan sát 2, ta ghép bóng \(0\) cuối với bóng \(0\) trước đó hoặc bóng \(1\) ngoài cùng bên phải:

Đáp án cuối là \(dp[N_0][N_1]\), trong đó \(N_0,N_1\) là tổng số bóng hình \(0\) và \(1\). Độ phức tạp thời gian là \(O(N^2)\).

Test Set 2

Nhìn quy hoạch động theo một hướng khác, ta giải được bài toán trong thời gian tuyến tính ngoài bước sắp xếp. Gọi \(dp[i]\) là thời gian tối ưu để thu gom \(i\) bóng đầu tiên. Các trạng thái cơ sở là \(dp[0]=0\), \(dp[1]=2X_1\). Để tính \(dp[i]\) với \(i\ge2\), lại giả sử bóng \(i\) có hình \(0\). Nếu bóng \(i-1\) có hình \(1\), ghép hai bóng cuối và có \(dp[i]=dp[i-2]+2X_i\) theo Quan sát 1. Nếu không, Quan sát 2 cho phép ghép hai bóng \(0\) cuối, với chi phí \(dp[i-2]+C+2X_i\), hoặc ghép bóng \(i\) với bóng \(1\) ngoài cùng bên phải ở vị trí \(j\). Tuy nhiên, công thức quy hoạch động cho lựa chọn sau chưa hiển nhiên, vì ngoài bóng \(j\) ta không biết cách ghép tối ưu của \(i-1\) bóng đầu. Các bóng \(0\) giữa \(j\) và \(i\) sẽ ra sao? Ta còn thiếu một quan sát then chốt.

Quan sát 3

Nếu tồn tại một cách ghép tối ưu của \(i\) bóng đầu trong đó bóng \(0\) ở vị trí \(i\) được ghép với bóng \(1\) ngoài cùng bên phải ở vị trí \(j\), và \(i-1\ne j\), thì bóng \(0\) ở vị trí \(i-1\) không được ghép với một bóng \(0\) khác.

Chứng minh. Giả sử ngược lại có hai cặp \((i,j)\) và \((i-1,k)\), với \(k<i-1\) và bóng \(k\) hình \(0\). Hai cặp đóng góp \(2X_i+2X_{i-1}+C\) vào tổng chi phí. Ta có thể sắp lại thành \((i,i-1)\) và \((j,k)\), chỉ tốn \(2X_i+C+2\max(X_j,X_k)\), ít hơn \(2(X_{i-1}-\max(X_j,X_k))\). Điều này mâu thuẫn với tính tối ưu.

Từ Quan sát 3, bóng \(0\) ở vị trí \(i-1\) phải được ghép với một bóng \(1\) khác, cụ thể là bóng \(1\) chưa ghép ngoài cùng bên phải. Có thể tiếp tục lập luận này, quét dần sang trái và ghép bóng \(0\) với bóng \(1\) chừng nào bên phải một bóng \(1\) đã ghép vẫn còn bóng \(0\). Quá trình được minh họa dưới đây.

Gọi \(k\) là bóng chưa ghép ngoài cùng bên phải sau quá trình ghép \(0\)–\(1\). Trong tập \(\{k+1,k+2,\ldots,i\}\) không có lần đổi hình nào, và chi phí thu gom các bóng đó bằng hai lần tổng tọa độ \(X_{\text{bóng 0}}(k+1,i)\) của các bóng hình \(0\) trong tập. Do đó, tổng chi phí theo cách này là

Có thể tính \(X_{\text{bóng 0}}(k+1,i)\) trong \(O(1)\) bằng tổng tiền tố. Nhưng làm sao tìm \(k\) hiệu quả mà không thực sự thực hiện toàn bộ quá trình ghép? \(k\) là chỉ số lớn nhất thỏa \(k<i\) và đoạn \(\{k+1,\ldots,i\}\) có số bóng \(0\) bằng số bóng \(1\). Xét cân bằng tại chỉ số \(i\): \(b_i=z_i-o_i\), với \(z_i,o_i\) lần lượt là số bóng \(0\) và \(1\) trong \(\{1,\ldots,i\}\). Đoạn \(\{k+1,\ldots,i\}\) có số lượng hai hình bằng nhau khi và chỉ khi \(b_k=b_i\). Ta tìm \(k\) trong \(O(1)\) nếu duy trì bảng băm lưu chỉ số gần nhất mà mỗi giá trị cân bằng xuất hiện. Nếu \(b_i\) xuất hiện lần đầu, không có đủ bóng \(1\) để ghép với mọi bóng \(0\), và có thể chọn \(k=0\).

Phương pháp chỉ thực hiện số phép toán hằng số tại mỗi chỉ số. Vì thế, độ phức tạp tổng thể bị chi phối bởi bước sắp xếp và bằng \(O(N\log N)\).

Dữ liệu kiểm thử

Google khuyến nghị bạn luyện gỡ lỗi lời giải mà không xem dữ liệu kiểm thử.

Phân tích chính thức của Google Code Jam 2022, Vòng 2, bài I, O Bot.