Dịch đề:

Bài A div2: 

Có N đại biểu tham gia bầu cử, người thứ i sẽ nhận được a[i] phiếu bầu cử từ a[i] công dân. Người thứ nhất muốn giành chiến thắng, nên tìm cách hối lộ một số công dân để anh ta bầu cử phiếu cho mình. Tính số người ít nhất anh ta cần phải hối lộ, biết người thứ nhất sẽ giành chiến thắng nếu số phiếu của anh ta lớn hơn số phiếu của những người còn lại.

Bài C div2/A div 1:

Cho mảng gồm N số nguyên A1...AN. Mỗi bước có thể chọn một số nguyên trong mảng, tăng gấp 2, gấp 3 lần giá trị của số đó. Hỏi sau một số bước hữu hạn tất cả các phần tử của mảng A đều bằng nhau

Bài D Div2/B div 1:

Cho N cái cột, cột thứ i có độ cao là Hi, tạo thành một số hình. Tại mỗi bước bạn phải xóa toàn bộ viền ngoài của các hình đó. Hỏi sau bao nhiêu bước thì bạn xóa dc toàn bộ các hình đó.

Hóng cao nhân chỉ em bài C div 1 :(

C div 1:

• Gọi cây con gốc u là T(u)
• Đặt f1(u) = có thể trải T(u) thành 1 đường thẳng, và có u ở 1 đầu. --> f1(u) = true khi u có duy nhất 1 con v, và f1(v) = true
• Đặt f2(u) = có thể trải T(u) thành 1 đường thẳng --> f1(u) = true khi u có không quá 2 con v1, v2, và f1(v1) = f1(v2) = true
• Đặt f3(u) = có thể trải T(u) xuống dải 2*N điểm, với 1 phía bị chặn (do u là con của 1 đỉnh nào đó khác). f3(u) = true khi u có không quá 1 con v mà f3(v) = true, các con còn lại w của u phải có f2(w) = true
• Đặt f4(u) = có thể trải T(u) xuống dải 2*N điểm. f4(u) = true khi u có không quá 2 con mà f3(v) = true, các con còn lại phải có f2(w) = true

Tính 4 mảng trên bằng DFS 1 lần trên cây trong O(N).

Sau khi có 4 mảng này, thì bạn giải được bài toán nếu coi đỉnh 1 là gốc của cây.

Tuy nhiên trong bài này có thể đặt đỉnh bất kỳ làm gốc --> bạn cần phải tính thêm 1 số thứ nữa :v bạn có thể đọc code mình (account I_love_Hoang_Yen) nhưng code mình khá phức tạp, tính 4 mảng g1 --> g4 với ý nghĩa tương tự f :))

Chúc mừng anh RR lên international grandmaster

các pro chỉ mình cách làm bài Bdiv1 với

Qhd left[i] là số bước ít nhất để xóa cột thứ i từ bên trái-> left[i]=min(a[i],i,left[i-1]+1)

 right[i] là số bước ít nhất để xóa cột thứ i từ bên phải-> right[i]=min(a[i],n-i+1,right[i+1]+1)

kết quả : max( min(left[i],right[i]) ) :)

Cảm ơn a và chúc mừng a đã lên international grandmaster :)