Baseball Elimination Assignment 👨🏫
ps: Следующую часть лучше прочитать, только когда будете делать задание, иначе без контекста не сложно понять :)
У нас есть таблица бейсбольный матчей. Нам нужно понять, какие команды точно не попадут в победители, как бы не сыграли другие команды.
Как выполнить задание и не сдаться? 💪
Читаем презентацию: https://www.cs.princeton.edu/~wayne/papers/baseball_talk.pdf
1. Начинаем с самого простого, считываем таблицу из текстового файла и записываем в нужные структуры:
- массив с количеством побед win[teams.length]
- массив с количеством проигрышей losses[teams.length]
- массив с оставшимися играми rem[teams.length]
- массив с количеством матчей команд с другом другом games[teams.length][teams.length]
- массив команд teams[teams.length]
- мапа для конвертации индекса команды в название Map<int,string>
Для того, чтобы построить FlowNetwork, чтобы определить вылетит ли команда, нам нужно:
- Все матчи где не участвует эта команда - пилим отдельный метод на это и возвращаем все матчи, других команд
- Размер сети - Количество команда + Количество матчей + sink node + source node
2. Теперь у нас есть все, чтобы построить сеть:
- Коннектим с помощью FlowEdge sink node c нодами команды и выставляем им capacity = w[target] + r[target] - w[current], где target команда, которую проверяем на вылет, a current - текущая.
Зачем это делаем? Так мы ограничиваем количество побед, которых команда может получить. Далее поясню.
- Соединяем матчи с командами, тут capacity не ограничен, ставим Infinity
- Соединяем source node c матчами, capacity будет равен количеству оставшихся игр у команда games[team1][team2]
Я долго не мог уловить момент с распределением capacity, пока хорошенько не вчитался в течении 2 дней 😂
Суть такова: если ребра из source node, во время работы алгоритма Фалкерсона, заполняются не полностью, это значит что ограничение, которое мы создали в соединении команд и sink node нарушается, если бы они наполнились полностью. А это значит, что команда не может победить так как количество игр, распределенное между командами будет больше, чем количество возможных побед искомой команды.
В целом, это базовые советы, которые решают 90% задачи.
Следующие шаг: Закончить теорию по Radix Sort
#week_9 #assiignment
ps: Следующую часть лучше прочитать, только когда будете делать задание, иначе без контекста не сложно понять :)
У нас есть таблица бейсбольный матчей. Нам нужно понять, какие команды точно не попадут в победители, как бы не сыграли другие команды.
Как выполнить задание и не сдаться? 💪
Читаем презентацию: https://www.cs.princeton.edu/~wayne/papers/baseball_talk.pdf
1. Начинаем с самого простого, считываем таблицу из текстового файла и записываем в нужные структуры:
- массив с количеством побед win[teams.length]
- массив с количеством проигрышей losses[teams.length]
- массив с оставшимися играми rem[teams.length]
- массив с количеством матчей команд с другом другом games[teams.length][teams.length]
- массив команд teams[teams.length]
- мапа для конвертации индекса команды в название Map<int,string>
Для того, чтобы построить FlowNetwork, чтобы определить вылетит ли команда, нам нужно:
- Все матчи где не участвует эта команда - пилим отдельный метод на это и возвращаем все матчи, других команд
- Размер сети - Количество команда + Количество матчей + sink node + source node
2. Теперь у нас есть все, чтобы построить сеть:
- Коннектим с помощью FlowEdge sink node c нодами команды и выставляем им capacity = w[target] + r[target] - w[current], где target команда, которую проверяем на вылет, a current - текущая.
Зачем это делаем? Так мы ограничиваем количество побед, которых команда может получить. Далее поясню.
- Соединяем матчи с командами, тут capacity не ограничен, ставим Infinity
- Соединяем source node c матчами, capacity будет равен количеству оставшихся игр у команда games[team1][team2]
Я долго не мог уловить момент с распределением capacity, пока хорошенько не вчитался в течении 2 дней 😂
Суть такова: если ребра из source node, во время работы алгоритма Фалкерсона, заполняются не полностью, это значит что ограничение, которое мы создали в соединении команд и sink node нарушается, если бы они наполнились полностью. А это значит, что команда не может победить так как количество игр, распределенное между командами будет больше, чем количество возможных побед искомой команды.
В целом, это базовые советы, которые решают 90% задачи.
Следующие шаг: Закончить теорию по Radix Sort
#week_9 #assiignment
👍2