Problem link
Difficulty
MEDIUM
Pre-requisites
binary search, max flow
Problem
There are n goods and m channels which can transport the goods. A[i][j] denotes time taken for ith good to be transmitted by jth channel. Find smallest time T such that you are able to transpost at least K
goods.
Solution
Binary Search Idea
You can observe that if you get more time, you will be able to transport more goods. So you can convert this idea into a binary search over T (time). Your function f(T) will tell you
maximum number of goods you can transport in time <= T. Your objective is to find smallest T such that f(T) >= K. You can notice that f(T) is an increasing function. So we can use binary search.s
Calculating f(T)
Let’s create a bipartite graph. In the left part, we have all the goods and in the right part, we have all the channels.
We will add an edge between good i and channel j if A[i][j] <= T. This edge denotes that we can transport ith good via jth channel.
Note that value of maximum number of goods transported will be exactly equal to maximum matching in the above bipartite graph.
Maximum Matching in bipartite graph
You can create a flow network by adding all the left part nodes to source with a capacity of 1. Similarly also add all the right part nodes to sink with capacity of 1.
Now apply max flow in the above network constructed. Maximum flow in this network will give maximum bipartite matching in the bipartite graph.
Complexity
log(max(A[i][j][)) * time taken in max flow (this can vary depending on your algorithm for max flow).
Tester’s solution: Will be added later.