Phân tích: Crazy Rows

Phát biểu lại bài toán

Dễ dàng nhận thấy, đối với mỗi hàng, chỉ có vị trí của số '1' cuối cùng là quan trọng. Chúng ta có thể phát biểu lại bài toán như sau:

CR: Cho một danh sách số \((a_0, \ldots, a_{N-1})\). Bạn được phép tráo đổi hai số kề nhau. Hãy tìm số lần tráo đổi ít nhất để trong cấu hình cuối cùng, số thứ \(i\) không vượt quá \(i\).

Trường hợp đặc biệt quen thuộc

Có lẽ nhiều bạn đã biết trường hợp đặc biệt sau đây:

CR*: Cho một hoán vị \((x_0, \ldots, x_{N-1})\) của các số từ 0 đến \(N-1\). Bạn được phép tráo đổi hai số kề nhau. Hãy tìm số lần tráo đổi ít nhất để sắp xếp danh sách theo thứ tự tăng dần.

Có lẽ bạn cũng đã biết lời giải đầy đủ cho CR*. Lời giải cho CR* rất đơn giản và thanh lịch, đồng thời quan trọng đối với bài toán của chúng ta.
Lời giải (cho CR*): Định nghĩa độ nghịch thế (disorder) của danh sách là số cặp \(i < j\) mà \(x_i > x_j\). Trong một lần tráo đổi (hai số kề nhau), tổng số độ nghịch thế thay đổi đúng một đơn vị. Do đó, nếu độ nghịch thế của cấu hình ban đầu là \(D\), bạn cần ít nhất \(D\) lần tráo đổi. \(D\) lần tráo đổi cũng là đủ — miễn là danh sách chưa được sắp xếp, luôn tồn tại các cặp kề nhau sai thứ tự. Bạn có thể tráo đổi bất kỳ cặp nào như vậy và giảm độ nghịch thế đi 1.

Đặc biệt:

(1) Một dạng lời giải tối ưu của CR* là trước tiên đưa số 0 bằng các phép tráo đổi về tận cùng bên trái, rồi để nó ở đó mãi mãi.

Lời giải cho bài toán

Giả sử chúng ta biết số \(a_i\) nào cuối cùng sẽ chuyển đến vị trí 0, số nào sẽ chuyển đến vị trí 1, v.v., thì chúng ta chỉ cần sử dụng thuật toán cho CR*. Nhưng có thể có nhiều ứng cử viên cho một vị trí duy nhất. Ví dụ, có thể có nhiều \(i\) sao cho \(a_i = 0\), hoặc thậm chí một số \(a_i = -1\).

Dưới đây là giải pháp C++ của ban giám khảo. b[i] là vị trí "đã giải mã" nơi a[i] sẽ ở trong cấu hình cuối cùng. Thuật toán là: Đối với các ứng cử viên cho vị trí 0, hãy chọn ứng cử viên nằm bên trái nhất. Sau đó, trong số còn lại, đối với các ứng cử viên cho vị trí 1, hãy chọn ứng cử viên nằm bên trái nhất, và cứ tiếp tục như vậy.

  // -1 means no position is assigned for a[j].
  for(i=0;i<N;i++) b[j]=-1;
  for(i=0;i<N;i++) {
    for(j=0;j<N;j++) if(b[j]<0 && a[j]<=i) {
        b[j]=i; break;
      }
  }
  int r=0;
  for(i=0;i<N;i++) for(j=i+1;j<N;j++) 
    if(b[i]>b[j]) r++;
  // output r as the answer

Lưu ý rằng, một khi các giá trị b[i] đã được cố định, bạn chỉ cần đếm số nghịch thế như trong *CR*; không cần mô phỏng việc tráo đổi thực tế.

Chứng minh lời giải

Quan sát then chốt là, đối với nhiều ứng cử viên cho vị trí 0, bạn sẽ không bao giờ cần tráo đổi bất kỳ hai ứng cử viên nào trong số họ. Giả sử bạn có tráo đổi \(u\) và \(v\), cả hai đều \(\le 0\). Tôi có thể đơn giản là bỏ qua nó, và giả vờ rằng chúng đã được tráo đổi (tức là trao đổi vai trò của \(u\) và \(v\) sau đó). Cấu hình cuối cùng vẫn là một cấu hình tốt. Do đó, chúng ta đã chứng minh được rằng, trong tất cả các ứng cử viên cho vị trí 0, ứng cử viên nằm bên trái nhất, gọi là \(u^*\), cuối cùng sẽ đi đến vị trí 0.

Bây giờ, hãy tưởng tượng chúng ta đã giải mã được các vị trí cuối cùng cho mọi số. Khi đó (1) cho chúng ta biết rằng có một lời giải mà trước tiên chúng ta di chuyển \(u^*\) về tận cùng bên trái, và không bao giờ lo lắng về nó nữa. Do đó, bây giờ chúng ta đối mặt với câu hỏi tiếp theo: Số nào trong các số còn lại nên đi đến vị trí 1?
Đây chính xác là cùng một bài toán, nhưng với ít hơn một số.

Nguồn

Bản dịch dựa trên phân tích chính thức của Google Code Jam 2009 - Round 2 - Crazy Rows, thuộc kho Google Coding Competitions (Apache-2.0).