|
|
If the test is: 4 6 1 2 1 3 1 4 2 3 2 4 3 4 then all created routes are as follows: 1 - 2 - 3 - 1 1 - 2 - 4 - 1 1 - 3 - 4 - 1 2 - 3 - 4 - 2 1 - 2 - 3 - 4 - 1 1 - 2 - 4 - 3 - 1 1 - 3 - 2 - 4 - 1 Am I right? Indeed I was right, the answer for this test is 6. Can this problem be solved faster than in O(2^n * n^3)? Thanks to authors And what's cool here? IMHO, quite standard DP. Don't understand, why so few authors have solved it... It was cool in finding proper layout (for me at least). Of course, counting routes was trivial. Problem is very difficult. I think that answer is maximal cycles degree of vertices, or maxilal number of cycles containing some vertex. All Right but max lengs of cycles must be used also. Test: 14 91 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 2 14 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3 11 3 12 3 13 3 14 4 5 4 6 4 7 4 8 4 9 4 10 4 11 4 12 4 13 4 14 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 7 8 7 9 7 10 7 11 7 12 7 13 7 14 8 9 8 10 8 11 8 12 8 13 8 14 9 10 9 11 9 12 9 13 9 14 10 11 10 12 10 13 10 14 11 12 11 13 11 14 12 13 12 14 13 14 Answ: 8463398736 Indeed, very cool problem when trying to prove it. 5 10 1 2 2 3 1 3 1 4 3 4 2 4 5 1 5 2 5 3 5 4 Answer for this test is 30 More informating test :K14- complete graph. It seems that answer is very big. Edited by author 31.08.2008 10:59 Does the first test to the problem coincide with the sample? Edited by author 22.03.2008 14:28 Yes. This is my stupid bug. AC now... |
|
|