Rất cảm ơn các bạn đã tham gia contest, dưới đây là solution của các bài tập.

Bài A div 2

$|C - A| = |B - C| => A = B $ hoặc \(C = (A + B) / 2\)

Vậy nếu \(A = B\) hoặc \((A + B)\) là số chẵn thì sẽ tồn tại \(C\) thõa mãn điều kiện.

Bài B div 2

X chính là độ dài của xâu Y. Trường hợp đặc biệt duy nhất là Y = 0. Khi đó, đáp án là 0.

Bài C div 2

Bài này cách của mình chỉ là duyệt các giá trị của \(x\) từ \(1\) đến \(10000\) và tính \(y\). Nếu tồn tại \(y\) là số nguyên dương thì \((x, y)\) chính là \(1\) nghiệm của phương trình. Ngoài ra vẫn còn \(1\) cách sử dụng "Giải thuật Eculid mở rộng" nhưng mình sẽ không đề cập ở đây mà để các bạn tìm hiểu.

Bài A div 1

Bài này rất đơn giản. Đặt mn là giá trị phần tử nhỏ nhất trong A. Ta xét 2 trường hợp

• Nếu k ≥ mn in ra 0.
• Nếu k ≤ mn, ta sẽ trừ mn đi k và tính giá trị của biểu thức như thường.

Bài B div 1

Bài này có thể quy về như sau: hãy đổi chỗ 2 phần tử i và j để dãy đạt được có thứ tự từ điển lớn nhất. Có thể giải như sau, tìm vị trí i gần nhất mà A_i ≠ n - i + 1. Và đổi chỗ A_i với A_j mà A_j = n - i + 1.

Bonus: Hãy giải bài này với n = 100000 và biểu thức là mũ cơ số 2.

Bài C div 1

Bài này cực kì đơn giản. Hãy định nghĩa dp[i] là kết quả bài toán nếu chúng ta chỉ xét i số đầu.

Dễ dàng làm được thuật O(n^2) bằng công thức truy hồi sau:

dp[i] = dp[i-1] + ... + dp[i-x] với các số a[i], a[i-1] , ... a[i-x] đều bằng nhau và i - x + 1 ≤ k.

Để đạt được thuật O(n), chúng ta chỉ đơn giản dùng một mảng tổng prefix sum để tính nhanh phần chuyển đổi trạng thái.

Bài D div 1

Chúng ta cần đổi màu một ô để 2 ô trong một query liên thông. Đầu tiên, ta sẽ tìm hết tất cả thành phần liên thông.

Quan sát răng, với mỗi ô, ta chỉ có tối đa 4 cách đổi có ích. Vậy, hãy thử đổi hết 4 cách này và xem xét những thành phần nào đã liên thông với nhau. Có thể lưu những thành phần này trong một map/set và dúng cấu trúc dữ liệu đó để trả lời câu hỏi.

Sẽ có một vài trường hợp đặc biệt, và mình tin các bạn sẽ làm được.

Bài E div 1

Hãy lấy nút 1 làm gốc.

Ý tưởng chính là với mỗi cạnh, hãy xem cạnh này đóng góp vào tổng bao nhiêu lần.

Ta có thể dùng quy hoạch động để giải bài toán này. Gọi dp[u] là số lần cạnh u - (cha của u) đóng góp vào kết quả bài toán. Giả sử, ta đang ở nút u, và đã có kết quả ở các nút con của nó. Hơn nữa, ta cũng có set[u] là tập các nút là con của u. Dùng set này, ta hoàn toàn tính được kết quả thay đổi nếu thêm 1 màu vào set.

Hãy gán kết quả của dp[u] với kết quả của một nút con dp[v] bất kỳ, và gán set[u] = set[v]. Việc còn lại chỉ là mang tất cả các nút con của set[child] mà child != v bỏ vào set[u]. Mỗi lần như thế, ta lại tính được dp[u]. Nhưng độ phức tạp là O(n^2) ?

Để giải quyết, ta sẽ dùng tối ưu small-to-larger merging trick để nhận được độ phức tạp O(nlog(n)log(n)).

Trên đây chỉ là lời giải sơ lược về các bài tập. Nếu các bạn có thắc mắc gì, hãy để lại comment.

UPDATE: Trong quá trình contest, đã có một vài lỗi trong bài Thảo Tác Lớn Nhất. Đề nên là (n+1)^(n-i+1). Ngoài vấn đề đó, hi vọng các bạn đã ít nhiều thưởng thức contest lần này. Một vấn đề nữa, ở bài Trị Tuyệt Đối nhỏ nhất, có một số submission có lẽ đã được 100, tuy nhiên, không hiểu vì lí do gì mà các bạn chỉ được 90. Mình sẽ tiến hành rejudge toàn bộ bài này. Các bạn yên tâm rằng sau khi rejudge, điểm các bạn sẽ không giảm.