140 - Bandwidth

[dennis]

Can anyone help me with this problem?
thx for any hints

[Dmytro Chernysh]

A famous NP-complete problem... So, it can be solved only using backtracking.
Mail me, and I'll give you input/output file using my AC-solution.

[Almost Human]

I got WA on this problem ...

I wonder where I could be wrong ? please help ...

[yiuyuho]

did not find the correct minimum.

a greedy approach will fail if that's what you're trying.

[Almost Human]

Thank you for your reply, yiuyuho. I've finally got AC.

However, I didn't use greedy method, I made a silly mistake.

[dhyanesh]

Hi

Can someone provide input output for 140 bandwidth .. I am stuck on it using a backtracking solution.

-Dhyanesh

[dhyanesh]

never mind ... i got AC .. a stupid mistake !

[geran]

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.

[geran]

nevermind, I found it, I had reserved to little memory for the input line ...

[soddy]

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

[Jan]

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

[hi!man!]

I got several WAs, anyone check these i/o?
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
#

My 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 E D F G H -> 2
A B H C E G D F -> 3
A B C D E F G H -> 7

EDIT: after Jan answered my problem, I noticed I had a wrong input, sorry for that.

[Jan]

My accepted code returns.

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

Hope these help.

[hi!man!]

thank you, I got AC
still a silly mistake.

[iit2006015]

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");
}