## 1172 - The Bridges of Kolsberg

Moderator: Board moderators

Degiac
New poster
Posts: 2
Joined: Thu Sep 04, 2014 11:41 pm
Location: Salerno, Italy
Contact:

### Re: 1172 - The Bridges of Kolsberg

Has someone got some tricky test cases for this problem? I keep getting WA and I can't realize why. I wrote some test cases myself but I always get the right answer

EDIT: nvm, solved

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 1172 - The Bridges of Kolsberg

I added some random input at:
http://www.udebug.com/UVa/1172
Check input and AC output for thousands of problems on uDebug!

New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

### Re: 1172 - The Bridges of Kolsberg

Hi, Can anybody tell me How to proceed to solve this problem? It looks like matching with some constraints. Please give me some hints?

New poster
Posts: 3
Joined: Thu Jul 09, 2015 5:20 am

### Re: 1172 - The Bridges of Kolsberg

Hey guys,

I solved this problem and only got accepted after considering the constraint: no city could be an endpoint of more than one bridge. Does the problem description imply this constraint ? If anyone got accepted without considering such a constraint, I would appreciate telling me briefly his algorithm to look for my bug, if any.

Thanks

Shafayat
New poster
Posts: 7
Joined: Mon Jan 19, 2015 11:32 am

### Re: 1172 - The Bridges of Kolsberg

Why I'm getting WA?

Code: Select all

``````#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;

struct bridge
{
long long int cost;
char city,os;
}le,ri;     //store inputs. 'le' for first bank and 'ri' for second bank

struct table
{
long long int pos;
long long int co;   // stores the cost
long long int cou;  // count the bridge
}tab;         //table for current maximum cost and minimum number of bridge

/* in this solve function I use algorithm like coin change algorithm.
here, I create a table.
for all bridges in 're', i choose bridge from 'le' and find current maximum cost and minimum number of bridge.*/

void solve(long long int a,long long int b)
{
memset(tab,0,sizeof(tab));
for(long long int i=0;i<a;i++)     //Select bridge from le
{
for(long long int j=0;j<b;j++)   //Select bridge from re
{
if(strcmp(le[i].os,ri[j].os)==0)      // compare OS name
{
if((tab[i][j].co+le[i].cost+ri[j].cost)>tab[i][j+1].co && (tab[i][j].co+le[i].cost+ri[j].cost)>tab[i+1][j].co)  // check if (cost stored in previous diagonal cost from table+ cost of current bridge) is greater than cost stored in upward position and left position of the table
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
tab[i+1][j+1].pos=j+1;   // stores the position where I get current maximum
tab[i+1][j+1].cou=tab[i][j].cou+1;   // count the bridge number

}
else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i][j+1].co)   // if current cost and cost of upward position in table is same than choose that one which contains minimum number of bridge
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
if((tab[i][j].cou+1)<tab[i][j+1].cou)
{
tab[i+1][j+1].pos=j+1;
tab[i+1][j+1].cou=tab[i][j].cou+1;
}
else
{
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}

}
else if((tab[i][j].co+le[i].cost+ri[j].cost)==tab[i+1][j].co)  // if current cost and cost of left position in table is same
{
tab[i+1][j+1].co=tab[i][j].co+le[i].cost+ri[j].cost;
if((tab[i][j].cou+1)<tab[i+1][j].cou)
{
tab[i+1][j+1].pos=j+1;
tab[i+1][j+1].cou=tab[i][j].cou+1;
}
else
{
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}

}
// conditions after this line works if (cost stored in previous diagonal cost from table+ cost of current bridge) is smaller than upward and left position
else if(tab[i][j+1].co>tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co<tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou<tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co==tab[i+1][j].co && tab[i][j+1].cou>tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
}
}
else    // if OS name does not matches than I choose from upward and left position
{
if(tab[i][j+1].co>tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].co<tab[i+1][j].co)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
if(tab[i][j+1].cou<tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i][j+1].co;
tab[i+1][j+1].pos=tab[i][j+1].pos;
tab[i+1][j+1].cou=tab[i][j+1].cou;
}
else if(tab[i][j+1].cou>tab[i+1][j].cou)
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
else
{
tab[i+1][j+1].co=tab[i+1][j].co;
tab[i+1][j+1].pos=tab[i+1][j].pos;
tab[i+1][j+1].cou=tab[i+1][j].cou;
}
}
}
}
}

}

int main()
{
long long int a,b,c,d,e,f,g,h;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin>>a;
for(b=1;b<=a;b++)
{
cin>>c;
for(d=0;d<c;d++)
{
cin>>le[d].city>>le[d].os>>le[d].cost;
}
cin>>d;
for(e=0;e<d;e++)
{
cin>>ri[e].city>>ri[e].os>>ri[e].cost;
}
solve(c,d);
for(int i=0;i<=c;i++)
{
for(int j=0;j<=d;j++)
{
printf("%8lld-%lld ",tab[i][j].co,tab[i][j].cou);
}
cout<<endl;
}
printf("%lld %lld\n",tab[c][d].co,tab[c][d].cou);
}
return 0;
}

``````

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

### Re: 1172 - The Bridges of Kolsberg

Be careful of the boundary condition.