Phân tích: Lost Password

Đây chắc chắn là một bài đáng ngại. Ngay cả những chuỗi nhỏ, như ví dụ từ The Fellowship of the Ring, cũng khó xử lý thủ công. Khi cố ghép các mật khẩu dài tới \(500\) vào một chuỗi mật khẩu, số khả năng lớn đến mức việc tối ưu nhanh chóng trở nên choáng ngợp.

Tập dữ liệu nhỏ

Hãy bắt đầu với tập nhỏ, nơi ta cần nối các cặp ký tự. Ý tưởng then chốt là hình dung mọi thứ như một đồ thị. Nếu từng biết dãy De Bruijn, đó là mô hình hoàn hảo. Tạo một đỉnh cho mỗi ký tự — \(26\) chữ thường và mọi biến thể l33t — rồi thêm các cạnh giữa các ký tự. Mỗi từ hai ký tự cần có trong chuỗi mật khẩu tương ứng với một cạnh; chẳng hạn t0 là cạnh 't' -> '0'. Gọi chúng là cạnh ứng viên.

Một chuỗi mật khẩu là một đường đi trên đồ thị: bắt đầu ở ký tự đầu rồi liên tục sang ký tự kế tiếp. Ví dụ, abc0 là đường 'a' -> 'b' -> 'c' -> '0'. Vì vậy, bài toán trở thành: đường đi ngắn nhất chứa mọi cạnh ứng viên dài bao nhiêu?

Lúc này nên nhớ tới bài toán cổ điển về đường đi Euler. Tương đương, bắt đầu chỉ với các cạnh ứng viên, cần thêm ít nhất bao nhiêu cạnh để đồ thị có đường đi Euler? May thay, bài toán Euler đã được giải hoàn toàn.

Sự thật. Một đồ thị có hướng có đường đi Euler khi và chỉ khi: (1) mọi đỉnh có bán bậc vào bằng bán bậc ra, ngoại trừ nhiều nhất hai đỉnh lệch nhau một; và (2) mọi đỉnh có bậc dương liên thông trong đồ thị vô hướng nền.

Thử vài ví dụ sẽ cho thấy đồ thị ở đây luôn liên thông; ta sẽ quay lại chứng minh hình thức trong phần tập lớn. Chính việc tính liên thông “được miễn phí” làm bài toán giải được, nên đây là điểm đáng suy nghĩ.

Điều kiện còn lại chỉ yêu cầu cân bằng bậc. Ta có thể thêm bất kỳ cạnh nào: chọn đỉnh \(u\) có bán bậc vào lớn hơn bán bậc ra và đỉnh \(v\) có bán bậc ra lớn hơn bán bậc vào, rồi thêm cạnh \(u\to v\). Lặp cho tới khi chỉ còn hai đỉnh lệch nhẹ. Sau tất cả những phân tích trên, ta thu được một thuật toán tham lam rất đơn giản.

Tập dữ liệu lớn

Lời giải trên đã chứa phần lớn ý tưởng cho tập lớn, nhưng cần đẩy chúng xa hơn. Có ba thách thức:

1. Với mật khẩu dài hơn \(2\), diễn giải chúng thành cạnh như thế nào?
2. Khi cân bằng bậc, một số cạnh không thể thêm; phải sửa thuật toán tham lam ra sao?
3. Chuỗi mật khẩu đầu ra có thể khổng lồ. Có thể giải trong thời gian nhỏ hơn chính độ dài đầu ra không?

Thách thức đầu là quan trọng nhất; dãy De Bruijn lại cho mô hình phù hợp. Khi xây dựng các mật khẩu độ dài \(k\), tạo một đỉnh cho mỗi cụm dài \(k-1\). Mỗi mật khẩu ứng viên là cạnh từ cụm tiền tố tới cụm hậu tố. Sau đây là cách phát biểu chặt chẽ.

Diễn giải bằng luồng chi phí nhỏ nhất

Gọi mọi chuỗi con độ dài \(k\) của \(S\), cùng mọi biến thể l33tspeak của nó, là một ứng viên. Gọi mọi chuỗi dài \(k-1\) gồm chữ thường và chữ số là một cụm, bất kể có nằm trong ứng viên hay không. Với cụm \(s\), đặt \(w(s)\) bằng số ứng viên kết thúc bằng \(s\) trừ số ứng viên bắt đầu bằng \(s\). Tổng mọi \(w(s)\) bằng \(0\). Trọng số này đo độ lệch của đỉnh tương ứng khỏi điều kiện Euler.

Lập đồ thị có hướng \(G\) với các cụm làm đỉnh. Với hai cụm \(a,b\), thêm cạnh \(a\to b\) nếu có thể biến \(a\) thành \(b\) bằng cách thêm một ký tự vào cuối \(a\) và bỏ ký tự đầu. Thiết lập bài toán luồng: cụm \(s\) có trọng số dương là nguồn dung lượng \(|w(s)|\); cụm có trọng số âm là đích dung lượng \(|w(s)|\). Mọi cạnh có dung lượng vô hạn và chi phí một.

Gọi ANSWER là độ dài nhỏ nhất của chuỗi mật khẩu cho \(S\); \(C\) là tập mọi ứng viên; FLOW_EDGES là số cạnh ít nhất, tức chi phí nhỏ nhất, của một luồng gần cực đại: luồng được phép để thừa tối đa một đơn vị dung lượng ở một nguồn và tối đa một đơn vị ở một đích.

Bổ đề 1.

Phần chứng minh 1: \(\text{ANSWER}\le\text{FLOW_EDGES}+|C|+k-1\)

Tạo đa đồ thị có hướng \(G'\) như sau:

1. Bắt đầu bằng đa đồ thị do luồng gần cực đại chi phí nhỏ nhất trên \(G\) tạo ra.
2. Với mỗi ứng viên \(c\), thêm cạnh từ cụm tiền tố của \(c\) tới cụm hậu tố của \(c\).

Với cụm \(s\), xét bán bậc ra trừ bán bậc vào trong \(G'\). Sau bước đầu, giá trị đúng bằng \(w(s)\) ngoại trừ hai đỉnh lệch một, vì luồng chỉ gần cực đại. Sau bước hai, giá trị trở thành \(0\), vẫn ngoại trừ hai đỉnh lệch một. Do đó, \(G'\) thỏa điều kiện bậc của đường đi Euler.

Ta còn phải chứng minh liên thông. Đây là lúc dùng cấu trúc đặc thù của bài và điều kiện \(|S|\ge2k\). Chúng tôi nghi điều kiện cuối không thật sự cần, nhưng nếu bỏ nó thì chứng minh khó hơn nhiều.

Gọi đỉnh \(s\) là đỉnh lõi nếu nó tương ứng với một cụm trong \(S\), hoặc một biến thể l33t của cụm như vậy. Nếu \(s\) là đỉnh lõi, trong \(G'\) nó kề với các cụm đứng trước và sau nó trong \(S\). Có thể có nhiều tiền nhiệm hoặc kế nhiệm nếu ký tự mới có biến thể l33t hoặc \(S\) xuất hiện nhiều lần.

Vì vậy, ta có thể đi theo các cạnh của \(G'\) từ \(s\) tới một cụm \(a(s)\) bắt đầu tại ký tự đầu của \(S\), rồi từ đó tới một cụm \(b(s)\) kết thúc tại ký tự cuối của \(S\). Do \(a(s)\) và \(b(s)\) hoàn toàn không chồng nhau, ta có thể chọn \(b(s)\) hoàn toàn không dùng l33t bằng cách luôn thêm ký tự kế nhiệm không-l33t. Khi đó \(b(s)\) không phụ thuộc \(s\). Như vậy, mọi đỉnh lõi đều nối tới cùng một đỉnh trong \(G'\).

Xét một đỉnh không-lõi \(t\) có bậc dương trong \(G'\). Điều này chỉ có thể xảy ra nếu \(t\) có bậc dương trong \(G\), nên qua luồng nó phải nối với một đỉnh lõi \(s\). Mọi đỉnh lõi đã liên thông, vì vậy các đỉnh không-lõi cũng liên thông.

Suy ra đồ thị vô hướng nền của \(G'\) liên thông. Do đó \(G'\) có đường đi Euler gồm các đỉnh
\(s_1,s_2,\ldots,s_{\text{FLOW_EDGES}+|C|+1}\).
Ta dựng chuỗi mật khẩu:

1. Bắt đầu bằng \(k-1\) ký tự của \(s_1\).
2. Với mỗi đỉnh kế tiếp \(s_i\), nối thêm ký tự cuối của \(s_i\) không thuộc \(s_{i-1}\).

Chuỗi có đúng \(k-1+\text{FLOW_EDGES}+|C|\) ký tự. Sau khi nối ký tự của \(s_i\), \(k-1\) ký tự cuối luôn đúng bằng \(s_i\); bất biến này được chứng minh dễ dàng bằng quy nạp. Với ứng viên bất kỳ \(c\), do cách dựng \(G'\), tồn tại \(i\) sao cho tiền tố của \(c\) là \(s_{i-1}\) và hậu tố là \(s_i\). Sau khi nối ký tự cho \(s_i\), \(k\) ký tự cuối đúng bằng \(c\). Mọi ứng viên đều xuất hiện, nên bất đẳng thức được chứng minh.

Phần chứng minh 2: \(\text{ANSWER}\ge\text{FLOW_EDGES}+|C|+k-1\)

Ta đảo ngược lập luận trên; phần này dễ hơn vì không phải lo liên thông. Xét chuỗi mật khẩu \(P\) dài ANSWER. Theo định nghĩa, mọi ứng viên xuất hiện trong \(P\). Với ứng viên \(c\), gọi \(pos(c)\) là vị trí ký tự bắt đầu lần xuất hiện đầu tiên của \(c\). Sắp các ứng viên \(c_1,c_2,\ldots,c_{|C|}\) theo \(pos(c)\).

Với mỗi \(i\), xét chuỗi con của \(P\) bắt đầu tại \(pos(c_i)+1\) và kết thúc tại \(pos(c_{i+1})+k-2\). Nó bắt đầu bằng cụm hậu tố của \(c_i\) và kết thúc bằng cụm tiền tố của \(c_{i+1}\). Đảo ngược phép dựng ở phần trước, chuỗi con này là một đường trong \(G\) từ hậu tố của \(c_i\) tới tiền tố của \(c_{i+1}\), chứa \(pos(c_{i+1})-pos(c_i)-1\) cạnh.

Gộp mọi đường ấy tạo một luồng có nguồn tại mọi cụm hậu tố ngoại trừ hậu tố của \(c_{|C|}\), và đích tại mọi cụm tiền tố ngoại trừ tiền tố của \(c_1\). Cộng các nguồn và đích lại cho đúng một luồng gần cực đại trên \(G\). Luồng dùng chính xác

cạnh. Vì vậy,

Cuối cùng, \(pos(c_{|C|})\le |P|-k=\text{ANSWER}-k\) và \(pos(c_1)\ge0\). Suy ra
\(\text{ANSWER}\ge\text{FLOW_EDGES}+k+|C|-1\), như cần chứng minh.

Lời giải tham lam

Ta chưa giải xong bài, nhưng đã đưa nó về dạng dễ xử lý hơn. Luồng chi phí nhỏ nhất phức tạp song đã được biết rõ và giải được trong thời gian đa thức. Có thể tối ưu ở đây, hoặc dùng một ý tưởng khéo hơn để đơn giản hóa đáng kể.

Bổ đề 2. Cố định \(G\) và gán dung lượng nguồn/đích tùy ý cho các nút. Có thể thu được luồng gần cực đại chi phí nhỏ nhất bằng cách liên tục chọn đường ngắn nhất từ một nguồn chưa dùng tới một đích chưa dùng, đẩy luồng theo đường đó, và không bao giờ hoàn lại luồng đã đẩy.

Chứng minh. Gọi \(F\) là một luồng gần cực đại chi phí nhỏ nhất, và giả sử đường nguồn-đích ngắn nhất trong \(G\) đi từ nguồn \(u\) tới đích \(x\). Giả sử \(F\) chứa đường từ \(u\) tới đích khác \(y\) và đường từ nguồn khác \(v\) tới \(x\). Ta khẳng định có thể thay hai đường này bằng một đường \(u\to x\) và một đường \(v\to y\) mà không tăng tổng số cạnh. Vì \(F\) chỉ gần cực đại, có thể \(u\) hoặc \(x\) không được dùng trong \(F\); trường hợp đó còn đơn giản hơn. Mọi cạnh của \(G\) có dung lượng vô hạn, nên chỉ cần kiểm tra độ dài.

Với hai cụm \(p,q\), đặt \(A(p,q)\) là chuỗi dài nhất vừa là hậu tố của \(p\), vừa là tiền tố của \(q\). Khoảng cách từ \(p\) tới \(q\) trong \(G\) đúng bằng \(k-1-|A(p,q)|\). Vì đường \(u\to x\) ngắn nhất, ta có
\(|A(u,x)|\ge\max(|A(u,y)|,|A(v,x)|)\).
Ta cần chứng minh

\(A(u,x)\) và \(A(u,y)\) cùng là hậu tố của \(u\), nhưng \(A(u,x)\) không ngắn hơn, nên \(A(u,y)\) là hậu tố của \(A(u,x)\). Tương tự, \(A(v,x)\) là tiền tố của \(A(u,x)\). Đặt
\(t=|A(u,y)|+|A(v,x)|-|A(u,x)|\).
Nếu \(t\le0\), khẳng định hiển nhiên. Nếu \(t>0\), phải tồn tại chuỗi \(z\) dài \(t\) vừa là hậu tố của \(A(v,x)\) vừa là tiền tố của \(A(u,y)\). Khi đó \(z\) cũng là hậu tố của \(v\) và tiền tố của \(y\), nên \(|A(v,y)|\ge|z|=t\). Khẳng định được chứng minh.

Như vậy có thể sửa \(F\) để chứa đường \(u\to x\) mà không tăng số cạnh. Phần còn lại của \(F\) là một luồng nhỏ hơn; áp dụng lại cùng lập luận để buộc nó chứa đường ngắn nhất giữa một nguồn và đích còn lại mà vẫn không tăng số cạnh. Lặp lại cho ta đúng luồng tham lam trong bổ đề, nên luồng ấy tối ưu.

Cài đặt

Gần xong! Ta đã có thuật toán tham lam, nhưng nó có nghĩa gì trong bài gốc và cài nhanh thế nào?

Trước tiên dựng các cụm tiền tố và hậu tố của mọi ứng viên. Cần tạo luồng gần cực đại từ các hậu tố tới các tiền tố. Nếu một cụm vừa là hậu tố vừa là tiền tố, hai lần xuất hiện triệt tiêu nhau.

Đầu tiên tìm nguồn \(u\) và đích \(x\) cách nhau một cạnh trong đồ thị nền; tương đương tồn tại chuỗi dài \(k-2\) vừa là hậu tố của \(u\) vừa là tiền tố của \(x\). Tiếp theo tìm cặp cách nhau hai cạnh, tương đương chuỗi chung dài \(k-3\), rồi tiếp tục như vậy.

Tóm tắt thuật toán ban đầu:

1. \(P\) là đa tập cụm tiền tố của mọi ứng viên; \(S\) là đa tập cụm hậu tố.
2. Đặt \(x=k+|C|\), \(i=0\).
3. Trong khi \(|P|\ge2\) và \(|P\cap S|\ge1\): xóa một bản sao của phần tử chung khỏi cả \(P,S\), rồi tăng \(x\) thêm \(i\).
4. Bỏ ký tự cuối khỏi mọi phần tử \(P\), bỏ ký tự đầu khỏi mọi phần tử \(S\).
5. Tăng \(i\) thêm một và lặp từ bước 3 cho tới khi \(P,S\) chỉ còn một phần tử.
6. In \(x\).

Đáng tiếc, cách này vẫn quá chậm: thời gian tỉ lệ với độ dài chuỗi mật khẩu đầu ra, có thể tới \(10^{18}\). Tối ưu cuối cùng dựa trên việc: với bất kỳ phần tử của \(P\) hoặc \(S\), mọi biến thể l33tspeak của nó cũng nằm trong cùng đa tập. Vì vậy, luôn có thể xử lý toàn bộ biến thể thành một lô:

1. \(P\) là ánh xạ từ cụm sang số lần một biến thể l33t của cụm xuất hiện làm tiền tố ứng viên; định nghĩa \(S\) tương tự cho hậu tố.
2. Đặt \(x=k+|C|\), \(i=0\).
3. Khi \(P,S\) chưa rỗng, trong lúc có phần tử chung \(t\), xóa \(m=\min(P[t],S[t])\) bản khỏi cả hai và tăng \(x\) thêm \(i\cdot m\).
4. Bỏ ký tự cuối khỏi mọi khóa của \(P\), bỏ ký tự đầu khỏi mọi khóa của \(S\).
5. Tăng \(i\) và lặp từ bước 3 đến khi \(P,S\) rỗng.
6. In \(x-i+1\).

Cách cài của misof

Chỉ một thí sinh giải được bài này trong cuộc thi, và anh dùng một biến thể của phương pháp trên. Thay vì thuật toán tham lam, anh cài trực tiếp bài toán luồng, đồng thời nhóm các biến thể l33t như ta đã làm để đạt thời gian dưới tuyến tính theo độ dài chuỗi mật khẩu. Cách ấy chậm hơn và khó cài hơn một chút, nhưng hoạt động hoàn toàn tốt. Xin chúc mừng misof vì đã tìm ra nó!

Dựa trên phân tích chính thức của Google Code Jam.