Building Bridges
Introduction
Several problems cannot be solved using regular algorithms like greedy or divide and conquer, or the solutions they provide are not optimal.
So, we use Dynamic Programming, which is an optimization of simple recursion to solve such problems. The basic idea is to store the results of sub-problems to avoid recalculation and reduce the time complexity of the problems.
The problem of Building Bridges is a classical question of Dynamic Programming and is considered to be a variation of Longest Increasing Subsequences.
Problem Statement:
The problem states that there are 2 * N cities situated along the bank of a river, with N cities lying to the North of the river and N lying on the Southern bank of the river. The coordinates of cities on the Northern bank and the Southern bank are given as the input.
Your task is to connect the cities of the Northern bank with that of the Southern bank with the help of bridges, but the bridges must not overlap each other.
Find the maximum number of bridges that can be formed satisfying the given conditions.
Example
- N = 4
A[] = {6, 4, 2, 1}
B[] = {2, 3, 6, 5}
Thus, the maximum number of bridges that can be formed without overlapping is 2.
2. N = 4
A[] = {3, 2, 2, 1}
B[] = {5, 4, 5, 2}
Thus, the maximum number of bridges that can be formed without overlapping is 4.
Dynamic Programming
For building bridges, we will have to see all possible combinations of bridges and check which one is the most optimal to provide the maximal answer. This will make repetitive calculations, and to avoid such repetitions, we will store the answers in a memoization array.
Algorithm
- Store the coordinates of the cities in a pair.
- Sort the pairs according to the south coordinates in increasing order.
- The north and south coordinates should both be in the increasing order or decreasing order to avoid overlapping.
- Since we sorted the coordinates of the cities on the Southern bank, we need to find the coordinates of cities on the Northern bank that are increasing or decreasing to find the maximum number of non-overlapping bridges.
- Now we will find the Longest Increasing Subsequence of the coordinates of the North to find the maximum number of bridges.
- In this problem, a value greater than or equal to the previous value can also be considered part of the increasing subsequence.
Note: In the original algorithm, we chose the element only if it is greater than the previous one, but the values equal to the previous one also work in this problem.
Let us understand the above algorithm with the help of an example:
The number of cities on each bank, N = 4
The coordinates of cities on the Northern bank, A[] = {6, 4, 2, 1}
The coordinates of cities on the Southern bank, B[] ={2, 3, 6, 5}
We will first sort the arrays according to the Southern coordinates.
Now, we will find the longest increasing subsequence of the Northern coordinates.
The LIS is given by {1, 2 }.
Thus, the length of the LIS is 2.
Hence the maximum number of bridges is also 2.
Implementation
Program
// C++ program to implement building bridges using Dynamic Programming.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to find the maximum number of bridges that can be constructed.
int maxBridges(vector<pair<int, int>> &values, int n)
{
int memo[n];
for (int i = 0; i < n; i++)
memo[i] = 1;
// Sorting the values according to the South Coordinates.
// We have passed in the South-North coordinates in the function.
sort(values.begin(), values.end());
// Initialising a variable that will store the length of the LIS.
int max = memo[0];
// Finding the length of the longest increasing subsequence on the Northern coordinates.
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
if (values[i].second >= values[j].second && memo[i] < 1 + memo[j])
{
memo[i] = 1 + memo[j];
}
// Finding the maximum length at every step.
if (max < memo[i])
{
max = memo[i];
}
}
}
// Returning the maximum number of bridges that can be built.
return max;
}
int main()
{
int n, i;
vector<int> north, south;
int a;
// Taking user input.
cout << "Enter the total number of cities on each bank: \n";
cin >> n;
cout << "Enter the coordinates of the cities on the northern bank: \n";
for (i = 0; i < n; i++)
{
cin >> a;
north.push_back(a);
}
cout << "Enter the coordinates of the cities on the southern bank:\n";
for (i = 0; i < n; i++)
{
cin >> a;
south.push_back(a);
}
// Making a vector pair with south coordinates and the north coordinates.
vector<pair<int, int>> values;
for (i = 0; i < n; i++)
{
values.push_back({south[i], north[i]});
}
// Calling the function and printing the output.
cout << "The maximum number of bridges that can be constructed is " << maxBridges(values, n);
return 0;
}
Input:
Enter the total number of cities on each bank:
4
Enter the coordinates of the cities on the northern bank:
6 4 2 1
Enter the coordinates of the cities on the southern bank:
2 3 6 5
Output:
The maximum number of bridges that can be constructed is 2.
Time Complexity
Since a nested loop is being used to compute the LIS, and hence the maximum number of bridges, the time complexity of this approach is given by O(N^{2}).
Space Complexity
An extra array of size N is taken to store the value of LIS at every index, thus the space complexity is given by O(N).
Optimized DP
Since this problem, Building Bridges, is a variation of the Longest Increasing Subsequence, we can optimize the solution for LIS itself.
Algorithm
- Store the coordinates of the cities in a pair.
- Sort the pairs according to the North coordinates in increasing order.
- Since the Northside is increasing, we will find the Longest Increasing Subsequence for the Southern coordinates.
- The length of this longest increasing subsequence will be the answer to our problem.
- In this method, we create a DP array and initialize it with an enormous value, say INT_MAX.
- We traverse the Southern Coordinates one by one, and then find the index of the just next greater element present in the DP array and update it with the value of this Southern coordinate. The length of the LIS, which is ending at that index, will be increased by 1.
- Note that the smallest element will have the highest chance of contributing to the LIS.
- Subsequently, we will keep track of the maximum LIS and this maximum will be our answer.
Let us try to understand this with the help of an example.
The number of cities on each bank, N = 4
The coordinates of cities on the Northern bank, A[] = {6, 4, 2, 1}
The coordinates of cities on the Southern bank, B[] = {2, 3, 6, 5}
We will first sort the arrays according to the Northern coordinates.
Now, we have to find the LIS for the Southern Coordinates:
Let’s consider our DP array:
DP[5] =
Let us store the LIS at every index in the variable ANS.
- i = 0
value = 5
Next greater element in the DP array = INT_MAX
Index of next greater element = 0
DP[5] becomes:
ANS = max(0, 0+1)
= max(0,1)
= 1
- i = 1
value = 6
Next greater element in the DP array = INT_MAX
Index of next greater element = 1
DP[5] becomes:
ANS = max(1, 1+1)
= max(1,2)
= 2
- i = 2
value = 3
Next greater element in the DP array = 5
Index of next greater element = 0
DP[5] becomes:
ANS = max(2, 0+1)
= max(2,1)
= 2
- i = 3
value = 2
Next greater element in the DP array = 3
Index of next greater element = 0
DP[5] becomes:
ANS = max(2, 0+1)
= max(2,1)
= 2
Thus, the length of the LIS is 2.
Hence the maximum number of bridges will be 2.
Implementation
Program
// Optimized C++ program to implement building bridges using Dynamic Programming.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function to find the maximum number of bridges that can be constructed.
int maxBridges(vector<pair<int, int>> & values, int n)
{
// Sorting the values according to the North Coordinates.
// We have passed in the North-South coordinates in the function.
sort(values.begin(), values.end());
// Creating a DP array to store the number of non-overlapping bridges.
vector<int> dp(n + 1, INT_MAX);
// To store the maximum number of non-overlapping bridges.
int ans = 0;
for (int i = 0; i < n; i++)
{
// Provides the index of the next greater element.
int idx = lower_bound(dp.begin(), dp.end(), values[i].second) - dp.begin();
dp[idx] = values[i].second;
ans = max(ans, idx + 1);
}
return ans;
}
int main()
{
int n, i;
vector<int> north, south;
int a;
// Taking user input.
cout << "Enter the total number of cities on each bank: \n";
cin >> n;
cout << "Enter the coordinates of the cities on the northern bank: \n";
for (i = 0; i < n; i++)
{
cin >> a;
north.push_back(a);
}
cout << "Enter the coordinates of the cities on the southern bank:\n";
for (i = 0; i < n; i++)
{
cin >> a;
south.push_back(a);
}
// Making a vector pair with north coordinates and the south coordinates.
vector<pair<int, int>> values;
for (i = 0; i < n; i++)
{
values.push_back({north[i], south[i]});
}
cout << "The maximum number of bridges is " << maxBridges(values, n);
return 0;
}
Input:
Enter the total number of cities on each bank:
4
Enter the coordinates of the cities on the northern bank:
6 4 2 1
Enter the coordinates of the cities on the southern bank:
2 3 6 5
Output:
The maximum number of bridges that can be constructed is 2.
Time Complexity
In this approach, we traverse a single loop from index 0 to N-1, and in every iteration, we use a lower bound, which costs O(log N) time. Thus, the time complexity is given by O(N * log N).
Space Complexity
Since it uses an extra DP array for storing the number of non-overlapping bridges, the space complexity is given by O(N).
Key Takeaways
So, this blog discussed the classical problem of building bridges, how it can be solved using the concept of Longest Increasing Subsequence, and how it can be further optimized to reduce time complexity.
To learn more, head over right now to CodeStudio to practice problems on dynamic programming and crack your interviews like a Ninja!
In case of any comments or suggestions, feel free to post them in the comments section.
By Ishita Chawla
Comments
No comments yet
Be the first to share what you think