Một cách làm bài này là ta ưu tiên trường hợp cột dọc trước và xử lý hàng ngang sau và làm dãy quay về trạng thái tắt.

Gọi ~s1~ là dãy bóng đèn thứ nhất, ~s2~ là dãy bóng đèn thứ hai.

• Trường hợp dọc: Khi ~\left\{ \begin{array}{rcl} s1_i=s1_{i+2} \\s1_i \neq s1_{i+1}\\s2_i=s2_{i+2}\\s2_i \neq s2_{i+1} \end{array}\right. ~ thì ta cộng ~1~ vào kết quả và tiến hành bật/tắt lại cột ~i+1~.

  Để bật/tắt cột ~i+1~ ta có thể dùng cách sau s1[i+1]='0'+'1'-s1[i+1], tương tự với s2.

  Ví dụ như các trường hợp:

  101 010	101 101	010 101	010 010

  Thì sẽ được biến đổi như sau:

  111 000	111 111	000 111	000 000

• Sau khi xét trường hợp dọc ta xét trường hợp hàng ngang. Ta có khả năng bật/tắt cả dãy liên tiếp nên

  Nếu ~\left\{ \begin{array}{rcl} s1_i=0 \\ s1_{i+1}=1\\ \end{array}\right.~ Thì kết quả sẽ cộng ~1~

  Tương tự với ~s2~ nếu ~\left\{ \begin{array}{rcl} s2_i=0 \\ s2_{i+1}=1\\ \end{array}\right.~ Thì kết quả sẽ cộng ~1~

  Có các điều kiện như trên vì đó là dấu hiệu bắt đầu của một dãy ngang đang bật nên ta cộng 1 lần thực hiện và đổi nó về tắt. Tuy nhiên đề chỉ kêu số lần bật/tắt nên không cần thiết phải cập nhật lại dãy.

Độ phức tạp: ~ \mathcal{O}(n).~

Code tham khảo của lds

void lds_go_goooo()
{
    int ans=0;
    s1[0]=s2[0]=s1[n+1]=s2[n+1]='0';
    FOR(i,0,n-1)
    {
        if(s1[i]==s1[i+2]&&s1[i]!=s1[i+1]&&s2[i]==s2[i+2]&&s2[i]!=s2[i+1])
        {
            s1[i+1]='0'+'1'-s1[i+1];
            s2[i+1]='0'+'1'-s2[i+1];
            ans++;
        }
        if(s1[i]=='0'&&s1[i+1]=='1')    ans++;
        if(s2[i]=='0'&&s2[i+1]=='1')    ans++;
    }
    cout<<ans;
}