CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    May 2013
    Posts
    6

    Building bridges

    **Problem:**
    There is a river that runs horizontally through an area. There are a set of cities above and below the river. Each city above the river is matched with a city below the river, and you are given this matching as a set of pairs.

    You are interested in building a set of bridges across the river to connect the largest number of the matching pairs of cities, but you must do so in a way that no two bridges intersect one another.


    **My Approach:**
    I am sorting the first set and then finding the largest increasing subsequence from second set despite trying all test cases. I am getting wrong answer. Please help if there is something wrong with the approach or any test case i am missing.

    Here is the link to the original problem: http://www.spoj.com/problems/BRIDGE/

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct dj{
    int x;
    int y;
    }a[1000];
    inline int myf(dj dj1,dj dj2)
    {
    return dj1.x<dj2.x;
    }
    int main()
    {
    int n,t,L[1000],len;
    scanf("%d",&t);
    while(t--)
    {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i].x);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i].y);

    sort(a,a+n,myf);

    L[0]=1;
    len=1;
    for(int i=1;i<n;i++)
    {
    L[i]=1;
    for(int j=0;j<i;j++)
    {
    if((a[i].y>a[j].y)&&(L[i]<L[j]+1))
    L[i]=L[j]+1;
    }
    if(len<L[i])
    len=L[i];
    }
    printf("%d\n",len);
    }
    return 0;
    }

  2. #2
    Join Date
    May 2009
    Posts
    2,413

    Re: Building bridges

    Why can't you have just one bridge? That bridge would connect all cities above the river with all cities below.

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Building bridges

    Quote Originally Posted by nuzzle View Post
    Why can't you have just one bridge? That bridge would connect all cities above the river with all cities below.
    The full problem description explains the scenario and the constraints.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  4. #4
    Join Date
    May 2009
    Posts
    2,413

    Re: Building bridges

    Quote Originally Posted by 2kaud View Post
    The full problem description explains the scenario and the constraints.
    Well, if you get it please explain why bridging the third and fourth pairs is the correct solution?

    2 5 8 10
    6 4 1 2

  5. #5
    Join Date
    May 2013
    Posts
    6

    Re: Building bridges

    Originally we have 10 points.

    1 2 3 4 5 6 7 8 9 10
    <---- Cities on the first bank of river---->
    --------------------------------------------
    <--------------- River--------------->
    --------------------------------------------
    1 2 3 4 5 6 7 8 9 10
    <------- Cities on second bank of river------->

    Test Case:
    2 5 8 10
    6 4 1 2

    We can connect 8th city on first bank to the 1st city on second bank . This gives us one bridge. explained by (8,1) pair.
    secondly, we can connect 10th city on first bank to the 2nd city on second bank. This gives us 2 Non overlapping(non cutting) bridges.

    But if we consider connecting 2nd city on first bank to 6th city on second bank. Then this will cut all the three remaining bridges.
    Similary while connecting 5th city on first bank to 4th city on second bank.

    Thefore, maximum number of overlapping bridges are 2.

  6. #6
    Join Date
    May 2013
    Posts
    6

    Re: Building bridges

    got AC

    Anyone having error in the above program, can check out this working code.
    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    struct dj{
    int x;
    int y;
    }a[1000];
    inline int myf(dj dj1,dj dj2)
    {
    if(dj1.x<dj2.x)
    return 1;
    if(dj1.x==dj2.x)
    if(dj1.y<dj2.y)
    return 1;
    return 0;
    }
    int main()
    {
    int n,t,L[1005],len;
    scanf("%d",&t);
    while(t--)
    {
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i].x);
    for(int i=0;i<n;i++)
    scanf("%d",&a[i].y);

    sort(a,a+n,myf);

    L[0]=1;
    len=1;
    for(int i=1;i<n;i++)
    {
    L[i]=1;
    for(int j=0;j<i;j++)
    {
    if((a[i].y>=a[j].y)&&(L[i]<L[j]+1))
    L[i]=L[j]+1;
    }
    if(len<L[i])
    len=L[i];
    }
    printf("%d\n",len);
    }
    return 0;
    }

  7. #7
    Join Date
    May 2009
    Posts
    2,413

    Re: Building bridges

    Quote Originally Posted by codedhrj View Post
    Thefore, maximum number of overlapping bridges are 2.
    Thank you, I get it now.

    I think you've come up with a nice solution strategy. First sorting the bridges according to "from" and then finding the longest increasing subsequence among the "to". That would correspond to the largest number of non-intersecting bridges.

    The sorting is O(N*logN) but it looks like you have an O(N^2) algorithm for the subsequence part. According to this link, O(N*logN) is possible for the latter also,

    http://en.wikipedia.org/wiki/Longest...ng_subsequence

    That means a solution with a total complexity of O(N*logN) is possible for this problem.
    Last edited by nuzzle; May 31st, 2013 at 02:37 AM.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured