Phân tích

Xem clip hướng dẫn giải

Với mỗi câu hỏi của Bob, ta cần tìm cách xác định xem có thể sắp xếp lại các kí tự trong một chuỗi để tạo thành một chuỗi đối xứng hay không. Và tập kí tự thuộc chuỗi con ~[L_i, R_i]~ của chuỗi được cho trong test case.

Một cách tiếp cận là duyệt qua tất cả các hoán vị của chuỗi con và xác định xem có chuỗi đối xứng nào trong số đó không. Với một chuỗi con độ dài ~l~, ta có thể phải kiểm tra đến ~Factorial~~(l)~ hoán vị, mỗi hoán vị mất ~O(l)~ để kiếm tra. Đôi khi, các lời giải "brute force" như vậy là đủ để giải các bài toán, nhưng trong bài này, kể cả với ~N_{max}~ là ~20~ trong subtask đầu cũng sẽ cần tới ~20 \times Factorial(20) \approx 4.9 \times 10^{19}~ phép xử lí, và chương trình sẽ không thể xử lí trong giới hạn thời gian được.

Một quan sát quan trọng chính là một chuỗi đối xứng có thể được mô tả như là một chuỗi bất kì với độ dài từ ~0~ trở lên, theo sau là chuỗi đảo ngược của nó, và có một kí tự ở giữa hoặc không. Ví dụ, ABCCBA (không có kí tự ở giữa) và ABCXCBA (có một kí tự ở giữa) đều là những chuỗi đối xứng. Những ví dụ trên thể hiện một tính chất quan trọng của chuỗi đối xứng, đó là tất cả các kí tự (trừ kí tự ở giữa), đều xuất hiện chẵn lần trong chuỗi.

Tính chất này đúng với mọi chuỗi đối xứng, và điều này dẫn đến nhận xét là bất kì bộ kí tự nào có tính chất này đều có thể sắp xếp để tạo thành một chuỗi đối xứng. Ta có thể tạo chuỗi bằng cách chọn các cặp kí tự và dùng chúng để dựng nên hai chuỗi giống nhau. Sau đó, ta còn lại dư tối đa một kí tự. Cuối cùng, ta đảo lại một trong hai chuỗi và ghép chúng lại với nhau, nếu có kí tự dư thì ta đặt kí tự đó vào giữa. Và ta sẽ nhận được một chuỗi đối xứng.

Subtask 1

Với mỗi câu hỏi, ta có thể đếm số lần xuất hiện của các kí tự trong chuỗi con và xác định xem có thể sắp xếp chúng để tạo thành chuỗi đối xứng hay không. Ta có thể đếm số lần xuất hiện trong ~O(N)~. Có ~Q~ câu hỏi trong mỗi test case, nên cách làm này có độ phức tạp là ~O(Q \times N)~ và có thể AC được subtask này.

Subtask 2

Subtask này có giới hạn lớn hơn cho ~Q~ và ~N~, và cách tiếp cận ở Subtask 1 sẽ chạy rất chậm, và sẽ vượt quá giới hạn thời gian. Một quan sát quan trọng đó là với mỗi test case được cho, những câu hỏi của Bob không độc lập với nhau, chúng đều là những câu hỏi về chuỗi con của cùng một chuỗi. Liệu ta có thể tận dụng điều này để chia sẻ hoặc dùng lại những phép tính giữa các câu hỏi hay không?

Nghĩ một chút về thuật toán được dùng ở Subtask 1, ta có thể thấy rằng quá trình đếm số lần xuất hiện của các kí tự trong các chuỗi con đã bị lặp lại nhiều lần qua những câu hỏi khác nhau. Ví dụ, nếu một câu hỏi hỏi về đoạn ~[20, 70]~ và một câu khác hỏi về đoạn ~[30, 80]~, và ta phải lặp lại quá trình đếm cho đoạn ~[30, 70]~. Tuy nhiên, ta có thể thực hiện quá trình đếm để chuẩn bị cho tất cả các câu hỏi có thể xuất hiện bằng cách dựng một mảng prefix sum (tổng tiền tố) cho số lần xuất hiện của từng kí tự.

Tạo một tổng tiền tố cho số lần xuất hiện của các kí tự của một chuỗi độ dài ~N~ mất độ phức tạp ~O(N)~. Hơn nữa, sau khi mảng perfix sum được dựng xong, việc trả lời bất kì câu hỏi nào của Bob đều có thể thực hiện trong ~O(1)~. Với bất kì câu hỏi ~[L_i, R_i]~, số lần xuất hiện của các kí tự trong chuỗi con sẽ chính là hiệu giữa hai giá trị của prefix sum ở hai vị trí đầu và kết thúc của chuỗi con. Và điều này dẫn đến tổng độ phức tạp thuật toán giảm đi từ ~O(Q \times N)~ xuống còn ~O(Q+N)~, đủ để AC Subtask 2.

Cũng nên đề cập rằng giới hạn bộ nhớ 1GB là rất dư so với cách tiếp cận này; bởi vì ta thực sự không cần đếm số lần xuất hiện của các kí tự, mà ta chỉ cần đếm xem chúng xuất hiện chẵn lần hay lẻ lần. Ta có thể tính một mảng gọi là "prefĩ parity" (tính chẵn/lẻ tiền tố) và so sánh tính chẵn/lẻ ở hai vị trí đầu và cuối chuỗi con. Nếu chuỗi con đó có tối đa một kí tự có giá trị chẵn/lẻ khác nhau ở hai đầu, thì chuỗi con có thể được sắp xếp để trở thành một chuỗi đối xứng.

Code tham khảo

Solve(N, Q, letters, questions) {
 answer = 0
 prefix[1]['A':'Z'] = 0
 for i in 1:N {
   prefix[i+1] = prefix[i]
   prefix[i+1][letters[i]]++
 }
 for i in 1:Q {
   [L,R] = questions[i]
   frequencies = prefix[R+1] - prefix[L]
   odds = 0
   for c in 'A':'Z' {
     if IsOdd(frequencies[c]) {
       odds++
     }
   }
   if odds <= 1 {
     answer++
   } 
 }
 return answer
}

Tải bộ test

Bạn hãy cố gắng tập sửa lỗi mà không nhìn vào dữ liệu test! Link tải.