Editorial for Bà Nội Đan Len


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Bà Nội Đan Len

Chủ đề: xử lý chuỗi (string), ngăn xếp bằng list chứa tuple

Tóm tắt đề

Khai triển một công thức dạng 2[x3[yz]]w, trong đó n[S] nghĩa là lặp \(S\) đúng \(n\) lần, các cặp ngoặc có thể lồng nhau.

Ý tưởng 1: đệ quy (đúng nhưng nguy hiểm)

Cấu trúc lồng nhau gợi ý ngay tới đệ quy: hàm doc() đọc một công thức cho tới khi gặp ]. Mỗi khi gặp n[ thì gọi đệ quy doc() để đọc phần bên trong, rồi nhân lên \(n\) lần.

Cách này đúng, nhưng công thức dài \(10^4\) ký tự có thể lồng sâu tới hơn \(3000\) tầng (ví dụ 1[1[1[...1[a]...]]]). Giới hạn đệ quy mặc định của Python là \(1000\) tầng nên chương trình bị RecursionError → IR. Muốn dùng đệ quy thì phải thêm sys.setrecursionlimit(...).

Ý tưởng 2: tự quản lý ngăn xếp (an toàn)

Thay vì để Python tự nhớ "đang ở tầng nào" qua các lời gọi hàm, ta tự nhớ bằng một list dùng làm ngăn xếp. Duyệt từng ký tự:

  • Chữ số: ghép vào số đang đọc, so = so * 10 + int(ch). Số có thể có nhiều chữ số như 10 hay 1000000000.
  • Dấu [: sắp vào một tầng mới. Cất tầng hiện tại cùng số lần lặp vào ngăn xếp dưới dạng một tuple (hien_tai, so), rồi bắt đầu tầng mới rỗng.
  • Dấu ]: kết thúc tầng hiện tại. Lấy tầng ngoài ra khỏi ngăn xếp, rồi nối thêm vào nó chuỗi của tầng vừa xong nhân với \(k\).
  • Chữ cái: thêm vào tầng hiện tại.
ngan_xep = []
hien_tai = []
so = 0
for ch in cong_thuc:
    if ch.isdigit():
        so = so * 10 + int(ch)
    elif ch == "[":
        ngan_xep.append((hien_tai, so))
        hien_tai, so = [], 0
    elif ch == "]":
        trong = "".join(hien_tai)
        hien_tai, k = ngan_xep.pop()
        hien_tai.append(trong * k)
    else:
        hien_tai.append(ch)

Hai chi tiết quan trọng về tốc độ:

  1. Dùng phép nhân chuỗi trong * k, không viết vòng for lặp \(k\) lần. Với 1000000000[], phép nhân "" * 10**9 cho kết quả ngay lập tức, còn vòng lặp một tỉ lần thì TLE.
  2. Lưu mỗi tầng là một list các mảnh chuỗi, cuối cùng mới "".join(...). Cộng chuỗi liên tục bằng += vẫn chạy được với dữ liệu bài này, nhưng dùng list + join là thói quen tốt hơn.

Độ phức tạp

Mỗi ký tự của công thức được xử lý một lần. Phần tốn thời gian nhất là sao chép chuỗi khi join và nhân chuỗi, tổng cộng tỉ lệ với (độ sâu lồng nhau) × (độ dài kết quả) trong trường hợp xấu nhất, vẫn chạy nhanh với giới hạn của đề.

Code mẫu

def khai_trien(cong_thuc):
    ngan_xep = []
    hien_tai = []
    so = 0
    for ch in cong_thuc:
        if ch.isdigit():
            so = so * 10 + int(ch)
        elif ch == "[":
            ngan_xep.append((hien_tai, so))
            hien_tai, so = [], 0
        elif ch == "]":
            trong = "".join(hien_tai)
            hien_tai, k = ngan_xep.pop()
            hien_tai.append(trong * k)
        else:
            hien_tai.append(ch)
    return "".join(hien_tai)

print(khai_trien(input().strip()))

Comments

There are no comments at the moment.