Editorial for Bedao Regular Contest 02 - LEAVES


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

Ý tưởng 1

Gọi ~cnt_i~ là đếm số node và lá có độ cao là i

Dễ thấy với từng ~i~ độ cao muốn nó thành một cây nhị phân đầy đủ thì số lượng node và lá có độ cao là ~i~ đều phải là một số chẵn, để đếm số lượng node và lá có độ cao là ~i~ thì ta có các nhận xét như sau:

  • Tổng số lượng node có độ cao ~i~ bằng tổng số node và lá có độ cao là ~i+1~ chia cho ~2~ hay ~\frac{cnt_{i+1}}{2}~

Vậy ta chỉ cần duyệt ngược lại từ độ cao cao nhất về độ cao là ~1~, mỗi lần duyệt ta kiểm tra xem với độ cao ~i~ có số lượng node và lá là ~cnt_i~ thì nó có thỏa mãn là cây nhị phân không khi và chỉ khi ~cnt_i~ là một số chẵn và nếu thỏa mãn thì ta cập nhật số lượng node và lá cho độ cao ~i-1~

Lưu ý: Ta cần phải xét xem số lượng gốc của cây hay là ~cnt_0~ có thỏa mãn luôn luôn bằng ~1~, nếu thỏa mãn cùng với điều kiện trên thì đây là cây nhị phân đầy đủ.


Ý tưởng 2

Sử dụng hàng đợi ưu tiên - priority queue để mô phỏng lại cách từ lá lên đỉnh gốc

Gọi ~pq~ là tập hợp độ cao của nút lá và phần tử đầu tiên của ~pq~ chính là nút lá có độ sâu cao nhất

Khi ~pq~ vẫn còn nhiều hơn ~1~ phần tử thì ta sẽ lấy trong ~pq~ hai phần tử mỗi lượt là:

  • ~best~ là nút lá có độ cao cao nhất

  • ~secondBest~ là nút lá có độ cao cao nhì ( tức có độ cao bé hơn hoặc bằng ~best~ )

Nếu ~best = secondBest~ thì ta sẽ thêm vào ~pq~ độ cao ~best-1~ ( hoặc ~secondBest-1~ ) và có khả năng tạo được cây nhị phân đày đủ, ngược lại không thể tạo được cây nhị phân đầy đủ

Vậy chạy đến khi ~pq~ chỉ còn ~1~ phần tử thì kiểm tra xem phần tử còn lại duy nhất trong ~pq~ đó có độ cao bằng ~0~ hay không, nếu không thì không thể tạo được cây nhị phân đầy đủ, ngược lại thì tạo được.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.