Editorial for Bedao Regular Contest 02 - LEAVES
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ý 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