Tóm tắt đề bài

Cho \(n\) từ, với mỗi từ \(s\):

• Nếu độ dài \(|s| \le 10\): Giữ nguyên từ đó.
• Nếu độ dài \(|s| > 10\): Rút gọn thành định dạng: ký tự đầu + số lượng ký tự ở giữa + ký tự cuối.

Phân tích

• Điều kiện: \(n \le 100\), độ dài xâu \(|s| \le 100\).
• Số lượng ký tự ở giữa: Nếu xâu có độ dài \(L\), sau khi bỏ đi ký tự đầu và ký tự cuối, số lượng ký tự còn lại ở giữa sẽ là \(L - 2\).
• Ví dụ: Xâu competitive có độ dài \(L = 11\).
  • Ký tự đầu: c
  • Ký tự cuối: e
  • Số ký tự ở giữa: \(11 - 2 = 9\)
  • Kết quả: c9e

Cách làm đơn giản (Brute Force)

Vì bài toán này yêu cầu xử lý trực tiếp từng xâu theo quy tắc cố định và các ràng buộc về \(n\) cũng như độ dài xâu rất nhỏ, cách làm duyệt qua từng xâu và kiểm tra điều kiện độ dài chính là cách làm tối ưu nhất. Không có cách làm "ngây thơ" hơn cho bài toán này.

Hướng giải quyết (Tối ưu)

1. Đọc số lượng xâu \(n\).
2. Sử dụng một vòng lặp chạy \(n\) lần, mỗi lần đọc vào một xâu \(s\).
3. Lấy độ dài \(L\) của xâu \(s\).
4. Kiểm tra điều kiện:
   • Nếu \(L \le 10\): In ra xâu \(s\).
   • Nếu \(L > 10\): In ra ký tự đầu \(s[0]\), giá trị \(L-2\), và ký tự cuối \(s[L-1]\).

Lưu ý khi lập trình:

• Trong C++, sau khi dùng cin >> n, một ký tự xuống dòng \n vẫn còn sót lại trong bộ đệm. Nếu sử dụng getline để đọc xâu, cần dùng cin.ignore() để loại bỏ ký tự thừa này. Nếu dùng cin >> s, chương trình sẽ tự động bỏ qua các khoảng trắng và ký tự xuống dòng.

Độ phức tạp

• Thời gian: \(O(n \times L)\) với \(L\) là độ dài trung bình của các xâu. Với \(n, L \le 100\), tổng số thao tác chỉ khoảng \(10^4\), hoàn toàn đáp ứng thời gian yêu cầu.
• Bộ nhớ: \(O(L)\) để lưu trữ xâu đang xử lý.

Tóm tắt đề bài

Cho \(n\) thời điểm bắt đầu \(a_1, a_2, \dots, a_n\) đã được sắp xếp tăng dần. Với một số nguyên dương \(k\), mỗi thời điểm \(a_i\) tạo ra một đoạn thời gian \([a_i, a_i + k - 1]\). Tổng số thời điểm được phủ là số lượng các số nguyên thuộc ít nhất một trong các đoạn này. Hãy tìm giá trị \(k\) nhỏ nhất sao cho tổng số thời điểm được phủ ít nhất là \(h\).

Phân tích

• Điều kiện: \(n \le 2 \cdot 10^5\), \(h \le 10^{18}\), \(a_i \le 10^9\).
• Nhận xét quan trọng:
  • Nếu ta tăng \(k\), tổng số thời điểm được phủ chắc chắn sẽ không giảm. Đây là tính chất đơn điệu, cho phép chúng ta sử dụng Tìm kiếm nhị phân để tìm \(k\).
  • Với một giá trị \(k\) cố định, làm sao để tính tổng số thời điểm được phủ?
    • Xét hai thời điểm liên tiếp \(a_i\) và \(a_{i+1}\).
    • Đoạn bắt đầu từ \(a_i\) là \([a_i, a_i + k - 1]\).
    • Nếu \(a_i + k - 1 < a_{i+1}\), đoạn này không chạm tới \(a_{i+1}\), số điểm phủ được là \(k\).
    • Nếu \(a_i + k - 1 \ge a_{i+1}\), đoạn này bị chồng lấn bởi đoạn bắt đầu từ \(a_{i+1}\). Số điểm phủ được thực tế chỉ là \(a_{i+1} - a_i\).
    • Riêng đoạn cuối cùng bắt đầu từ \(a_n\) luôn phủ được đúng \(k\) điểm (vì không có \(a_{n+1}\) phía sau).
  • Vậy tổng số điểm phủ được với giá trị \(k\) là:
    
    \[ f(k) = \sum_{i=1}^{n-1} \min(k, a_{i+1} - a_i) + k \]

Cách làm đơn giản (Brute Force)

Ý tưởng

Thử từng giá trị \(k\) bắt đầu từ \(1, 2, 3, \dots\) cho đến khi tổng số điểm phủ được đạt ít nhất \(h\).

Độ phức tạp

• Thời gian: \(O(h \cdot n)\) trong trường hợp xấu nhất.
• Đánh giá: Với \(h\) lên tới \(10^{18}\), cách này chắc chắn sẽ bị quá thời gian (TLE). Cách này chỉ phù hợp với Subtask 2 khi \(h\) nhỏ.

Hướng giải quyết (Tối ưu)

Thuật toán

Sử dụng tìm kiếm nhị phân trên giá trị của \(k\):

1. Khoảng tìm kiếm: \(low = 1\), \(high = h\) (vì trong trường hợp xấu nhất \(n=1\), ta cần \(k=h\)).
2. Với mỗi giá trị \(mid = (low + high) / 2\):
   • Tính tổng số điểm phủ được \(f(mid)\) theo công thức đã phân tích ở trên.
   • Nếu \(f(mid) \ge h\): \(mid\) có thể là kết quả, ta lưu lại và thử tìm giá trị nhỏ hơn bằng cách đặt \(high = mid - 1\).
   • Nếu \(f(mid) < h\): \(mid\) quá nhỏ, ta cần tăng \(k\) bằng cách đặt \(low = mid + 1\).

Ví dụ minh họa

Với \(n=3, h=10\) và \(a = [1, 4, 10]\):

• Nếu \(k=3\): \(f(3) = \min(3, 4-1) + \min(3, 10-4) + 3 = 3 + 3 + 3 = 9 < 10\) (Không đủ).
• Nếu \(k=4\): \(f(4) = \min(4, 4-1) + \min(4, 10-4) + 4 = 3 + 4 + 4 = 11 \ge 10\) (Thỏa mãn).
• Vậy \(k\) nhỏ nhất là \(4\).

Độ phức tạp

• Thời gian: \(O(T \cdot n \log h)\). Với \(T \cdot n \approx 2 \cdot 10^5\) và \(\log h \approx 60\), tổng số phép tính khoảng \(1.2 \cdot 10^7\), hoàn toàn khả thi trong giới hạn 1-2 giây.
• Bộ nhớ: \(O(n)\) để lưu mảng \(a\).

Tóm tắt đề bài

Cho \(n\) xâu ký tự \(s_1, s_2, \dots, s_n\). Một xâu được gọi là "đối xứng được" nếu có thể sắp xếp lại các ký tự của nó để tạo thành một xâu palindrome. Hãy đếm số cặp \((i, j)\) với \(1 \le i < j \le n\) sao cho xâu \(s_i + s_j\) là một xâu đối xứng được.

Phân tích

• Điều kiện để một xâu là đối xứng được: Một xâu có thể sắp xếp thành palindrome khi và chỉ khi có tối đa một loại ký tự xuất hiện lẻ lần trong xâu đó.
  • Nếu tất cả các ký tự đều xuất hiện chẵn lần: Có thể tạo palindrome độ dài chẵn (ví dụ: aabb \(\rightarrow\) abba).
  • Nếu có đúng một ký tự xuất hiện lẻ lần: Có thể tạo palindrome độ dài lẻ với ký tự đó ở giữa (ví dụ: aacbb \(\rightarrow\) abcba).
  • Nếu có từ hai ký tự trở lên xuất hiện lẻ lần: Không thể tạo palindrome.
• Tính chất nối xâu: Khi nối hai xâu \(s_i\) và \(s_j\), số lần xuất hiện của một ký tự \(c\) trong xâu mới là tổng số lần xuất hiện của \(c\) trong \(s_i\) và \(s_j\).
  • Một ký tự xuất hiện lẻ lần trong \(s_i + s_j\) khi và chỉ khi tính chẵn lẻ của số lần xuất hiện của nó ở \(s_i\) và \(s_j\) là khác nhau.

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua mọi cặp \((i, j)\), nối hai xâu lại và đếm tần suất các ký tự từ a đến z. Nếu có không quá 1 ký tự có tần suất lẻ thì tăng biến đếm.

Độ phức tạp

• Thời gian: \(O(n^2 \times L)\) với \(L\) là độ dài trung bình của xâu.
• Đánh giá: Với \(n = 10^5\), cách này sẽ bị quá thời gian (TLE). Chỉ phù hợp cho Subtask 1 và 2 (\(n \le 5000\)).

Hướng giải quyết (Tối ưu)

Nhận xét (Bitmask)

Vì ta chỉ quan tâm đến tính chẵn lẻ của 26 ký tự, ta có thể biểu diễn mỗi xâu \(s_i\) bằng một số nguyên (mask) 26 bit.

• Bit thứ \(k\) (từ 0 đến 25) của mask sẽ là 1 nếu ký tự thứ \(k\) trong bảng chữ cái xuất hiện lẻ lần trong \(s_i\), và là 0 nếu xuất hiện chẵn lần.
• Khi nối hai xâu \(s_i\) và \(s_j\), mask của xâu mới \(S = s_i + s_j\) sẽ là: mask(S) = mask(s_i) XOR mask(s_j).
• Điều kiện để \(S\) đối xứng được là mask(S) có không quá một bit 1. Điều này xảy ra khi:
  1. mask(s_i) XOR mask(s_j) == 0 (tức là mask(s_i) == mask(s_j)).
  2. mask(s_i) XOR mask(s_j) == 2^k với \(k \in [0, 25]\) (tức là hai mask chỉ khác nhau đúng 1 bit).

Thuật toán

1. Với mỗi xâu \(s_i\), tính mask_i.
2. Sử dụng một bảng băm (hoặc mảng nếu đủ bộ nhớ) để lưu số lần xuất hiện của các mask đã gặp trước đó.
3. Với mỗi mask_i:
   • Cộng vào kết quả số lượng mask_i đã xuất hiện trước đó (trường hợp XOR bằng 0).
   • Duyệt qua 26 vị trí bit \(k\), cộng vào kết quả số lượng mask dạng mask_i XOR (1 << k) đã xuất hiện trước đó (trường hợp XOR có 1 bit 1).
   • Tăng số lần xuất hiện của mask_i trong bảng băm.

Độ phức tạp

• Thời gian: \(O(L + n \times 26)\), trong đó \(L\) là tổng độ dài các xâu.
• Bộ nhớ: \(O(n)\) để lưu trữ bảng băm các mask.

Tóm tắt đề bài

Cho dãy số nguyên \(a\) gồm \(n\) phần tử. Với mỗi vị trí \(i\):

• \(L_i\): Số lần giá trị \(a_i\) xuất hiện trong đoạn \([1, i]\).
• \(R_i\): Số lần giá trị \(a_i\) xuất hiện trong đoạn \([i, n]\).

Yêu cầu: Đếm số cặp \((i, j)\) sao cho \(1 \le i < j \le n\) và \(L_i > R_j\).

Phân tích

• Điều kiện: \(n \le 10^6\), \(a_i \le 10^9\).
• Nhận xét 1: Giá trị tối đa của \(L_i\) và \(R_j\) là \(n\).
• Nhận xét 2: Ta có thể tính trước mảng \(L\) bằng cách duyệt từ đầu đến cuối và dùng một cấu trúc dữ liệu (như std::map hoặc mảng nếu đã nén số) để đếm số lần xuất hiện của từng giá trị. Tương tự, mảng \(R\) có thể tính bằng cách duyệt ngược từ cuối về đầu.
• Nhận xét 3: Bài toán yêu cầu đếm cặp \((i, j)\) với \(i < j\) và \(L_i > R_j\). Đây là một dạng bài toán đếm nghịch thế (inversions) biến thể, nơi ta so sánh hai mảng khác nhau tại các vị trí khác nhau.

Cách làm đơn giản (Brute Force)

Ý tưởng

1. Tính mảng \(L\) và \(R\) bằng hai vòng lặp.
2. Duyệt mọi cặp \((i, j)\) với \(1 \le i < j \le n\).
3. Nếu \(L_i > R_j\) thì tăng biến đếm.

Độ phức tạp

• Thời gian: \(O(n^2)\)
• Đánh giá: Phù hợp cho \(n \le 5000\) (Subtask 1 và 2).

Hướng giải quyết (Tối ưu)

Nhận xét

Bài toán yêu cầu đếm \(i < j\) sao cho \(L_i > R_j\). Khi ta duyệt \(j\) từ \(n\) về \(1\):

• Với mỗi \(j\), ta cần đếm xem có bao nhiêu \(i < j\) mà \(L_i > R_j\).
• Tuy nhiên, cách tiếp cận thuận tiện hơn là duyệt \(j\) từ \(n\) về \(1\) và duy trì các giá trị \(R_k\) đã đi qua vào một cấu trúc dữ liệu. Nhưng để thuận theo chiều \(i < j\), ta nên duyệt từ cuối về đầu và đếm các giá trị \(R_j\) nhỏ hơn \(L_i\).

Thuật toán

1. Tiền xử lý: Tính mảng \(L\) bằng cách duyệt từ \(1 \to n\).
2. Sử dụng Binary Indexed Tree (BIT):
   • Duyệt \(i\) từ \(n\) về \(1\).
   • Tại mỗi bước \(i\):
     • Những giá trị \(R_j\) với \(j > i\) đã được thêm vào BIT.
     • Ta cần đếm số lượng giá trị \(R_j\) đã có trong BIT mà nhỏ hơn \(L_i\). Kết quả này chính là bit.get(L[i] - 1).
     • Sau đó, tính \(R_i\) và cập nhật \(R_i\) vào BIT để phục vụ cho các bước \(i\) phía trước.
3. Lưu ý: Vì \(a_i\) lên tới \(10^9\), ta dùng std::map để đếm tần suất khi tính \(L_i\) và \(R_i\). Các giá trị trong BIT chỉ nằm trong khoảng \([1, n]\).

Độ phức tạp

• Thời gian: \(O(n \log n)\) do thao tác trên BIT và map.
• Bộ nhớ: \(O(n)\) để lưu mảng và BIT.