Problem Link - Catering Contracts
Problem Statement:
The government has invited bids from contractors to run canteens at all railway stations. Contractors will be allowed to bid for the catering contract at more than one station. However, to avoid monopolistic price-fixing, the government has declared that no contractor may bid for a pair of neighbouring stations.
The railway network has exactly one route between any pair of stations. Each station is directly connected by a railway line to at most 50 neighbouring stations.
To help contractors plan their bids, the government has provided data on the number of passengers who pass through each station each year. Contractors would like to bid for stations with a higher volume of passenger traffic to increase their turnover.
Approach:
To solve this, we use dynamic programming with depth-first search (DFS). We start by representing the railway stations and their connections as a tree. For each station, we need to decide whether to include it in the bid or not. If we include the station, we cannot include its direct neighbors, so we calculate the total profit of including this station and the profit of not including it. The optimal solution is then the maximum profit we can achieve.
The dynamic programming array, dp, has two values for each station: one for including the station in the bid and another for excluding it. The inclusion value adds the station’s passenger traffic to the profit and excludes the neighbors’ traffic. The exclusion value simply adds the maximum profit from its neighbors, whether they are included or not.
By recursively solving for all stations starting from the root, we can find the optimal solution. Finally, we return the maximum profit between including or excluding the root station.
Space Complexity:
The space complexity is O(n), where n is the number of stations, due to the storage required for the dp array, visited array, and the recursion stack.
Time Complexity:
The time complexity is O(n), where n is the number of stations, as we are visiting each station once using DFS.