The Caribbean salesman

[admin]

Bob is a salesman in the Caribbean islands. While he is sunbathing on the white sand beach or admiring the emerald sea while slurping a Rhum cocktail, Bob uses this relaxing time to plan for his trip to visit his customers.

Read

[Alexey Solodovnikov]

Uff, the last testcase (test_30_150) is pretty hard, IMHO Only two guys have passed it.

[davidb]

Actually it really depends on your algorithm, the last test case isn't the most time consuming if you look at the actual submission reports. But yeah, that's a difficult problem for sure and getting the right algorithm is key.

[Alexey Solodovnikov]

Indeed I have two different approaches for sparse and dense graphs, the dense graph version should be more optimized. Here is my java submission result that fails on the last testcase only. Could you please upload your version?

the.caribbean.salesman.png (49.85 KiB) Viewed 1888 times

PS. If someone needs more than 100 testcases, grab them here:
http://facebook-puzzles-testcases.googl ... ebulll.zip

[davidb]

My Python submission results:
http://codercharts.com/submission/233

My C++ submission results (slightly different algo, I didn't optimize it as much as the python one):
http://codercharts.com/submission/272

You'll have to be logged in to see the reports. Just as a small hint, I use a single algo regardless of whether the graph is dense or sparse.

[Alexey Solodovnikov]

Thanks! Great result indeed, will try to rewrite my algo - already have ideas

[gonzzas]

Hi all,

I have a question regarding this problem. In the problem specification there is never mentioned if Bob must return (or not) to the starting point, so I initially assumed that Bob doesn't need to end where he started.

But after looking at the example, it looks like my initial assumption is wrong and Bob in fact needs to return to the initial point.

Because if Bob doesn't need to end where he started, he can travel through all islands with only the following tickets (at least one of the possibilities):

1 2 4 5 6 7 with the cost of 150.

So - just to clarify - Bob needs in fact to end in the same island where he started right?

Thank you all.

Regards
gonzzas

[Alexey Solodovnikov]

So - just to clarify - Bob needs in fact to end in the same island where he started right?

Yep. It should be the cycle or few cycles but all connected. Consider the following important testcase:

1 C0 C1 619
2 C0 C2 837
3 C0 C3 765
4 C1 C0 850
5 C1 C2 69
6 C1 C3 106
7 C2 C0 1
8 C2 C1 841
9 C2 C3 877
10 C3 C0 117
11 C3 C1 580
12 C3 C2 873

The right result should be

912
1 5 6 7 10

PS. Original problem is here: http://www.facebook.com/careers/puzzles.php?puzzle_id=1
PPS. A lot of testcases are here: http://facebook-puzzles-testcases.googl ... ebulll.zip