140

.. · Post by .. » Wed Jan 02, 2002 8:10 pm

I solve 140(Bandwidth) by permutating all pattern and calculate the bandwidth.
But I think this is really slow, can anyone tell me the quick algorithm to solve 140?
Thanks a lot!

chrismoh · Post by **chrismoh** » Thu Jan 03, 2002 11:51 pm

Unfortunately, there is no quick solution to this problem.

Backtracking with good cutoffs is probably efficient enough.

ftomi · Post by **ftomi** » Fri Feb 01, 2002 2:07 pm

Is there any trick in this problem? I should generate all the permutation, and select that one with the minimum bandwith what is the first in lexicaly oreder. But why my program gets WA? Because of the blank graphs/lines? What sould I print if there is one?
-> 0
Is it ok?

Lawrence · Post by **Lawrence** » Sat Feb 23, 2002 3:56 pm

How fast would you want? My complete search algorithm only runs 0.47 sec, this is enough for me.

C8H10N4O2 · Post by **C8H10N4O2** » Wed Apr 17, 2002 11:02 pm

I permutate and then check the bandwidth. It takes forever since my bandwidth checker is O(26^2). Any ideas on how to check bandwidth faster?

Stefan Pochmann · Post by **Stefan Pochmann** » Thu Apr 18, 2002 2:16 am

Well, the first thing to do is to go down to O(8^2) by renaming the nodes to A,B,C,... consecutively. Then, you can gain some speedup if you build the permutations recursively and while building them already partly calculate the bandwith. Of course this also works in the iterative version, but only if you do it yourself rather than to rely on next_permutation of the STL.

If you want it really fast, you should have a look at the programs Skiena mentions in his book. Reportedly you can solve cases with 30 nodes in about a second or a minute, I don't remember.

C8H10N4O2 · Post by **C8H10N4O2** » Thu Apr 18, 2002 10:38 am

You mean the Algorithm Design Manual? I will check it out when I get back from Cali. Thanks for the tip.

Stefan Pochmann · Post by **Stefan Pochmann** » Thu Apr 18, 2002 11:33 am

Yes, that's the one I meant. You can get a small part of it here:
http://www.cs.sunysb.edu/~algorith/file ... idth.shtml

You can also find two implementations of solutions there, I believe from his students. And at least one of them contains a little documentation of the used algorithm somewhere.

C8H10N4O2 · Post by **C8H10N4O2** » Mon Apr 22, 2002 1:02 am

Just to clarify, I have the book and have read it several times. I was trying to devise a novel algorithm:P

titid_gede · Post by **titid_gede** » Mon Apr 21, 2003 5:21 pm

is sample output for problem 140 correct? or just only to show the right output format? i was curios since (correspond to sample input) node F is not adjacent of node C, but the sample output gives F after C.
thank you very much.

turuthok · Post by **turuthok** » Mon Apr 21, 2003 9:40 pm

Titid, ... you misunderstood the problem. The sample output is correct. You're asked to print the optimal ordering of the nodes, ... you need to understand the pictures that describe ABCDEHGF and ABCDGFHE orderings ...

-turuthok-

titid_gede · Post by **titid_gede** » Tue Apr 22, 2003 5:26 pm

aha, I see, yes i misunderstood the problem, i got AC, thank you pak haryanto.

ivec · Post by **ivec** » Sat Jun 28, 2003 12:42 am

I had no luck on this one so far... first problem I seem to stumble on.
What would be a good approach?

Googling lead me to consider some "cuthill-mckee" algorithm, but I haven't been able to find a description of that algorithm online. Does anyone have such a description ?
Also, I'm not sure if the algorithm can easily find the lexicographically smallest solution.

So, at this stage, I would really be thankful for any links to some reference and/or hints towards a working approach.

TIA! -- Ivan

junjieliang · Post by **junjieliang** » Sun Jun 29, 2003 5:53 am

I think this problem is NP... so your best hope is brute-force with some pruning...

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

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

OJ Board

140 - Bandwidth

140 - bandwith

140 - Bandwidth