Codeforces Round #1091 (Div. 2) write-up

Sau gần 14 năm, tôi quay lại tham gia một coding contest trên Codeforces – lần đầu tiên trở lại competitive programming một cách nghiêm túc kể từ thời sinh viên. Trong quãng thời gian dài đó, trọng tâm công việc của tôi chuyển sang phát triển và vận hành hệ thống, khiến việc luyện thuật toán và thi contest dần trở nên xa lạ.

Lần tham gia này chủ yếu nhằm đánh giá lại tư duy thuật toán của bản thân sau nhiều năm. Trong bài viết này, tôi sẽ chia sẻ ngắn gọn trải nghiệm quay lại contest sau thời gian dài, đồng thời viết write‑up cho các bài toán đã giải được để hệ thống lại cách tiếp cận và rút kinh nghiệm cho các lần tham gia sau.

Thực ra, mấy hôm trước tôi đã tham gia một cuộc thi khác, cũng trên Codeforces. Lần đó coi như khởi động, thành tích của tôi cũng không cao.

Quay lại coding contest – gặp lại chính mình của ngày xưa

Gần đây, tôi quyết định tham gia lại một coding contest sau gần 14 năm vắng bóng. Cuộc thi diễn ra trên Codeforces – một cái tên rất quen thuộc với tôi từ những ngày còn là sinh viên. Ngày đó, tôi biết đến Codeforces là nhờ một anh khóa trên giới thiệu. Rồi cả nhóm chúng tôi cùng tham gia, cùng thi, cùng hồi hộp đợi kết quả sau mỗi contest. Không khí khi ấy rất sôi nổi: sau mỗi cuộc thi là những buổi trao đổi lời giải, bàn luận cách làm, đôi khi còn tranh luận xem ai tối ưu hơn. Đó là một khoảng thời gian rất đẹp, rất “thuần” về đam mê lập trình.

14 năm trước, tôi là sinh viên, có nhiều thời gian và nhiều năng lượng. Tôi tham gia contest với sự nhiệt tình gần như bản năng. Nhưng rồi cuộc sống thay đổi. Ra trường, đi làm, trách nhiệm ngày càng nhiều. Thời gian dành cho coding contest dần biến mất lúc nào không hay. Dù thỉnh thoảng trong công ty vẫn có những cuộc thi nội bộ nhỏ, nhưng cảm giác rất khác – nhanh, nhẹ, và không để lại nhiều dấu ấn. Tôi vẫn code, vẫn giải quyết bài toán mỗi ngày, nhưng tinh thần “contest” thì dần ngủ yên.

Lần quay lại này mang đến cho tôi rất nhiều cảm xúc. Vừa vui, vừa háo hức, lại vừa có chút bồi hồi như gặp lại một người bạn cũ. Kết quả lần này, tôi giải được 5 bài, và thật lòng mà nói, đó là thành tích tốt nhất từ trước đến nay của tôi trong một contest kiểu này. Tôi khá hài lòng với bản thân. Dù vậy, khi nhìn lên bảng xếp hạng và thấy nhiều người giải được đủ 8 bài trong thời gian rất ngắn, tôi không khỏi chạnh lòng. Sự chênh lệch về trình độ là quá rõ ràng. Nhưng thay vì nản, tôi lại thấy mình được nhắc nhở rằng: thế giới này rộng lớn hơn rất nhiều, và mình vẫn còn rất nhiều thứ để học. Tôi sẽ cố gắng, dù có thể chậm hơn người khác.

Một khoảnh khắc rất đặc biệt trong lần quay lại này là khi tôi nhận được tin nhắn từ một chàng trai trẻ. Bạn ấy nói rằng đã xem hồ sơ của tôi và nhận ra tôi từng tham gia contest từ năm 2012. Khi đó, bạn ấy mới học lớp 2. Còn bây giờ, chúng tôi lại cùng đứng trong một cuộc thi. Bạn nói rằng điều đó khiến bạn ấy cảm thấy “mind‑blowing”. Còn với tôi, tin nhắn ấy khiến tôi lặng người đi một chút. Tôi bất chợt nhớ lại chính mình của ngày xưa – cũng trẻ, cũng đầy nhiệt huyết, cũng không hề biết 14 năm sau cuộc sống sẽ đưa mình đến đâu.

Có lẽ điều đẹp nhất của coding contest nói riêng và lập trình nói chung là khả năng kết nối những con người rất khác nhau về tuổi tác, trải nghiệm và hoàn cảnh, nhưng lại giống nhau ở một điểm: yêu thích việc giải quyết vấn đề. 14 năm là một quãng đường dài, đủ để mọi thứ đổi thay. Nhưng cảm giác ngồi trước màn hình, đọc đề, suy nghĩ, thử sai, rồi vui mừng khi tìm ra lời giải – cảm giác đó vẫn còn nguyên.

Lần quay lại này không phải để chứng minh điều gì, mà giống như một cuộc hội ngộ. Hội ngộ với Codeforces, với ký ức sinh viên, và với chính bản thân mình của nhiều năm trước. Và tôi nhận ra rằng, dù có bận rộn hay trưởng thành đến đâu, phiên bản trẻ trung và đam mê ấy vẫn luôn ở đâu đó, chỉ chờ một dịp để quay trở lại.

Write up

Code trong phần này đều được refactor sau khi cuộc thi kết thúc, khi tôi có nhiều thời gian để suy nghĩ lại về logic và sửa lại code. Trong lúc cuộc thi đang diễn ra, đương nhiên code sẽ xấu hơn rất nhiều.

Ngoài ra, độ phức tạp của thuật toán trong phần này cũng được tính cho từng test case. Mỗi lần chương trình chạy, độ phức tạp cần nhân thêm số test case (t).

Bài A. The Equalizer

Đề bài

Hai người chơi lượt xen kẽ trên mảng a gồm n số nguyên. Mỗi lượt chọn a_i > 0 và giảm 1. Người đi nước cuối thắng. Shaunak đi trước và có thể dùng tối đa một lần nước đặc biệt: đặt tất cả a_i = k.

Phân tích

Trò chơi “lấy 1”: mỗi nước giảm tổng S đi 1, nên trò chơi kéo dài đúng S nước.

• Nếu không dùng nước đặc biệt: Shaunak thắng nếu S lẻ.
• Nếu dùng nước đặc biệt: Trò chơi coi như chơi lại từ đầu, các nước đi trước đó không còn quan trọng nữa. Lúc này, tổng số nước có thể đi là n * k và Shaunak là người đi sau. Shaunak thắng nếu n * k chẵn.

Code

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    s = sum(map(int, input().split()))
    if s & 1 or 1 - (n * k) & 1:
        print("YES")
    else:
        print("NO")

Độ phức tạp: O(n)

Bài C. Grid Covering

Đây là bài C nhưng tôi chọn làm trước, vì bài B liên quan đến bài D.

Đề bài

Prakul có phòng dạng lưới n x m (wrap-around – tức đi ra biên thì quay lại đầu). Xuất phát từ ô (1, 1), mỗi bước có thể:

• Nhảy b bước sang phải, hoặc
• Nhảy a bước xuống dưới.

Đề bài cho công thức rất phức tạp, nhưng thực ra suy nghĩ lại thì nó đơn giản như trên.

Bắt buộc phải xen kẽ hai loại bước (bắt đầu bằng loại nào cũng được). Hỏi: có thể đi qua tất cả các ô hay không?

Phân tích

Sau khi phân tích đề bài và có được công thức đơn giản hơn thì bài toán có vẻ dễ hơn khá nhiều. Chuyển sang hệ tọa độ 0. Xét đường đi bắt đầu bằng bước sang phải (R):

Nếu đi sang phải, có thể đi qua tất cả các vị trí (ka, kb) và (ka, (k+1)b). Nếu đi xuống dưới, có thể đi qua tất cả các vị trí (ka, kb) và ((k+1)a, kb).

Vì vậy, ta suy ra được 2 điều kiện sau:

1. gcd(a, n) = 1 – Nếu không, chỉ đi được các hàng là bội của gcd(a,n), bỏ sót hàng.
2. gcd(b, m) = 1 – Tương tự cho cột.

Khi hai điều kiện trên đã thỏa mãn, giả sử sau khi xuất phát từ ô đầu tiên, đi theo hướng (RD), sau k bước anh ta có thể quay lại chính ô đó nếu: ka ⋮ n và kb ⋮ m.

Vậy, giá trị nhỏ nhất của k là lcm(m, n). Tức là sau lcm(m, n) bước, sẽ quay lại ô ban đầu, lúc này chuyển hướng khác (DR) cũng sẽ quay trở lại sau lcm(m, n) bước. Tổng số ô có thể thăm là 2 * lcm(m, n).

Bài toán yêu cầu mỗi ô phải được thăm ít nhất một lần, có nghĩa là số ô được thăm ≥ nm

2 * lcm(m, n) ≥ nm = gcd(m, n) * lcm(m, n)

Như vậy điều kiện ở đây là gcd(n,m) ≤ 2. Thực ra, lúc này cần kiểm tra lại xem từng trường hợp gcd(m, n) bằng 1 hoặc 2 có thể thực hiện di chuyển toàn bộ các ô hay không. Nhưng thời gian có hạn, sau khi tìm được điều kiện này tôi summit code luôn và nó ra kết quả đúng.

Code

from math import gcd

t = int(input())
for _ in range(t):
    n, m, a, b = map(int, input().split())
    if gcd(a, n) == 1 and gcd(b, m) == 1 and gcd(n, m) <= 2:
        print("YES")
    else:
        print("NO")

Độ phức tạp: O(log(max(n, m))) (3 phép GCD).

Bài B. Flip the Bit (Easy Version)

Đề bài

Cho mảng nhị phân a độ dài n và một chỉ số đặc biệt p. Mỗi thao tác: chọn đoạn [l, r] chứa p và lật tất cả bit trong đoạn. Tìm số thao tác tối thiểu để mọi phần tử bằng x = a[p].

Phân tích

Đặt b[i] = a[i] ^ x. Cần biến tất cả b[i] thành 0. Mỗi thao tác luôn lật b[p], nên cần số chẵn thao tác để b[p] quay về giá trị ban đầu.

Để ý rằng, mỗi lần lật bit sẽ thay đổi giá trị các số bằng nhau liền nhau của hai đầu [l, r]. Vì vậy để tính số lần cần lật, chỉ cần tính số vị trí mà b[i] != b[i + 1] (số vị trí thay đổi 0↔1), cộng thêm 1 lần lật nếu vị trí đầu tiên/cuối cùng là 1.

Ngoài ra, khoảng [l, r] yêu cầu phải có chứa p. Ta chia hai phía quanh p:

• Trái (b[0..p-1])
• Phải (b[p+1..n-1])

Mỗi phía có thể tính được số lần cần lật để toàn bộ phía đó về 0. Vì có thể ghép thao tác trái và phải vào cùng một lần flip:

Đáp án = max(fl, fr) (làm tròn lên số chẵn)

Sau khi làm được bài D, tôi nghĩ lại, không cần làm tròn lên số chẵn. Vì với cách tính toán số bước cần thiết, kết quả sẽ luôn chẵn.

Code

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    p = int(input())
    x = a[p - 1]
    b = [ai ^ x for ai in a]

    fl = b[0]
    for i in range(p):
        if b[i] != b[i + 1]:
            fl += 1

    fr = b[n - 1]
    for i in range(p - 1, n - 1):
        if b[i] != b[i + 1]:
            fr += 1

    ans = max(fl, fr)
    print(ans + ans % 2)

Độ phức tạp: O(n)

Bài D. Flip the Bit (Hard Version)

Đề bài

Giống bài Easy nhưng có nhiều chỉ số đặc biệt p_1, p_2, ..., p_k. Thao tác [l, r] phải chứa ít nhất một chỉ số đặc biệt.

Phân tích

Dựa vào ý tưởng ở bài B, để tính số bước cần lật, xây dựng một mảng d như sau:

d[0] = b[0]
d[i] = b[i] ^ b[i + 1] (với mọi i trong khoảng [0, n - 1])
d[n] = b[n - 1]

Mảng này có chứa số bước lật cần thiết để biến toàn bộ b thành 0. Cũng từ ý tưởng bài B, với bài này, có k vị trí đặc biệt, nên chia chia mảng d[0..n] thành k + 1 đoạn:

• S_0 = {d[0], ..., d[p_1]}
• S_i = {d[p_i + 1], ..., d[p_{i+1}]}
• S_k = {d[p_k + 1], ..., d[n]}

Tính chất: Mỗi đoạn có số chẵn các vị trí = 1 (chứng minh qua XOR dọc theo các chỉ số đặc biệt mà b[p_i] = 0), cũng là số thao tác flip cần thiết để biến toàn bộ đoạn đó thành 0.

Bây giờ, việc quan trọng là phải ghép cặp để số thao tác là ít nhất. Mỗi thao tác ghép hai vị trí d từ ít nhất hai đoạn khác nhau (vì đoạn [l, r] phải chứa ít nhất một chỉ số đặc biệt nằm giữa d[l] và d[r + 1]).

Gọi c_i = số vị trí = 1 trong đoạn S_i. Có thể dễ dàng tính c_i bằng cách tính tổng.

• Mỗi thao tác loại bỏ tối đa 2 vị trí = 1 → cần ít nhất C/2 thao tác cho toàn bộ mảng d.
• Nếu một đoạn có c_i vị trí = 1, mỗi vị trí phải ghép với đoạn khác → cần ít nhất c_i thao tác.

Đáp án = max(C/2, max c_i)

Code

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    p = list(map(int, input().split()))

    x = a[p[0] - 1]
    b = [ai ^ x for ai in a]

    d = [0] * (n + 1)
    d[0] = b[0]
    for i in range(n - 1):
        d[i] = b[i] ^ b[i + 1]
    d[n] = b[n - 1]

    segs = [sum(d[:p[0]])] + [sum(d[p[j] : p[j + 1]]) for j in range(k - 1)] + [sum(d[p[k - 1]:])]
    print(max(sum(segs) // 2, max(segs)))

Độ phức tạp: O(n)

Bài E. Definitely Larger

Đề bài

Cho hoán vị p độ dài n và mảng d. Chỉ số j thống trị (dominate) chỉ số i khi và chỉ khi:

• j > i (vị trí j ở bên phải i)
• p[j] > p[i] (giá trị p tại j lớn hơn)
• q[j] > q[i] (giá trị q tại j lớn hơn)

d[i] = số lượng chỉ số j thống trị i. Đề bài cho hoán vị p độ dài n và mảng d. Xây dựng hoán vị q sao cho mỗi chỉ số i có đúng d[i] kẻ thống trị.

Ý tưởng chính

Nếu ta gán các giá trị q từ lớn đến nhỏ (n, n-1, …, 1), thì:

• Số lớn nhất n sẽ được gán cho vị trí d[i] = 0. Khi đó, vị trí này sẽ thống trị tất cả các vị trí bên trái nó trong mảng q. Nếu có nhiều d[i] = 0 thì chọn vị trí đầu tiên. Thực ra, tôi cũng không chắc chắn cách làm này là đúng. Đã có lúc tôi nghĩ phải thử hết các giá trị nhưng như vậy quá phức tạp.
• Tiếp tục với các giá trị nhỏ hơn. Mỗi khi gán q[i] = v sẽ là giá trị lớn nhất hiện tại, riêng trong mảng q, nó sẽ tiếp tục thống trị các vị trí bên trái chưa được gán. Các vị trí đã gán trước đó có giá trị lớn hơn v nên sẽ không bị thống trị bởi v.

Để xác định vị trí cần gán giá trị v, cần xây dựng mảng count để tính giá trị thống trị “hiện tại”, nghĩa là giá trị thống trị dựa vào mảng q chưa đầy đủ. Như đã nó ở trên, mỗi giá trị q được gán sẽ luôn thống trị các vị trí chưa được gán bên trái của nó, nên việc một chỉ số có bị thống trị hay không phụ thuộc vào mảng p:

count[i] = |j đã gán : j > i và p[j] > p[i]|

Mảng count sẽ được cập nhật liên tục mỗi khi mảng q được gán giá trị mới. Nghe thì phức tạp, nhưng việc cập nhật này khá đơn giản, chỉ cần kiểm tra vị trí gán mới nhất và cộng thêm 1 cho các vị trí bị nó thống trị.

Khi count[i] == d[i], chỉ số i đã có đủ số thống trị cần thiết, tức là chỉ số i đã “sẵn sàng” để được gán. Lúc này, nếu ta gán giá trị cho i, giá trị đó sẽ nhỏ hơn tất cả các giá trị đã gán (vì ta gán từ lớn đến nhỏ), nên không ảnh hưởng đến sự thống trị của các giá trị đó. Nếu có nhiều chỉ số “sẵn sàng”, ta chọn chỉ số đầu tiên.

Thuật toán

1. Khởi tạo count[i] = 0 cho mọi i.
2. Duyệt giá trị v từ n xuống 1:
    a. Tìm chỉ số i đầu tiên chưa gán mà count[i] == d[i].
    b. Nếu không tìm thấy → in -1 (không có lời giải).
    c. Gán q[i] = v.
    d. Cập nhật count: với mọi i' < i chưa gán mà p[i'] < p[i]:
       count[i'] += 1
       (i vừa được gán, i' nằm bên trái i, p[i'] < p[i])

Code

t = int(input())
for _ in range(t):
    n = int(input())
    p = list(map(int, input().split()))
    d = list(map(int, input().split()))

    q = [0] * n
    count = [0] * n

    try:
        for v in range(n, 0, -1):
            idx = next(i for i in range(n) if not q[i] and count[i] == d[i])
            q[idx] = v
            for i in range(idx):
                if not q[i] and p[i] < p[idx]:
                    count[i] += 1
        print(*q)
    except StopIteration:
        print(-1)

Độ phức tạp: O(n²), Với n ≤ 5000 và tổng n ≤ 5000, đây là hoàn toàn chấp nhận được.

Tổng kết

Bài học rút ra:

• Bài A: thường là bài dễ, chỉ cần đọc hiểu đề bài và suy nghĩ một chút là giải được.
• Bài B & C: Nhiều bài toán tưởng phức tạp nhưng phân tích cẩn thận, suy nghĩ kỹ thì cũng không quá khó.
• Bài D: Lần này khá may mắn vì nó liên quan đến bài B. Bài D thường phức tạp hơn nhiều nhưng có thể suy nghĩ biến bài toán thành các bài toán đơn giản hơn. Như lần này là dùng mảng và phép tính XOR biến thao tác lật đoạn thành thao tác lật hai điểm, đơn giản hóa bài toán rất nhiều.
• Bài E: Đây là level khó, các cuộc thi trước tôi chưa bao giờ làm được bài này (kể cả sau khi cuộc thi kết thúc). Lần này nhờ động lực của chàng thanh niên mà tôi minh mẫn lạ thường. Vì khó nên phải suy nghĩ nhiều, thử các phương án khác nhau. Tôi thấy mình cần học hỏi, luyện tập nhiều hơn để nắm bắt được nhiều kỹ thuật tiếp cận khác nhau. Trong cuộc thi, cần giải những bài trước thật nhanh để có thời gian suy nghĩ bài toán này.
• Các bài F trở lên: đây là những bài khó, tôi sẽ cố gắng luyện tập để ít nhất là có thời gian đọc đề trong lúc cuộc thi đang diễn ra.