Phân tích: The Great Wall

Dữ liệu nhỏ

Dù đề rất dài, dữ liệu nhỏ không khó; chính độ dài của đề đã khiến nhiều thí sinh e ngại, nên phải sau nửa giờ mới có bài nộp đầu và tổng số bài nộp khá ít. Với tối đa 10 bộ lạc, mỗi bộ lạc tối đa 10 đợt tấn công, và mọi đợt chỉ diễn ra trên một đoạn tường ngắn, ta có thể mô phỏng toàn bộ.

Vì \(\Delta p\) bị chặn bởi 10, một bộ lạc tấn công tối đa 10 lần, và vị trí đợt đầu nằm trong \([-100,100]\), mọi đợt tấn công đều nằm trong \([-200,200]\). Ta đủ sức lưu độ cao tường ở mỗi điểm đáng quan tâm. Vấn đề là những điểm nào cần quan tâm?

Biên vùng tấn công luôn nguyên, nên độ cao tường là hằng số trên mỗi khoảng mở \((x,x+1)\) với \(x\) nguyên. Hơn nữa, độ cao tại điểm nguyên không bao giờ thấp hơn cả hai khoảng mở kề nó, vì mọi đợt tấn công ảnh hưởng một khoảng kề cũng ảnh hưởng điểm nguyên sát đó. Do \(w_i<e_i\), mỗi đợt luôn phủ ít nhất một khoảng trọn vẹn; thành công chỉ phụ thuộc độ cao trên các khoảng, không phụ thuộc các đầu mút. Vì vậy chỉ cần lưu độ cao tại các điểm dạng \(x+0.5\). Dữ liệu nhỏ có 400 điểm như vậy, ban đầu đều cao 0.

Có tối đa 100 đợt tấn công. Sinh tường minh tất cả, ghi ngày, đầu, cuối và sức mạnh, rồi sắp xếp theo thời gian. Với mỗi ngày có tấn công, trước hết kiểm tra thành công của tất cả đợt trong ngày bằng độ cao hiện tại trên các khoảng bị đánh; sau đó mới đi qua mọi đợt và nâng tường khi cần. Điều quan trọng là chỉ nâng tường sau khi đã kiểm tra xong mọi đợt cùng ngày.

Dữ liệu lớn

Dữ liệu lớn có thể có \(10^6\) đợt tấn công trên một đoạn dài hơn \(10^8\). Ta vẫn có thể sinh mọi đợt và sắp xếp theo thời gian, nhưng cần biểu diễn tường gọn hơn, đồng thời kiểm tra và cập nhật nhanh hơn.

Nén tọa độ

Vì chỉ có \(10^6\) đợt, chỉ có cỡ \(10^6\) tọa độ đáng quan tâm. Sắp xếp mọi tọa độ đầu và cuối của các đợt, rồi chỉ xét một điểm giữa mỗi cặp đầu mút kề nhau. Có tối đa \(2\cdot10^6\) điểm; mỗi điểm đại diện một khoảng mà độ cao tường luôn đồng nhất. Đổi tên chúng thành các chỉ số liên tiếp. Sau phép nén này, mọi đợt tấn công diễn ra trong không gian tối đa \(2\cdot10^6\) điểm.

Để kiểm tra thành công và cập nhật tường, cần một biến thể của cây đoạn. Sau đây là hai cách.

Cây đoạn có các nút đại diện những khoảng chuẩn độ dài lũy thừa của hai, dạng \([m2^k,(m+1)2^k]\) (theo quy ước đầu mút thích hợp). Cha của khoảng \(I\) là khoảng chuẩn dài gấp đôi chứa \(I\); chẳng hạn cha của khoảng ứng với \(m,k\) là khoảng ứng với \(\lfloor m/2\rfloor,k+1\). Cấu trúc này quen thuộc; điểm mấu chốt là lưu gì trong nút.

Cách 1: hi và lo

Mỗi nút lưu hai giá trị hi và lo. hi được định nghĩa sao cho độ cao tường tại một điểm bằng giá trị hi lớn nhất trong mọi khoảng-nút chứa điểm đó. Một đoạn bất kỳ tách thành \(O(\log n)\) khoảng chuẩn; khi bị tấn công, cập nhật hi trên các nút ấy. Nhờ vậy cập nhật tường và truy vấn độ cao tại một điểm đều làm được trong thời gian logarit. Ta còn cần kiểm tra một đợt tấn công thành công hay không cũng nhanh như vậy.

Giá trị lo phục vụ việc đó. Với nút \(X\) và một đường từ \(X\) xuống lá, gọi hi lớn nhất trên đường là độ cao bộ phận của lá: đó là độ cao nếu bỏ qua mọi nút phía trên \(X\). Đặt lo của \(X\) là độ cao bộ phận nhỏ nhất trong các lá hậu duệ của \(X\).

Khi biết lo của một nút, độ cao nhỏ nhất của tường trong khoảng nút đó là giá trị lớn hơn giữa lo của nút và mọi hi trên các tổ tiên. Để kiểm tra một đoạn tấn công, tách nó thành \(O(\log n)\) khoảng-nút, tìm đoạn tường thấp nhất trong mỗi khoảng; nếu có đoạn thấp hơn sức mạnh tấn công thì đợt đó thành công. Mô tả trực tiếp cho \(O(\log^2 n)\), nhưng dễ hiện thực thành \(O(\log n)\).

lo có công thức đệ quy đơn giản: lấy giá trị lớn hơn giữa hi của chính nút và giá trị nhỏ nhất trong lo của các con. Khi cập nhật hi của một nút, chỉ cần cập nhật lo của nút đó và các tổ tiên. Cách thẳng cho \(O(\log^2 n)\) mỗi đợt, và cũng dễ tối ưu xuống \(O(\log n)\).

Cách 2: Sắp theo sức mạnh

Một cách cây đoạn khác là xử lý các đợt theo sức mạnh giảm dần thay vì theo thời gian. Với mỗi điểm, lưu thời điểm sớm nhất mà nó bị tấn công. Vì đang đi từ đợt mạnh nhất xuống, mọi đoạn tường từng bị một đợt đã xử lý tấn công sớm hơn sẽ chống được những đợt yếu hơn xảy ra muộn hơn.

Để biết đợt hiện tại có thành công không, tìm thời điểm tấn công muộn nhất trên toàn đoạn mà nó phủ; sau đó cập nhật thời điểm tại mỗi điểm thành giá trị nhỏ hơn giữa thời điểm đang lưu và thời điểm của đợt hiện tại.

Đây là cây đoạn min-max: cập nhật bằng phép lấy nhỏ nhất và truy vấn bằng phép lấy lớn nhất. Chọn thông tin phù hợp trong mỗi nút sẽ cho cả hai thao tác trong thời gian logarit.

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