Question
Ahuja et al. found that using a van Emde Boas tree reduces the complexity of this problem to “big O of m log log C” when certain values are bounded by C. For hidden Markov models, the Viterbi algorithm essentially solves this problem with probabilistic weights added. Fredman and Tarjan used Fibonacci heaps to find the asymptotically fastest known algorithm for one form of this problem, improving on Johnson’s algorithm. The Floyd–Warshall algorithm solves this problem for multiple sources. A priority queue is typically used to store unvisited items in a “big O of m log n” algorithm for this task. The Bellman–Ford algorithm works for this problem even if edge weights are negative, unlike Dijkstra’s algorithm. For 10 points, name this problem of finding the minimum-distance route between two vertices of a graph. ■END■
Summary
2024 ACF Regionals @ Berkeley | 01/27/2024 | Y | 1 | 100% | 0% | 0% | 71.00 |
2024 ACF Regionals @ JMU | 01/27/2024 | Y | 1 | 100% | 0% | 0% | 134.00 |
2024 ACF Regionals @ JMU | 01/27/2024 | Y | 1 | 100% | 0% | 0% | 83.00 |
2024 ACF Regionals @ Nebraska | 01/27/2024 | Y | 6 | 83% | 0% | 33% | 118.80 |
2024 ACF Regionals @ Imperial | 01/27/2024 | Y | 8 | 88% | 0% | 50% | 115.57 |
2024 ACF Regionals @ Vanderbilt | 01/27/2024 | Y | 1 | 100% | 0% | 0% | 116.00 |
2024 ACF Regionals @ MIT | 01/27/2024 | Y | 3 | 67% | 0% | 100% | 134.00 |
Buzzes
Player | Team | Opponent | Buzz Position | Value |
---|---|---|---|---|
Omer Keskin | Oxford A | Imperial A | 68 | 10 |
Michał Gerasimiuk | Stanford A | Stanford B | 71 | 10 |
Linus Luu | Cambridge C | Durham B | 78 | -5 |
Rasheeq Azad (UG) | UNC B (UG) | Maryland A (Grad) | 83 | 10 |
Andrew Fisher | Sheffield | Kiel | 92 | -5 |
Carlos Doebeli | Imperial B | Cambridge A | 93 | -5 |
Matt Sheldon | Oxford C | Oxford B | 93 | 10 |
Rahul Kumar | Rice A | Texas A&M B | 96 | -5 |
Parth Jagtap | Edinburgh | Warwick | 96 | -5 |
Ashton Lewis | Dartmouth A | Brown A | 100 | -5 |
Akshay Seetharam | Claremont A | UW A | 104 | 10 |
Shantanu Thorat | Texas A&M A | Sorbonne | 107 | 10 |
Matthew Wang | UBC A | Texas A | 115 | 10 |
Michael Sun | Brandeis B | Boston University | 115 | -5 |
Michael Sun | Brandeis B | Boston University | 115 | -5 |
Jack Lewis | MTSU | Geodesic | 116 | 10 |
Michael Kohn | Durham A | Cambridge B | 118 | 10 |
Thomas Hart | Warwick | Edinburgh | 128 | 10 |
Jason Thieu | Michigan State A | Iowa A | 129 | -5 |
Daniel Kim (DII) | Maryland C (DII) | Liberty B (DII) | 134 | 10 |
Caleb Hines (DII) | Liberty B (DII) | Maryland C (DII) | 134 | 0 |
Ryan Dunn | Iowa B | Appalachian State | 134 | 10 |
Roan Dowling | Iowa A | Michigan State A | 134 | 0 |
Dimitris Kalafatis | Texas A&M B | Rice A | 134 | 10 |
Kevin Flanagan | Bristol | KCL | 134 | 10 |
Nick Pruitt | KCL | Bristol | 134 | 0 |
Ian Dewan | Kiel | Sheffield | 134 | 0 |
Aisling Skeet | Durham B | Cambridge C | 134 | 10 |
Maxwell Ye | Cambridge A | Imperial B | 134 | 10 |
Jason Hong | Brown A | Dartmouth A | 134 | 0 |
Cindy Zhou | Boston University | Brandeis B | 134 | 10 |
Cindy Zhou | Boston University | Brandeis B | 134 | 10 |