Greedy Algorithm

Để hiểu thuật toán này là gì, các bạn có thể tìm hiểu qua trang vnoi wiki hoặc đọc cuốn competitive 2 or 3, ở bài viết này, mình xin giải các bài tập tham ăn trong cp2 và trên hackerrank.

Về các bài về interval, mình thấy có hai bài:

Thứ nhất là ví dụ một về tham ăn trên vnoi wiki, đó là trên 1 khoảng về thời gian xác định, tính số khoảng con (được cho trước) nhiều nhất có thể (không chồng chéo lên nhau) trên khoảng xác định đó. Đầu tiên, xác định bài toán con mà ta định tham ăn từ đó để được giải thuật tối ưu nhất, đó là mỗi khoảng được chọn thì kết thúc càng sớm càng tốt, để dành thời gian trống cho các khoảng phía sau. Cách làm đó là sắp xếp lại các khoảng con theo thứ tự tăng dần về thời gian kết thúc, chọn khoảng đầu tiên chính là khoảng có thời gian kết thúc sớm nhất, từ đó ta duyệt các đoạn ở phía sau nó trong tập hợp đã được sắp xếp, khoảng đầu tiên không chồng chéo với nó (tức là left của khoảng sau lớn hơn right của khoảng trước). Cứ như vậy, ta sẽ có được danh sách các khoảng phù hợp với yêu cầu bài toán.

Thứ hai là ví dụ 2 trong cuốn cp2 trang 53. Lượt bỏ các vấn đề về nội dung cũng như nhũng biến đổi về hình học, đề bài toán gọn sẽ là tìm số đoạn con (cho trước) ít nhất phủ kín một đoạn lớn cho trước. Một cách tự nhiên ta sẽ biết rằng, khoảng con có left bé nhất sẽ được chọn đầu tiên, vì vậy, ta sẽ sắp xếp các khoảng theo chiều tăng dần về của biên trái. Cách làm sẽ là duyệt từng khoảng một, và khoảng đó phải thỏa mãn 2 yếu tố, một là phủ kín, tức là nó phải bé hơn biên phải trước nó, hai là nó phải có biên phải dài nhất trong tất cả các khoảng thỏa yếu tố 1.

uva10382
 solution

 

Các bài toán implement (p2)

1. Bài toán Larry’s array

Đề bài: Larry’s array

Bài toán này là bài toán in ra Yes và No và điều này thường có nghĩa là chúng ta sẽ nhìn nhận vấn đề một cách tổng quát chứ không thực hiện các thao tác biến đổi trên input.

inversion, nó có nghĩa số các cặp số đứng sai vị trí theo yêu cầu được sắp xếp của mảng. Ví dụ như A=[1,5,2,6,4,3], muốn xếp A tăng dần thì các inversion sẽ là (5,2), (5,4), (5, 3), (6,4), (6,3) (1 < x < y < N && Ax > Ay). 

Bây giờ khi thực hiện thao tác của đề bài thì tính chẵn lẻ của số lượng inversion sẽ là không đổi. Thật vậy, giả sư khi ta thực hiện A,B,C->B,C,A thì nếu A > C, sau khi thay đổi ta sẽ có -1 đi số inversion trong mảng, tương tự là sẽ là cộng thêm 1 nếu A < C. Tương tự cho A và B, khi đó dễ thấy sự thay đổi sẽ là -2, 0, 2, điều này sẽ không làm thay đổi tính chẵn lẽ của inversion.

Continue reading “Các bài toán implement (p2)”