Editorial for Bedao Regular Contest 03 - RACE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Ta sẽ chia lời giải ra làm hai phần:

1, Số lượng va chạm đã diễn ra trong cuộc thi ngay trước khi mọi chú chó cán đích:

  • Nhận xét rằng khi hai chú chó va chạm, thay vì đổi vận tốc của hai chú chó theo chiều ngược lại, chúng ta có thể xem rằng hai chú chó vẫn giữ nguyên vận tốc, nhưng ID của hai chú chó thay đổi.

  • Khi đó bài toán trở thành cho một số đường chéo đi lên, và một số đường chéo đi xuống, đếm số cặp đường chéo giao nhau.

  • Chúng ta sort các đường chéo đi lên theo thứ tự tăng dần. Khi đó, với mỗi đường chéo đi xuống, ta có thể sử dụng thuật toán chặt nhị phân (hoặc hai con trỏ nếu sort cả các đường chéo xuống) để đếm xem có bao nhiêu đường chéo lên đã cắt.

  • Ngoài ra, còn một cách khác để giải đó là nếu ta lấy mảng tọa độ vị trí cuối cùng, nhưng ID của mỗi chú chó không thay đổi qua va chạm. Số lượng cặp nghịch thế trên mảng này cũng chính là kết quả.

2, Tọa độ ~y_i~ là vị trí cán đích của chú chó thứ ~i~:

  • Nhận xét rằng vị trí tương đối của mỗi chú chó so với những chú chó còn lại là không thay đổi. Điều này có nghĩa rằng nếu ban đầu, chú chó thứ ~i~ đứng ở dưới cùng, thì sau khi kết thúc cuộc thi, chú chó thứ ~i~ vẫn đứng ở dưới cùng.

  • Do đó, ta sinh ra ~n~ tọa độ vị trí cuối cùng từ ~n~ tọa độ vị trí ban đầu.

  • Vì vị trí tương đối không thay đổi, ta gán ID cho từng vị trí từ dưới lên, tương tự như thứ tự ID ở mảng ban đầu.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.