Phân tích

Bài toán này đơn giản hơn so với dự kiến, vì các ràng buộc không yêu cầu bạn phải viết một giải pháp cực kỳ tối ưu. Để giải quyết nó, bạn chỉ cần duyệt qua từng cặp dây và kiểm tra xem chúng có cắt nhau hay không.

Việc kiểm tra giao điểm có thể được thực hiện theo nhiều cách. Một cách là viết phương trình của hai đường thẳng và sau đó giải hệ phương trình tuyến tính hai ẩn để tìm giao điểm. Một cách dễ dàng hơn là chỉ cần kiểm tra xem thứ tự các đầu mút của cặp dây trên tòa nhà thứ nhất có ngược lại với thứ tự các đầu mút của chúng trên tòa nhà thứ hai hay không. Cụ thể, hai sợi dây \((A_i, B_i)\) và \((A_j, B_j)\) cắt nhau khi và chỉ khi:

• \((A_i > A_j\) và \(B_i < B_j)\) hoặc \((A_i < A_j\) và \(B_i > B_j)\).

Điều này có thể được chuyển thành mã giả như sau:

(A[i] - A[j]) * (B[i] - B[j]) < 0

Độ phức tạp

Thuật toán này tốn \(O(N^2)\) và nó đủ nhanh để giải quyết bài toán với \(N \le 1000\).

Hướng tiếp cận tối ưu hơn

Bài toán này rất giống với bài toán kinh điển tìm số lượng nghịch thế (inversions) trong một hoán vị cho trước. Một nghịch thế của một hoán vị \(p\) là một cặp chỉ số \(i < j\) sao cho \(p_i > p_j\).

Hãy xem tại sao hai bài toán này tương đương nhau. Nếu \(ra\) là thứ hạng của \(A_i\) khi chúng ta sắp xếp mảng \(A\) và \(rb\) là thứ hạng của \(B_i\) khi chúng ta sắp xếp mảng \(B\), thì bài toán các sợi dây trở thành bài toán đếm số nghịch thế trên hoán vị \(p\) trong đó \(p_{ra} = rb\) với mỗi \(i\).

Bài toán mới này là một ứng dụng tốt cho các thuật toán chia để trị, và có thể được giải trong thời gian \(O(N \log N)\). Thuật toán sắp xếp trộn (Merge sort) có thể được điều chỉnh một cách khéo léo để không chỉ sắp xếp mảng mà còn đếm số lượng nghịch thế. Các giải pháp khác sử dụng các cấu trúc dữ liệu như cây phân đoạn (segment tree), cây tìm kiếm nhị phân cân bằng (augmented balanced binary search tree) hoặc danh sách liên kết nhảy (augmented skip list).

Bạn có thể tìm hiểu thêm về: Số lượng nghịch thế trong một hoán vị.

Dựa trên phân tích chính thức của Google Code Jam.