update

kamyu104 · Oct 23, 2023 · f772047 · f772047
1 parent 72e215c
commit f772047
Show file tree

Hide file tree

Showing 2 changed files with 2 additions and 2 deletions.
diff --git a/README.md b/README.md
@@ -39,4 +39,4 @@
 |A2| [Ready, Go (Part 2)](https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/A1)| [Python3](./Round%202/ready_go_part_2.py3) | _O(R * C)_ | _O(R * C)_ | Easy | | BFS, DP |
 |B| [Meta Game](https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/B)| [Python3](./Round%202/meta_game.py3) | _O(N)_ | _O(1)_ | Easy | | Array |
 |C| [Wiki Race](https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/C)| [Python3](./Round%202/wiki_race.py3) [Python3](./Round%202/wiki_race2.py3) | _O(N + M * MAX_S)_ | _O(N + M * MAX_S)_ | Medium | | DFS, Freq Table, Tree DP |
-|D| [Tower Rush](https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/D)| [Python3](./Round%202/tower_rush.py3) | precompute: _O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))_<br>runtime: _O(N * log(max_h) + (max_h) * log(max_h))_ | _O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))_ | Hard | | Number Theory, Combinatorics, Inclusion-Exclusion Principle, Möbius Function, `Linear Sieve of Eratosthenes` |
+|D| [Tower Rush](https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/D)| [Python3](./Round%202/tower_rush.py3) | precompute: _O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))_<br>runtime: _O(N * F + (max_h) * log(max_h))_ | _O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))_ | Hard | | Number Theory, Combinatorics, Inclusion-Exclusion Principle, Möbius Function, `Linear Sieve of Eratosthenes` |
diff --git a/Round 2/tower_rush.py3 b/Round 2/tower_rush.py3
@@ -4,7 +4,7 @@
 # https://www.facebook.com/codingcompetitions/hacker-cup/2023/round-2/problems/D
 #
 # Time:  precompute: O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))
-#        runtime:    O(N * log(max_h) + (max_h) * log(max_h))
+#        runtime:    O(N * F + (max_h) * log(max_h)), F = max(len(DIVISORS[x]) for x in H)
 # Space: O(MAX_N + max(MAX_D, MAX_H) * log(max(MAX_D, MAX_H)))
 #