Minimum Encryption Cost in a File Tree
MediumTrees ยท Databricks
Given files, the paths of every file in a storage tree (such as "logs/app/a.txt", where all segments but the last are directories), and targets, the files that must end up encrypted, return the minimum total cost.
Encrypting one file costs file_cost. Encrypting a directory encrypts every file under it, nested ones included, whether or not they are targets, and costs dir_cost + bulk_rate * f, where f is the number of files under it. The root directory, which holds everything, can be encrypted this way too. Return 0 if nothing needs encrypting.
Example 1
- Input:
- files = ["app/a.log", "app/b.log", "app/c.log", "tmp/d.bin", "tmp/e.bin", "tmp/f.bin", "tmp/g.bin"], targets = ["app/a.log", "app/b.log", "app/c.log", "tmp/d.bin"], file_cost = 5, dir_cost = 6, bulk_rate = 2
- Output:
- 17
- Explanation
- Encrypt
appas a directory for 6 + 2 * 3 = 12, andtmp/d.binalone for 5.
Example 2
- Input:
- files = ["docs/a.md", "docs/b.md", "docs/old/c.md", "docs/old/d.md", "docs/old/e.md", "img/p.png"], targets = ["docs/a.md", "docs/b.md", "img/p.png"], file_cost = 4, dir_cost = 5, bulk_rate = 1
- Output:
- 11
- Explanation
- Encrypting the root covers all 6 files for 5 + 6 = 11, less than the 12 of any split.
Example 3
- Input:
- files = ["x.txt"], targets = ["x.txt"], file_cost = 9, dir_cost = 2, bulk_rate = 1
- Output:
- 3
Constraints
0 <= len(files) <= 2000fileshas no duplicates, no file is also a directory of another file, and each path has at most 20 segmentstargetsis a subset offiles0 <= file_cost, dir_cost, bulk_rate <= 1000