Test Set 1

Để giải Test Set 1, ta có thể đặt một dấu ngoặc mở trước mỗi nhóm chữ số 1 và một dấu ngoặc đóng sau nhóm đó.

Ta có thể dùng mẹo sau để đơn giản hóa việc cài đặt: thêm một chữ số 0 vào cả đầu lẫn cuối S. Khi đó, việc cài đặt chỉ còn là thay 01 bằng 0(1 và thay 10 bằng 1)0; trong một số ngôn ngữ lập trình, thao tác này có thể được viết chỉ bằng một dòng lệnh. Đừng quên xóa các chữ số 0 được thêm vào khỏi hai đầu chuỗi kết quả!

Test Set 2

Để thuận tiện, ta lại dùng mẹo được mô tả ở trên: thêm các chữ số 0 vào đầu và cuối S, sau đó quét S từ trái sang phải.

Giả sử ta gặp một số \(A\), ngay sau đó là một số \(B\) lớn hơn, và giả sử tất cả các dấu ngoặc đã chèn trước đó khiến \(A\) nằm ở đúng độ sâu lồng nhau — tức là có đúng \(A\) dấu ngoặc mở chưa khớp đứng trước \(A\) và không có dấu ngoặc đóng nào chưa khớp. Để \(B\) nằm ở độ sâu lồng nhau \(B\), ta cần thêm ít nhất \(B-A\) dấu ngoặc mở. Ta chỉ cần thêm đúng chừng đó và không làm gì khác, nhờ vậy độ dài chuỗi cuối cùng vẫn nhỏ nhất. Mọi dấu ngoặc mở bổ sung khác đều phải được đóng lại trước \(B\), khiến chuỗi dài thêm một cách không cần thiết.

Tương tự, nếu ta gặp một số \(A\), ngay sau đó là một số \(B\) nhỏ hơn, ta chỉ cần chèn \(A-B\) dấu ngoặc đóng. Khi \(A=B\), ta không cần chèn gì cả.

Ta không cần bất kỳ dấu ngoặc nào trước chữ số 0 tạm thời ở đầu hoặc sau chữ số 0 tạm thời ở cuối, vì vậy chỉ cần loại bỏ chúng trước khi in kết quả.

Vì ta chỉ thêm \(p\) dấu ngoặc khi bắt buộc phải có ít nhất \(p\) dấu ngoặc, chuỗi kết quả có độ dài nhỏ nhất.

Một lời giải kém hiệu quả nhưng thú vị

Bài toán có thể được giải chỉ bằng các phép thay thế chuỗi. Trước tiên, thay mỗi chữ số \(D\) bằng \(D\) dấu (, tiếp theo là chính chữ số đó, rồi đến \(D\) dấu ). Sau đó, liên tục xóa mọi lần xuất hiện của )(, làm chuỗi co lại sau mỗi lần, cho đến khi không còn )( nào để xóa.

Dưới đây là một cài đặt bằng Python 3:

for C in range(int(input())):
  rawstr = ''.join([int(x) * '(' + x + ')' * int(x) for x in str(input())])
  for _ in range(9):
    rawstr = rawstr.replace(')(', '')
  print("Case #{}: {}".format(C+1, rawstr))

Nguồn

Phần phân tích này được dịch đầy đủ từ lời giải chính thức của Google Code Jam 2020, Vòng loại — Nesting Depth.