Lời giải đầy đủ tại đây. Slides chữa bài của VNOI tại đây.

Tóm tắt đề bài

Cho dãy đèn gồm ~N~ bóng đèn, bóng đèn thứ ~i~ có trạng thái là ~S_i~ (~S_i=0,1,2~ tương ứng với trạng thái tắt, vàng hoặc đỏ). Với mỗi bóng đèn, có hai cách để thay đổi trạng thái bóng đèn như sau:

• Cách 1: Nếu trạng thái hiện tại là ~x~, nó sẽ biến đổi thành trạng thái ~(x+1)\ mod\ 3\ (0\rightarrow 1\rightarrow 2\rightarrow 0)~.
• Cách 2: Nếu trạng thái hiện tại là ~x~, nó sẽ biến đổi thành trạng thái ~(x-1)\ mod\ 3\ (0\rightarrow 2\rightarrow 1\rightarrow 0)~.

Bạn cần giải quyết ~Q~ yêu cầu khảo sát, với yêu cầu khảo sát thứ ~j~:

• Kiểm tra xem có thể thay đổi trạng thái tất cả bóng đèn từ ~L_j~ đến ~R_j~ về trạng thái tắt (~S=0~) hay không. Nếu có hãy in ra số thao tác ít nhất có thể để đưa các bóng đèn về trạng thái tắt, nếu không hãy in ra ~-1~.
• Mỗi thao tác được phép chọn ~X+Y~ bóng đèn phân biệt từ ~L_j~ đến ~R_j~, trong đó chọn ~X~ bóng đèn để thay đổi trạng thái theo cách 1 và ~Y~ bóng đèn còn lại biến đổi theo cách 2.

Lưu ý:

• Các yêu cầu khảo sát là độc lập, nghĩa là mỗi yêu cầu đều được xử lý trên trạng thái ban đầu của dãy đèn.
• ~X~ và ~Y~ là cố định cho tất cả ~Q~ yêu cầu.

Giới hạn và subtask

• ~0<X+Y\le 5~</li>
• ~X+Y\le N\le 666~
• ~1\le Q\le 10^5~
• ~S_i\in \{0,1,2\}~ với mọi ~i~ từ ~1~ đến ~N~
• ~1\le L_j\le R_j\le N~ với mọi ~j~ từ ~1~ đến ~Q~
• ~R_j-L_j+1\ge X+Y~ với mọi ~j~ từ ~1~ đến ~Q~

Subtask 1: ~X=Y=1;N\le 10;Q=1~

Với giới hạn ~N~ rất nhỏ, và mỗi bóng đèn chỉ có ~3~ trạng thái khác nhau nên ta có thể sinh hết mọi state lưu trạng thái của ~N~ bóng đèn có thể xảy ra.

Ta sẽ áp dụng thuật toán BFS để giải quyết subtask này. Coi trạng thái của các bóng đèn trong yêu cầu khảo sát là state xuất phát và cần tìm số bước tối thiểu để đạt được state ~\{0,0,0,\dots\}~.

Vì ~X=Y=1~, với mỗi state ta chỉ cần for trâu để chọn hai bóng đèn sẽ thay đổi trạng thái trong state chuyển cần xét. Có ~N\times (N-1)~ state chuyển khác nhau với mỗi state tương ứng.

Nhận xét độ phức tạp:

• Coi số lượng state là số đỉnh (~n~) và tổng số state chuyển với mỗi state là số cạnh của đồ thị (~m~). Độ phức tạp cho thuật toán BFS sẽ là ~O(n+m)~.
• Có ~3^N~ state khác nhau có thể tồn tại nên ~n=3^N~, và với mỗi state có ~N\times (N-1)~ state chuyển khác nhau nên ~m=3^N\times N\times (N-1)~.

Độ phức tạp: ~O\left(3^N+3^N\times N\times (N-1)\right)=O\left(3^N\times N^2\right)~.

Lưu ý: Nếu ~Q>1~, ta vẫn có thể giải quyết được. Ta sẽ coi trạng thái ~\{0,0,0,\dots\}~ là state xuất phát và BFS tới tất cả các state có thể xảy ra. Tuy nhiên, ta cần phải đảo ngược cách thay đổi trạng thái bóng đèn (Cách 1 ~\rightarrow~ Cách 2 và ngược lại do hai cách thay đổi trạng thái này ngược nhau, hay đơn giản hơn là đổi giá trị của ~X~ và ~Y~ cho nhau).

Subtask 2: ~X=Y=1;Q=1~

Với ~N~ lớn, ta không thể lưu hết mọi state có thể xảy ra, nên ý tưởng subtask 1 sẽ không thể thực hiện được nữa.

Vì giới hạn đặc biệt của subtask này (~X=Y=1~) nên ta có một nhận xét như sau:

• Gọi ~sum=\left(\sum S_i\right)\ mod\ 3~. Khi thay đổi trạng thái của bóng đèn theo cách 1, ~sum'=(sum+1)\ mod\ 3~, và theo cách 2 thì ~sum'=(sum-1)\ mod\ 3~.
• Như vậy sau một thao tác, ~sum'=(sum+1-1)\ mod\ 3=sum\ mod\ 3~. Hay nói cách khác, giá trị ~sum~ trong quá trình thực hiện thao tác luôn không đổi.
• Nếu ~sum\ne 0~ thì ta có thể suy ra ngay đáp án là ~-1~.

Trong trường hợp ngược lại, ta biết là luôn tồn tại phương án để đưa các bóng đèn về trạng thái tắt. Gọi ~a,b,c~ là số lượng bóng đèn có trạng thái ~0,1,2~.

Ta có: ~sum=(b+2c)\ mod\ 3=0 \leftrightarrow b\ mod\ 3=c\ mod\ 3~.

Tới đây thì ta có chiến thuật tham lam như sau:

• Các bóng đèn tắt ta hoàn toàn có thể bỏ qua.
• Trong trường hợp còn tồn tại ít nhất một bóng đèn ở trạng thái ~1~ và ~2~, ta sẽ thực hiện thao tác trên cả hai bóng đèn đó để đưa cả hai về trạng thái tắt. Cách làm này mất ~1~ thao tác.
• Trong trường hợp các bóng đèn bật đều ở trạng thái ~1~ hoặc ~2~, ta chọn ra ~3~ bóng đèn bật và thực hiện ~2~ thao tác để tắt tất cả chúng:

$$(1\ 1\ 1)\rightarrow (0\ 2\ 1)\rightarrow (0\ 0\ 0)$$

$$(2\ 2\ 2)\rightarrow (0\ 1\ 2)\rightarrow (0\ 0\ 0)$$

Như vậy đáp án sẽ bằng ~min(b,c)+\frac{2\times (b+c-2min(b,c))}3~.

Độ phức tạp: ~O(1)~.

Subtask 3: ~Q\le 5~

Ta cải tiến ý tưởng từ subtask 1. Rõ ràng ta không cần phải quan tâm trạng thái của tất cả bóng đèn mà chỉ cần quan tâm xem có bao nhiêu bóng đèn đang ở trạng thái ~0,1,2~. Vì thế nên ta có ý tưởng BFS mới như sau:

Ta sẽ lưu tất cả bộ ba số ~(a,b,c)\ (a+b+c=len=R_j-L_j+1)~, mỗi bộ số tương ứng với một state (ta có thể chỉ cần lưu hai trong ba số vì ta dễ dàng xác định được số còn lại).

Coi state ~(a_j,b_j,c_j)~ là state xuất phát (~a_j,b_j,c_j~ là số lượng bóng đèn ban đầu ở trạng thái ~0,1,2~), ta cần tìm số bước tối thiểu để đưa về state ~(len,0,0)~.

Để xác định các state chuyển, ta chỉ cần quan tâm số lượng bóng đèn ở trạng thái ~0,1,2~ sẽ thay đổi theo cách 1, 2. Trên thực tế, khi đã xác định được số bóng đèn ở trạng thái ~0,1~ sẽ thay đổi theo cách 1, 2 thì số lượng bóng đèn ở trạng thái ~2~ cũng sẽ được xác định. Như vậy ta cần ~4~ vòng lặp lồng nhau để xét tất cả các state chuyển.

Nhận xét độ phức tạp (tương tự như subtask 1):

• Số state khác nhau (cũng là số đỉnh) tối đa: ~n=C^2_{len+2}\le C^2_{N+2}~
• Số state chuyển tối đa với mỗi state: ~C^2_{X+2}\times C^2_{Y+2}~
• Số cạnh tối đa của đồ thị: ~m\le n\times C^2_{X+2}\times C^2_{Y+2}\le C^2_{N+2}\times C^2_{X+2}\times C^2_{Y+2}~

Độ phức tạp: ~O\left(Q\times N^2\times P\right)~, với ~P~ là số state chuyển tối đa (~P_{max}=60~ trong trường hợp ~X=2,Y=3~ hoặc ~X=3,Y=2~).

Subtask 4: Không có ràng buộc gì thêm

Tương tự subtask 1, ta có thể thực hiện BFS ngược thay vì làm như đã nói ở trên. Như vậy ta có thể xử lý mọi yêu cầu khảo sát có ~len=R_j-L_j+1~ giống nhau, tương đương với việc ta chỉ cần thực hiện BFS tối đa ~N~ lần tương ứng với các giá trị ~len~ từ ~1~ đến ~N~.

Độ phức tạp: ~O\left(N^3\times P\right)~.

Tuy nhiên, ta vẫn không thể đảm bảo thuật toán này đủ để chúng ta AC. Vì thế nên ta cần có một số cải tiến.

Lưu ý: Đây là cách làm của mình và có thể còn một số cách làm khác nữa.

Gọi ~f_{b,c}\ (b+c\le len)~ là số thao tác tối thiểu để từ state ~(len,0,0)~ đến được state ~(len-b-c,b,c)~. Khi tăng ~len~ lên ~1~ đơn vị, trên thực tế ta không cần phải reset mảng ~f~ để thực hiện BFS lại từ đầu mà chỉ cần BFS lại từ một số vị trí.

Tại sao cách này lại hoạt động? Vì cơ bản khi tăng ~len~ lên, ta dễ dàng nhận thấy:

• Mỗi đỉnh ta chỉ quan tâm hai giá trị tương ứng là ~b,c~ nên số đỉnh của đồ thị sẽ tăng lên.
• Đồng thời, với mỗi đỉnh, số cạnh nối cũng sẽ tăng lên. Một state có thể chuyển sang state khác phụ thuộc vào việc có đủ số bóng đèn với trạng thái tương ứng hay không để thực hiện thao tác, khi tăng ~len~ lên, chỉ có ~a=len-b-c~ tăng, còn ~b~ và ~c~ thì không bị ảnh hưởng nên điều này đúng.

Như vậy cấu trúc đồ thị mới khi tăng ~len~ sẽ chỉ thêm đỉnh và cạnh, điều này làm giảm độ dài đường đi ngắn nhất giữa các cặp đỉnh với nhau, nên việc BFS lại không làm ảnh hưởng gì hết.

Vậy ta sẽ BFS lại trên các đỉnh nào? Ta chỉ BFS trên các đỉnh có thêm cạnh sau khi tăng ~len~ lên. Với các đỉnh không có thêm cạnh nào thì việc BFS lại là vô nghĩa vì nếu có thể BFS sang đỉnh khác thì nó đã được thực hiện ở lượt trước rồi.

Dễ dàng nhận thấy với các đỉnh có ~1\le a\le X+Y~ là các đỉnh thỏa mãn vì số bóng đèn tối đa cần đổi trạng thái chỉ là ~X+Y~. Như vậy sẽ có xấp xỉ ~len\times (X+Y)~ đỉnh cần BFS lại với mỗi lần xét giá trị ~len~ mới.

Trên thực tế, tổng số lần thăm BFS tối đa chỉ xấp xỉ ~2\times 10^6~ (đã thử trên máy) nên độ phức tạp đã giảm đi đáng kể.

Độ phức tạp: ~O(S\times P)~, với ~S~ là số lần duyệt BFS.