140 - Bandwidth
Moderator: Board moderators
140
Can anyone help me with this problem?
thx for any hints
thx for any hints
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
140 - "Bandwith" - WA - please help
I got WA on this problem ...
I wonder where I could be wrong ? please help ...
I wonder where I could be wrong ? please help ...

-
- Learning poster
- Posts: 93
- Joined: Sun Jan 12, 2003 3:30 pm
140 bandwidth inputs
Hi
Can someone provide input output for 140 bandwidth .. I am stuck on it using a backtracking solution.
-Dhyanesh
Can someone provide input output for 140 bandwidth .. I am stuck on it using a backtracking solution.
-Dhyanesh
140 Bandwidth input
Can somebody please help me with some more input data to problem 140, I get a "Runtime Error" (sigsegv) by the online judge, I need more input data to track down this bug.
Problem 140 Bandwidth
I have checked with many test cases i got on net n my program is giving the right answers still i m getting WA....can anybody giv me some more test cases or can give sm particular case of getting a WA
Search the board first, dont open a new thread if there is one already. Check the following threads...
http://online-judge.uva.es/board/viewto ... hlight=140
http://online-judge.uva.es/board/viewto ... hlight=140
http://online-judge.uva.es/board/viewto ... hlight=140
http://online-judge.uva.es/board/viewto ... hlight=140
Ami ekhono shopno dekhi...
HomePage
HomePage
I got several WAs, anyone check these i/o?
thanks in advance.
Input:
My output:
EDIT: after Jan answered my problem, I noticed I had a wrong input, sorry for that.
thanks in advance.
Input:
Code: Select all
A:FB;B:GC;D:GC;F:AGH;E:HD
A:FB;B:GC;D:GC;F:AGH;E:H
A:B;B:C;C:D;D:E;E:F;F:G;G:H
A:B;B:C;C:D;D:E;E:F;F:G;G:H;H:A
A:B;B:CE;C:D;D:E;E:F;F:G;G:H;H:A
A:B;B:CE;CG:D;D:E;E:F;F:G;G:H;H:A <--Wrong Input, sorry
A:B;B:CE;C:DG;D:E;E:F;F:G;G:H;H:A
A:BCDEFGH;B:ACDEFGH;C:ABDEFGH;D:ABCEFGH;E:ABCDFGH;F:ABCDEGH;G:ABCDEFH;H:ABCDEFG
#
Code: Select all
A B C F G D H E -> 3
C D B G A F E H -> 2
A B C D E F G H -> 1
A B H C G D F E -> 2
C D B E A F H G -> 2
A B C E D F G H -> 2
A B H C E G D F -> 3
A B C D E F G H -> 7
Last edited by hi!man! on Sun Aug 12, 2007 3:07 am, edited 1 time in total.
My accepted code returns.
Output:
Hope these help.
Output:
Code: Select all
A B C F G D H E -> 3
C D B G A F E H -> 2
A B C D E F G H -> 1
A B H C G D F E -> 2
C D B E A F H G -> 2
A B C H E D G F -> 3
A B H C E G D F -> 3
A B C D E F G H -> 7
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 4
- Joined: Fri Jul 18, 2008 9:44 pm
Re: 140 - bandwith
plz somebody help i m keep getting wrong answer , above test cases r running


Code: Select all
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include<string>
#define MAX 1000001
using namespace std;
string i2s(int n)
{ stringstream ss;
ss<<n;
return ss.str();
}
int s2i(string h)
{ stringstream ss;
ss<<h;
int n;
ss>>n;
return n;
}
int main()
{ string h1="";
while(getline(cin,h1))
{ if(h1=="#")
{ break;
}
set<char> s;s.clear();
for(int i=0;i<h1.size();i++)
{ if(h1[i]!=';' && h1[i]!=':')
{ s.insert(h1[i]);
}
}
vector<char> re;re.clear();
for(set<char>::iterator i1=s.begin();i1!=s.end();i1++)
{ re.push_back(*i1);
}
int arr[s.size()][s.size()];memset(arr,0,sizeof(arr));
int cnt=0;
// formation of the graph for connectivity
for(set<char>::iterator i1=s.begin();i1!=s.end();i1++)
{ string k1="";k1+=(*i1);k1+=":";
int pos=h1.find(k1);
if(pos==string::npos)
{ cnt++;continue;
}
pos+=2;
while(h1[pos]!=';' && pos<h1.size())
{ int pos1=find(re.begin(),re.end(),h1[pos])-re.begin();
arr[cnt][pos1]=1;arr[pos1][cnt]=1;
pos++;
}
cnt++;
}
// formation of string having all symbols neighbours
string h="";
for(int i=0;i<s.size();i++)
{ h+=re[i];h+=":";
for(int j=0;j<s.size();j++)
{ if(arr[i][j]==1){h+=re[j];}
}
h+=";";
}
h.erase(h.size()-1);
vector<char> save;save.clear();
int min3=1000000000;
// checking all the premutations
do
{ //case of bandwidth of ordering
int max1=-1;
for(int i=0;i<re.size();i++)
{ string k1="";k1+=re[i];k1+=":";
int pos=h.find(k1);pos+=2;int max2=-1;
while(h[pos]!=';' && pos<h.size())
{ int pos1=find(re.begin(),re.end(),h[pos])-re.begin();
int val=abs(pos1-i);
max2=max(max2,val);
pos++;
}
max1=max(max1,max2);
}
if(min3>max1)
{ min3=max1;
save.clear();
for(int i=0;i<re.size();i++){save.push_back(re[i]);}
}
}while(next_permutation(re.begin(),re.end()));
for(int i=0;i<save.size();i++)
{ cout<<save[i]<<" ";
}
cout<<"-> "<<min3<<endl;
}
system("pause");
}