You are now a Civil Engineer and have been hired by BridgeCorp to design the opt

Question

You are now a Civil Engineer and have been hired by BridgeCorp to design the optimal bridge schema for Riverbank County. The county consists of n cities on each side of a river labeled 1,... n. An example of such a county with n = 8 is given below: 2, 6, 3, 5, 4, 1, 8, 7 --- River - -- 5, 2, 1, 3, 7, 6, 4, 8 Your boss wants you to design a schema such that there are as many bridges as possible con- necting cities on either end of the river. There are two constraints: bridges can only connect cities with matching labels and bridges are not allowed to cross. An optimal solution for the above situation would be to build bridges between cities 2, 3, 4, and 8. Design an O(n2) algorithm using Dynamic Programming to build an optimal schema for your boss's request. You must prove both the correctness and the runtime complexity for your boss to accept your proposal. Hint: One solution to this problem involves solving the LIS problem described in lecture.

Explanation / Answer

The two series are 2,6,3,5,4,1,8,7

and 5,2,1,3,7,6,4,8. For solving this, we reorder the numbering of cities based on ordering of the other end position of the city. Now, the solution of the problem is simply the LIS of the cities on the first end.

The code is as follows:

#include<iostream>
#include<utility>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;


int lis(int a[], int n)
{
int i, j;

//b[i]=longest increasing subsequence for the array a[0...i] by including a[i] in the subseuence at the end

int b[n];

// initialize b
for(i=0;i<n;i++){
b[i]=1;
}

//now, we have to fill this b array

//we will calulate the value of b[i] for every 1<=i<=n by checking whether any subsequence
//b[0], b[1],...,b[i-1] can fit before a[i] and then selecting the maximum out of them
for(i=1;i<n;i++)
{
  
for(j=0;j<i;j++)
{
//if the current element ie, the ith element has value greater than jth element, that
//means a[i] can be appended after b[j]
//Since, we are interested in finding the longest of such subsequences, we will consider
//only those values of b[j] that are greater than or equal to b[i]
if(a[i]>a[j] && b[i]<b[j]+1)
{
b[i]=b[j]+1;
}
}
}
//finding the maximum value in b
int max=0;

for(j=0;j<n;j++)
{
if(max<b[j])
max=b[j];
}

return max;
}


int main()
{
int i;
int n;
int index;

cout<<"Enter the total cities"<<endl;
cin>>n;

int first_end[n];
int other_end[n];
map<int,int> mp;
int reorder_first_end[n];

cout<<"Enter the cities on first end"<<endl;
for(i=0;i<n;i++)
{
cin>>first_end[i];
mp[first_end[i]]=i;
}

cout<<"Enter the cities on the other end"<<endl;
for(i=0;i<n;i++)
{
cin>>other_end[i];

//reordering
index=mp[other_end[i]];
reorder_first_end[index]=i+1;
}

cout<<"Maximum number of cities for which bridges can be made is "<<endl;
cout<<lis(reorder_first_end,n);

cout<<endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.