Phân tích: File Fix-it

Đây là một bài toán dễ, đặc biệt khi hiệu năng không phải là vấn đề lớn ở đây.

Với mỗi thư mục bạn muốn tạo, chúng ta xác định tất cả các thư mục mà bạn cần có. Đó là tất cả các thư mục tổ tiên của thư mục đó. Ví dụ, nếu một mục trong danh sách các thư mục muốn tạo là:

/home/gcj/round1b/problema/input

Chúng ta cần tất cả các thư mục sau:

/home
/home/gcj
/home/gcj/round1b
/home/gcj/round1b/problema
/home/gcj/round1b/problema/input

Thuật toán

Gọi A là tập hợp tất cả các thư mục chúng ta cần (bao gồm cả các thư mục đích và tất cả các thư mục cha, ông... của chúng), và B là tập hợp tất cả các thư mục đã tồn tại sẵn. Đơn giản là đếm xem có bao nhiêu phần tử thuộc A nhưng không thuộc B. Bạn cần sử dụng một lệnh mkdir cho mỗi phần tử như vậy.

Cài đặt

1. Sử dụng một cấu trúc dữ liệu tập hợp (như std::set trong C++ hoặc HashSet trong Java/Python) để lưu trữ tất cả các đường dẫn thư mục đã tồn tại.
2. Đối với mỗi đường dẫn mới cần tạo:
   • Tách đường dẫn thành các thành phần (ví dụ: /a/b/c thành /a, /a/b, /a/b/c).
   • Với mỗi thành phần, kiểm tra xem nó đã có trong tập hợp chưa.
   • Nếu chưa có, tăng biến đếm kết quả lên 1 và thêm đường dẫn đó vào tập hợp để các thư mục con sau này không phải đếm lại thư mục cha này nữa.
3. In ra kết quả cuối cùng cho mỗi bộ test.

Độ phức tạp

• Thời gian: Với \(N, M \le 100\) và độ dài đường dẫn tối đa 100, số lượng thư mục con cần kiểm tra là không lớn. Độ phức tạp sẽ phụ thuộc vào thao tác xử lý chuỗi và tìm kiếm trong tập hợp, hoàn toàn nằm trong giới hạn thời gian cho phép.
• Bộ nhớ: \(O((N+M) \times \text{độ dài đường dẫn})\) để lưu trữ các chuỗi trong tập hợp.

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