Editorial for Bedao Mini Contest 14 - OPERATION


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

Gọi ~mi_a~ là giá trị nhỏ nhất của mảng ~a~, ~ma_a~ là giá trị lớn nhất của mảng ~a~, ~x~ là giá trị cần tạo.

Nhận xét: Nếu ~mi_a \le x \le ma_a~ thì ta sẽ tạo được số ~x~ từ mảng ~a~.

Chứng minh: Sau khi thực hiện ~n - 1~ thao tác, ta cần đạt được ~mi_a = ma_a = x~. Ta chứng minh được sau mỗi thao tác, ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng, ta sẽ chia ra ~2~ trường hợp sau:

  • ~x < mi_a~ hoặc ~ma_a < x~: Vì ~mi_a~ sẽ không giảm và ~ma_a~ sẽ không tăng sau mỗi thao tác nên điều kiện ~mi_a = ma_a = x~ sẽ không thể đạt được.

  • ~mi_a \le x \le ma_a~: Ta có thể thực hiện tạo số ~x~ bằng cách sau: Chọn ~2~ số tương ứng với ~mi_a~ và ~ma_a~, xóa ~2~ số đi, thêm ~x~ vào. Sau đó, ở ~n - 2~ thao tác còn lại, chọn số ~x~ và một số bất kỳ trong mảng, xóa ~2~ số này và tiếp tục thêm số ~x~ vào. Dễ thấy, số còn lại trong mảng luôn là ~x~.

Độ phức tạp: ~O(n + q)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.