Level 1 Fewest encrypt commands
A storage team must bring a file tree into a required encryption state. The tree is given with these classes (they are in the starter; keep them in your solution):
@dataclass
class FileNode:
name: str
is_encrypted: bool # the REQUIRED final state of this file
@dataclass
class DirectoryNode:
name: str
directories: list["DirectoryNode"] = field(default_factory=list) # child directories
files: list[FileNode] = field(default_factory=list) # files directly inside
Right now every file is unencrypted. The only tool is encrypt(target), where target is either a single file or a directory; encrypting a directory encrypts every file anywhere below it. There is no way to decrypt, so you must never encrypt a file whose is_encrypted is False.
Write min_encrypt_operations(root: DirectoryNode) -> int: the smallest number of encrypt calls that leaves exactly the files marked is_encrypted=True encrypted.
- A directory can be encrypted in one call only if every file below it must be encrypted. A directory with no files anywhere below it gains nothing from a call.
- The root itself may be a target.
F = FileNode
D = DirectoryNode
root = D("/", [
D("photos", [D("2023", [], [F("a.jpg", True), F("b.jpg", True)])], [F("c.jpg", True)]),
D("docs", [], [F("cv.pdf", True), F("notes.txt", False), F("tax.pdf", True)]),
D("empty"),
], [F("readme", False)])
min_encrypt_operations(root) # 3: encrypt photos, cv.pdf and tax.pdf
Constraints: up to 10^5 directories and files in total, and directories can be nested up to 5,000 levels deep (too deep for plain recursion in Python). Recomputing "is everything below this directory encrypted?" separately for every directory is the classic slow approach.
Show hint
one post-order pass. For each directory compute two things from its children: whether it has any file below it with every such file needing encryption ("fully encrypted"), and the best cost for its subtree. A fully encrypted directory costs 1; otherwise it costs the sum over its child directories plus its own files that need encryption. Use an explicit stack for the post-order.