Hướng dẫn cho Google Code Jam 2008 - Minimum Scalar Product
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Phân tích: Minimum Scalar Product
Mặc dù tên bài toán mang âm hưởng hình học, nhưng thực chất đây là bài toán về hai mảng số.
Có hai hoán vị liên quan ở đây. Tuy nhiên, sau khi bạn cố định hoán vị cho \(V_1\), bạn hoàn toàn tự do trong việc chọn hoán vị cho \(V_2\). Rõ ràng là hoán vị đầu tiên không thực sự quan trọng. Điều quan trọng là \(x_i\) nào sẽ được ghép cặp với \(y_j\) nào.
Để tư duy dễ dàng hơn, chúng ta có thể giả định hoán vị đầu tiên thỏa mãn:
x1 ≤ x2 ≤ ... ≤ xn. (1)
Và nhiệm vụ của chúng ta là ghép các giá trị \(y\) với các giá trị \(x\) sao cho tích vô hướng là nhỏ nhất có thể.
Tại thời điểm này, nếu bạn cần một bài tập nhỏ: Hãy thử suy nghĩ về trường hợp \(n = 2\) với một ví dụ cụ thể. Bạn chắc chắn sẽ phát hiện ra rằng, để đạt được tích vô hướng tối thiểu, bạn luôn muốn ghép \(x_i\) nhỏ hơn với \(y_j\) lớn hơn.
Điều chúng ta muốn chứng minh là: dưới điều kiện (1), một trong những lời giải tối ưu sẽ có dạng:
y1 ≥ y2 ≥ ... ≥ yn. (2)
Chứng minh chặt chẽ cho (2) được trình bày ở cuối phần phân tích này. Để dễ hiểu, chúng tôi chỉ ra rằng bước then chốt chính là trường hợp \(n = 2\). Nếu \(x < x'\) và \(y < y'\), thì:
(xy + x'y') - (xy' + x'y) = (x - x')(y - y') > 0. (*)
Vì vậy, chúng ta ưu tiên ghép các giá trị \(y\) lớn với các giá trị \(x\) nhỏ.
Thuật toán
Do đó, bài toán này được giải bằng thuật toán đơn giản sau:
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end(), greater<int>());
long long ret = 0;
for (int i = 0; i < n; i++)
ret += (long long)(v1[i]) * v2[i];
Chứng minh (2)
Chúng ta chứng minh rằng bất kỳ hoán vị nào không thỏa mãn (2) đều có thể được biến đổi thành một hoán vị thỏa mãn (2), và trong mỗi bước biến đổi, chúng ta không làm tăng tích vô hướng.
Thật vậy, bất kỳ mảng nào chưa được sắp xếp đều có thể được biến đổi thành mảng đã sắp xếp chỉ bằng cách tráo đổi các phần tử kề nhau bị ngược thứ tự. (Đối với những độc giả muốn sự chặt chẽ hơn: hãy chứng minh điều này, có thể bằng cách đếm số cặp nghịch thế trong mảng.)
Tại mỗi bước, giả sử một giá trị \(x = x_i\) được ghép với một giá trị \(y\), và \(x' = x_{i+1}\) được ghép với một giá trị \(y'\) sao cho \(y \le y'\). Chúng ta tráo đổi \(y\) và \(y'\) trong bước này. Bất đẳng thức tương tự như (*), với dấu \(>\) được thay bằng \(\ge\), cho chúng ta biết rằng tích vô hướng không tăng lên trong bước này. ◊
Thông tin thêm:
Dựa trên phân tích chính thức của Google Code Jam.
Bình luận