Building Bridges – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves Building Bridges Problem using Dynamic Programming technique.

Problem Description

There is a river. There are n cities on both sides of the river (not necessarily in the same order). Bridges are to be built on the river for every city (from one end of the river to the other end where the same city is located). But no two bridges should intersect. Find out the maximum number of cities for which the bridges can be built over the river.

NOTE- For every city i on one end, there is a city i on the other end.

Problem Solution

This problem is a variant longest increasing subsequence(LIS). First, we reorder the numbering of cities based on ordering of the other end. Now, the answer to the problem is simply the simply the LIS of the cities on the first end. (Look at the example below for further clarification).

Expected Input and Output

Case-1:

 
There are 4 cities.
The cities on first end of the river are in order 4 1 3 2
The cities on other end of the river are in order 1 3 4 2
 
First, we reorder the numbering of cities based on ordering of the other end
first end after reordering 3 1 2 4
other end after reordering 1 2 3 4
 
Now, simply calculate longest increasing subsequence of the cities on first end(after reordering).
 
LIS(3,1,2,4)=3
So, there can be atmost 3 non-intersecting bridges for this example.
Program/Source Code

Here is source code of the C++ Program to Solve Building Bridges Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

advertisement
advertisement
  1. #include<iostream>
  2. #include<utility>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<map>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. int lis(int a[], int n)
  11. { 
  12.     int i, j;
  13.  
  14.     //create an array b of size n ie, b[n]
  15.     //b[i] represents the value of longest increasing subsequence with a[i] being the last element
  16.  
  17.     //b[i]=longest increasing subsequence for the array a[0...i] by including a[i] in the subseuence
  18.     //at the end
  19.  
  20.     int b[n];
  21.  
  22.     //Since, we are definitely including a[i] for the calculation of b[i], b[i] will 
  23.     //either be equal to 1 or greater than 1
  24.     //so, initialize b
  25.     for(i=0;i<n;i++)
  26.         b[i]=1;
  27.  
  28.  
  29.     //now, we have to fill this b array
  30.  
  31.     //we will calulate the value of b[i] for every 1<=i<=n by checking whether any subsequence
  32.     //b[0], b[1],...,b[i-1] can fit before a[i] and then selecting the maximum out of them
  33.     for(i=1;i<n;i++)
  34.     {
  35.         //for every i, we will check all values of 0<=j<i for subsequences b[j] to which a[i]
  36.         //could be appended and select the longest one
  37.         for(j=0;j<i;j++)
  38.         {
  39.             //if the current element ie, the ith element has value greater than jth element, that
  40.             //means a[i] can be appended after b[j]
  41.             //Since, we are interested in finding the longest of such subsequences, we will consider
  42.             //only those values of b[j] that are greater than or equal to b[i]
  43.             if(a[i]>a[j] && b[i]<b[j]+1)
  44.             {
  45.                 b[i]=b[j]+1;
  46.             }
  47.         }
  48.     }
  49.  
  50.     //now, we have calculated all the values of b[i] for 0<=i<n
  51.     //The length of the longest increasing subsequence of the given array is the maximum of all
  52.     //these values because the longest increasing subsequence can end with any element of the array
  53.  
  54.     //finding maximum element in b array
  55.     int max=0;
  56.  
  57.     for(i=0;i<n;i++)
  58.     {
  59.         if(b[i]>max)
  60.             max=b[i];
  61.     }
  62.  
  63.     return max;
  64. }
  65.  
  66.  
  67. int main()
  68. {
  69.     int i;
  70.     int n;
  71.     int index;
  72.  
  73.     cout<<"Enter the total number of cities"<<endl;
  74.     cin>>n;
  75.  
  76.     int first_end[n];
  77.     int other_end[n];
  78.     map<int,int> mp;
  79.     int reorder_first_end[n];
  80.  
  81.     cout<<"Enter the ordering of cities on first end"<<endl;
  82.     for(i=0;i<n;i++)
  83.     {
  84.         cin>>first_end[i];
  85.         mp[first_end[i]]=i;
  86.     }
  87.  
  88.     cout<<"Enter the ordering of cities on the other end"<<endl;
  89.     for(i=0;i<n;i++)
  90.     {
  91.         cin>>other_end[i];
  92.  
  93.         //reordering
  94.         index=mp[other_end[i]];
  95.         reorder_first_end[index]=i+1;
  96.     }
  97.  
  98.     cout<<"Maximum number of cities for which bridges can be made is "<<endl;
  99.     cout<<lis(reorder_first_end,n);
  100.  
  101.     cout<<endl;
  102.     return 0;
  103. }
Program Explanation

In the main function, we ask the user to input the cities on both the ends. Then we will reorder the number of cities on the first end. We pass these reordered numbering of cities on first end to the function lis as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases
 
Case-1:
$ g++ building_bridges.cpp
$ ./a.out
Enter the total number of cities
4
Enter the ordering of cities on first end
4 1 3 2
Enter the ordering of cities on the other end
1 3 4 2
Maximum number of cities for which bridges can be made is 
3

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.