solution

Thân của một vòng lặp là một khối lệnh tuần tự gồm $n$ câu lệnh dạng x = y op z (op $\in \{+,-,*,/\}$), trong đó mỗi biến chỉ được ĐỊNH NGHĨA (xuất hiện ở vế trái) đúng MỘT lần duy nhất trong toàn thân vòng lặp (dạng SSA cục bộ — thứ tự các câu lệnh trong danh sách không nhất thiết phản ánh thứ tự phụ thuộc). Mỗi toán hạng $y$ hoặc $z$ là một hằng số nguyên, hoặc tên một biến. Cho trước tập $E$ gồm các biến "bên ngoài vòng lặp" — giá trị của các biến này không đổi qua mọi lần lặp (ví dụ: hằng số toàn cục, biến chỉ gán trước vòng lặp). Bất kỳ biến nào KHÔNG thuộc $E$ và cũng KHÔNG được định nghĩa bởi thân vòng lặp (ví dụ biến đếm vòng lặp, hay một biến tích lũy được cập nhật ở nơi khác) được xem là thay đổi mỗi lần lặp — KHÔNG bất biến.

Một câu lệnh x = y op z là bất biến vòng lặp (loop-invariant) khi và chỉ khi cả hai toán hạng $y, z$ đều thỏa: là hằng số, HOẶC là biến thuộc $E$, HOẶC là biến được định nghĩa bởi một câu lệnh KHÁC trong thân vòng lặp mà câu lệnh đó CŨNG đã được xác định là bất biến. Tính chất này lan truyền theo dây chuyền nên cần áp dụng lặp tới điểm cố định qua toàn bộ $n$ câu lệnh.

Giả sử vòng lặp chạy $N$ lần ($N \ge 0$). Nếu tất cả câu lệnh bất biến được "kéo" (hoist) ra ngoài vòng lặp — chỉ tính một lần duy nhất, VÔ ĐIỀU KIỆN (dù vòng lặp có thực sự chạy lần nào hay không) — trong khi $n-k$ câu lệnh còn lại ($k$ = số câu bất biến) vẫn chạy đủ $N$ lần bên trong vòng lặp, hãy tính:

(a) $k$ — số câu lệnh bất biến tìm được, và danh sách chỉ số (1-indexed, theo thứ tự xuất hiện trong input) của các câu lệnh đó, tăng dần.

(b) Tổng số lượt thực thi câu lệnh TRƯỚC khi tối ưu: $N \times n$; và SAU khi tối ưu: $k + N \times (n - k)$ (lưu ý: nếu $N = 0$, tổng sau tối ưu vẫn bằng $k$ chứ không phải $0$, vì $k$ câu lệnh đã bị kéo ra chạy vô điều kiện một lần — đây chính là rủi ro thực tế cần cân nhắc khi áp dụng LICM cho các phép toán có thể gây lỗi, dù đề bài giả định mọi phép toán ở đây luôn an toàn).