- Data Structures And Algorithms 1 (178.54 KiB) Viewed 40 times
Data structures and Algorithms
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
Data structures and Algorithms
Data structures and Algorithms
6. (5 marks) In the baseball elimination problem, we can show that if wi+ri≤wk+rk and team k is eliminated, then team i is also eliminated (where wi denotes the wins of team i, and ri denotes the number of games that team i has left to play). Use this fact to show that in a division containing n teams, we can determine all the eliminated teams by solving O(logn) maxflow problems.
6. (5 marks) In the baseball elimination problem, we can show that if wi+ri≤wk+rk and team k is eliminated, then team i is also eliminated (where wi denotes the wins of team i, and ri denotes the number of games that team i has left to play). Use this fact to show that in a division containing n teams, we can determine all the eliminated teams by solving O(logn) maxflow problems.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!