|
|
| Show all threads Hide all threads Show all messages Hide all messages | | how to solve | Denis | 1614. National Project “Trams” | 17 Jun 2021 22:24 | 18 | is it possible to solve this problem with "smart" backtracking algo using a lot of restrictions ? As I know YES.
But there easy and beautiful math solution. give me a hint how to solve it without using backtracking algorithm
thank you Please send it to me too.
eros_89@yandex.ru About math solution.. I am trying to it by the following way:
Assume a connection between stops A and B. Then connection from B to A exists too. Then, to satisfy the problem's conditions, we have to introduce (2*n-1)*n connections (ordered in such a way that each tram route has 2*n-1 connections). All the connections are distinct.
Next, each tram stop has exactly 2*n-1 connections to other distinct stops. It is always odd integer, so every tram stop must appear exactly once at the beginning of single route, and next time it must appear (2*n-2)/2=n-1 times in the middle of other routes. It is true for all the routes.
So first we should build the following answer matrix if we consider n = 3:
1 x x x x 4
2 x x x x 5
3 x x x x 6
Then I am trying to place other elements to the matrix according to some placement rules from the thoughts above, but I am still unable to come up with a good solution.
Could someone point out, am I going correct in my math thoughts or such approach leads to naive backtracking solution? Thanks!
Sorry I was so verbose :D No more math is needed. Now you can use backtracking. I resisted the idea of writing a backtracking algo, but decided to implement it with rule of placing elements leftmost and outermost as you suggested and got AC :) Thank you.
PS. I wonder if it is possible to write a backtracking solution without any initial placements or not.
2 Chmel_Tolstiy: Could you please give me small hint about a math solution? master.wsd064 (no spam) gmail.com
Edited by author 03.04.2008 18:27 your Idea is a 2/3 of all way. just try to find a regularity between this paths. I think it's easy. naxart[at]yandex[dot]ru
it's my email. I've found simple maths solution, here is my solution for n=3
1 2 3 4 5 6
2 4 6 1 3 5
3 6 2 5 1 4
Edited by author 02.06.2008 05:28
Edited by author 02.06.2008 05:28 There is no need for _smart_ backtracking. I placed 1..n on the left side and n..2n on the right side. Then I launched recursion over all cells row-by-row, column-by-column, taking every edge (i;j) exactly once, and it's AC in 0.078 sec.
For n=100 there occurs only 562 returns. So, it's almost greedy algo.
The only problem was expanding that recursion into a loop 'cuz I had stack overflow with 200x100 calls.
Edited by author 25.07.2008 17:31 Continue filling the matrix from both left and right.
Keep each pair of opposite columns contain every tram stops. I want to know too.
pkkj@tom.com
Thanks.
Only math solution acceptable
because this is structure design problem.
I spent a lot of time but was unable to find it.
Solution easy to find in internet with key words
"decomposing complete graph in hamilton paths"
Use diameters and walk left-rigth- down with respect to them.
Edited by author 14.08.2009 11:02 no subject
Edited by author 14.08.2009 11:03 | | for n=4 ? | puella | 1614. National Project “Trams” | 19 Jul 2008 00:53 | 2 | 1 2 3 1 4 2 5 8
2 6 1 5 3 4 5 7
3 6 4 7 1 8 7 6
4 8 2 7 3 8 6 5 | | What does this problem mean? | Shu Tianmin | 1614. National Project “Trams” | 6 Apr 2008 12:16 | 1 | I can't understand what this problem means?
Who can help me to explain it?
Thinks a lot! | | graph | enick | 1614. National Project “Trams” | 30 Mar 2008 18:03 | 1 | graph enick 30 Mar 2008 18:03 ways in graph,and no more...
Edited by author 30.03.2008 18:03 |
|
|
|
