Editorial for Bedao Grand Contest 11 - HIDDENPER


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

Subtask 1

Với mỗi ~1\le i<n~, ta hỏi hai hoán vị ~P~ và ~Q~ sao cho ~P_0=1,P_i=N~ và ~Q_0=N,Q_i=1~ đồng thời các vị trí còn lại bằng nhau. Ta nhận được hai tổng ~X_0-X_i+C~ và ~X_i-X_0+C~, từ đây ta tính được hiệu ~X_i-X_0~. Để ý rằng khi ~X_i=1~ thì hiệu này đạt giá trị nhỏ nhất, ta tính được ~X_0~ và từ đó dễ dàng khôi phục được hoán vị.</p>

Subtask 2

Ở subtask 1 ta chỉ mới sử dụng giá trị ~1~ và ~N~, để giảm số câu hỏi ta sẽ sử dụng thêm giá trị ~2~. Và để phá được dấu giá trị tuyệt đối thì ta chỉ nên đặt ~2~ vào các vị trí mà ta đã biết nó lớn hơn ~1~.

Xét ba vị trí ~i, j, k~ với điều kiện ta đã biết ~X_i>1~. Ta hỏi hai hoán vị ~P~ và ~Q~ sao cho ~P_i=2,P_j=1,P_k=N~ và ~Q_i=2,Q_j=N,Q_k=1~. Ta nhận được hai tổng ~X_i+X_j-X_k+C~ và ~X_i-X_j+X_k+C~, tính hiệu ~X_j-X_i~ và xác định vị trí lớn hơn, giả sử đó là ~j~. Ta hỏi tiếp hoán vị ~R~ sao cho ~R_i=N,R_j=2,R_k=1~ và nhận được tổng ~-X_i+X_j+X_k+C~. Từ đây dễ dàng tìm được ~X_k-X_i~. Trường hợp ~k~ là chỉ số lớn hơn ta xử lý tương tự.

Trở lại với bài toán, đầu tiên ta tìm hiệu ~X_1-X_0~ và xác định vị trí chắc chắn lớn hơn ~1~. Sau đó cứ mỗi hai phần tử liên tiếp ta áp dụng thuật toán trên và thu được các hiệu, từ đó sử dụng nhận xét ở cuối subtask 1 để khôi phục hoán vị.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.