Khoảng giá trị khả thi

Ta cần tìm một mức lương \(X\) sao cho mọi mức lương trong công ty sau khi cho nghỉ việc đều nằm giữa \(X\) và \(X+D\), đồng thời số nhân viên còn lại là lớn nhất.

Nếu giữ nhân viên \(i\), ta phải có

Không chỉ vậy, \(X\) cũng phải thuộc \([S_j-D,S_j]\) với mọi nhân viên \(j\) là quản lý của \(i\), quản lý của quản lý đó, và cứ thế cho đến CEO. Do đó, với mỗi nhân viên, ta cần tìm giao của tất cả các khoảng trên đường từ gốc đến nhân viên ấy. Có thể tính dễ dàng bằng một lượt duyệt tiền thứ tự trên cây, mang theo giao của các khoảng trên đường đi. Nếu giao rỗng thì không thể giữ nhân viên đó.

Tìm điểm được nhiều khoảng phủ nhất

Gọi khoảng thu được cho nhân viên \(i\) là \([A_i,B_i]\). Tạo một mảng các cặp số nguyên, gồm hai cặp cho mỗi nhân viên: \((A_i,+1)\) và \((B_i,-1)\). Sắp xếp mảng theo thành phần thứ nhất; nếu bằng nhau, dùng thành phần thứ hai để đặt các sự kiện \(+1\) trước các sự kiện \(-1\), vì hai đầu mút của khoảng đều được tính.

Khởi tạo bộ đếm bằng 0 rồi duyệt mảng theo thứ tự đã sắp xếp, cộng thành phần thứ hai của mỗi cặp vào bộ đếm. Giá trị lớn nhất mà bộ đếm đạt được chính là đáp án.

Duyệt cây tốn \(O(N)\); sắp xếp các sự kiện tốn \(O(N\log N)\) thời gian và dùng \(O(N)\) bộ nhớ.

Dựa trên phân tích chính thức của Google Code Jam.