140 - Bandwidth

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dennis
New poster
Posts: 5
Joined: Fri Aug 01, 2003 4:41 am
Contact:

140

Post by dennis » Sun Aug 10, 2003 6:13 am

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

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Sun Aug 10, 2003 6:27 am

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

140 - "Bandwith" - WA - please help

Post by Almost Human » Tue Dec 16, 2003 12:52 pm

I got WA on this problem ...

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

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Fri Dec 19, 2003 7:03 am

did not find the correct minimum.

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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Sat Dec 20, 2003 8:45 am

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

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

dhyanesh
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:28 am

140 bandwidth inputs

Post by dhyanesh » Mon Jul 11, 2005 11:40 pm

Hi

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

-Dhyanesh

dhyanesh
New poster
Posts: 5
Joined: Sat Feb 26, 2005 5:28 am

Post by dhyanesh » Tue Jul 12, 2005 12:43 am

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

geran
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

140 Bandwidth input

Post by geran » Sat Aug 06, 2005 10:28 am

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
New poster
Posts: 13
Joined: Sun Jun 19, 2005 4:36 pm

Post by geran » Sat Aug 06, 2005 10:35 am

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

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Problem 140 Bandwidth

Post by soddy » Wed May 30, 2007 2:28 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed May 30, 2007 8:27 am

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
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Sat Aug 11, 2007 11:06 am

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.
Last edited by hi!man! on Sun Aug 12, 2007 3:07 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Aug 11, 2007 9:30 pm

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.
Ami ekhono shopno dekhi...
HomePage

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm

Post by hi!man! » Sun Aug 12, 2007 3:08 am

thank you, I got AC :)
still a silly mistake.

iit2006015
New poster
Posts: 4
Joined: Fri Jul 18, 2008 9:44 pm

Re: 140 - bandwith

Post by iit2006015 » Thu Apr 16, 2009 9:14 pm

plz somebody help i m keep getting wrong answer , above test cases r running :oops: :oops:

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


Post Reply

Return to “Volume 1 (100-199)”