10319  Manhattan
Moderator: Board moderators

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
10319  Manhattan
I try to formulate this problem as a twocoloring problem.
My idea is that I treat each pair of input point as a single node.
And for each pair of node, if their desired paths may conflict, they are
joined by an edge. Then I just check this graph to see if it is twocolorable.
But this idea seems not to work...since there are many cases of relation between a pair of nodes described above. Is my idea totally wrong?
Any better formulation for this problem?
My idea is that I treat each pair of input point as a single node.
And for each pair of node, if their desired paths may conflict, they are
joined by an edge. Then I just check this graph to see if it is twocolorable.
But this idea seems not to work...since there are many cases of relation between a pair of nodes described above. Is my idea totally wrong?
Any better formulation for this problem?
Re: 10319  Manhattan
That won't work, because as you say, there are two paths for each pair, and many pairs, so it's possible that you have 3 pairs where for any 2 of those there's a way to avoid a conflict, but then that choice conflicts with the 3rd pair.ShihChia Cheng wrote:I try to formulate this problem as a twocoloring problem.
My idea is that I treat each pair of input point as a single node.
And for each pair of node, if their desired paths may conflict, they are
joined by an edge. Then I just check this graph to see if it is twocolorable.
But this idea seems not to work...since there are many cases of relation between a pair of nodes described above. Is my idea totally wrong?
I think 2SAT should work...Any better formulation for this problem?

 New poster
 Posts: 17
 Joined: Fri May 24, 2002 4:24 am
 Location: Taiwan
 Contact:
I'm working with this problem now.
I did use method similar with 2SAT problem,
I first construct a graph use following way:
Let each street and each avenue be two vertecies, one means the positive direction and the other means the negative direction. And then for each route (s1, a1, s2, a2), if s1 != s2 and a1 != a2 then I'll add eight edges into the graph:
[c]
if (s2 > s1) {
graph[NEGATIVE(a2)][POSITIVE(a1)] = graph[NEGATIVE(a1)][POSITIVE(a2)] = 1;
if (a2 > a1)
graph[NEGATIVE(a2)][POSITIVE(s2)] = graph[NEGATIVE(a1)][POSITIVE (s1)] = 1;
else if (a1 > a2)
graph[NEGATIVE(a2)][NEGATIVE(s2)] = graph[NEGATIVE(a1)][NEGATIVE (s1)] = 1;
}
else if (s1 > s2) {
graph[POSITIVE(a2)][NEGATIVE(a1)] = graph[POSITIVE(a1)][NEGATIVE(a2)] = 1;
if (a2 > a1)
graph[POSITIVE(a2)][POSITIVE(s2)] = graph[POSITIVE(a1)][POSITIVE (s1)] = 1;
else if (a1 > a2)
graph[POSITIVE(a2)][NEGATIVE(s2)] = graph[POSITIVE(a1)][NEGATIVE (s1)] = 1;
}
if (a2 > a1) {
graph[NEGATIVE(s2)][POSITIVE(s1)] = graph[NEGATIVE(s1)][POSITIVE (s2)] = 1;
if (s2 > s1)
graph[NEGATIVE(s2)][POSITIVE(a2)] = graph[NEGATIVE(s1)][POSITIVE(a1)] = 1;
else if (s1 > s2)
graph[NEGATIVE(s2)][NEGATIVE(a2)] = graph[NEGATIVE(s1)][NEGATIVE(a1)] = 1;
}
else if (a1 > a2) {
graph[POSITIVE(s2)][NEGATIVE(s1)] = graph[POSITIVE(s1)][POSITIVE (s2)] = 1;
if (s2 > s1)
graph[POSITIVE(s2)][POSITIVE(a2)] = graph[POSITIVE(s1)][POSITIVE(a1)] = 1;
else if (s1 > s2)
graph[POSITIVE(s2)][NEGATIVE(a2)] = graph[POSITIVE(s1)][NEGATIVE(a1)] = 1;
}
[/c]
after that, I'll compute all reachbillity for all pair (i, j)
then the final process is just to check whether each route
can be assigned without any contridictions, if no contridiction occurs, print "Yes", otherwise, print "No".
But I got WA several times with the above algorithm..
may anyone give me some hints about this problem?
I did use method similar with 2SAT problem,
I first construct a graph use following way:
Let each street and each avenue be two vertecies, one means the positive direction and the other means the negative direction. And then for each route (s1, a1, s2, a2), if s1 != s2 and a1 != a2 then I'll add eight edges into the graph:
[c]
if (s2 > s1) {
graph[NEGATIVE(a2)][POSITIVE(a1)] = graph[NEGATIVE(a1)][POSITIVE(a2)] = 1;
if (a2 > a1)
graph[NEGATIVE(a2)][POSITIVE(s2)] = graph[NEGATIVE(a1)][POSITIVE (s1)] = 1;
else if (a1 > a2)
graph[NEGATIVE(a2)][NEGATIVE(s2)] = graph[NEGATIVE(a1)][NEGATIVE (s1)] = 1;
}
else if (s1 > s2) {
graph[POSITIVE(a2)][NEGATIVE(a1)] = graph[POSITIVE(a1)][NEGATIVE(a2)] = 1;
if (a2 > a1)
graph[POSITIVE(a2)][POSITIVE(s2)] = graph[POSITIVE(a1)][POSITIVE (s1)] = 1;
else if (a1 > a2)
graph[POSITIVE(a2)][NEGATIVE(s2)] = graph[POSITIVE(a1)][NEGATIVE (s1)] = 1;
}
if (a2 > a1) {
graph[NEGATIVE(s2)][POSITIVE(s1)] = graph[NEGATIVE(s1)][POSITIVE (s2)] = 1;
if (s2 > s1)
graph[NEGATIVE(s2)][POSITIVE(a2)] = graph[NEGATIVE(s1)][POSITIVE(a1)] = 1;
else if (s1 > s2)
graph[NEGATIVE(s2)][NEGATIVE(a2)] = graph[NEGATIVE(s1)][NEGATIVE(a1)] = 1;
}
else if (a1 > a2) {
graph[POSITIVE(s2)][NEGATIVE(s1)] = graph[POSITIVE(s1)][POSITIVE (s2)] = 1;
if (s2 > s1)
graph[POSITIVE(s2)][POSITIVE(a2)] = graph[POSITIVE(s1)][POSITIVE(a1)] = 1;
else if (s1 > s2)
graph[POSITIVE(s2)][NEGATIVE(a2)] = graph[POSITIVE(s1)][NEGATIVE(a1)] = 1;
}
[/c]
after that, I'll compute all reachbillity for all pair (i, j)
then the final process is just to check whether each route
can be assigned without any contridictions, if no contridiction occurs, print "Yes", otherwise, print "No".
But I got WA several times with the above algorithm..
may anyone give me some hints about this problem?
I can't get my 2SAT solution to work either. I am sure the 2SAT part is correct as I've tested it extensively, and I can't find any test cases that break my solution either. Someone in the ranklist said they used "2SAT and SCC"... I don't understand why one would need to use SCC. Is there something wrong with my approach?dh3014 wrote:I'm working with this problem now.
I did use method similar with 2SAT problem,
(snip)
I first construct a graph use following way:
after that, I'll compute all reachbillity for all pair (i, j)
then the final process is just to check whether each route
can be assigned without any contridictions, if no contridiction occurs, print "Yes", otherwise, print "No".
But I got WA several times with the above algorithm..
may anyone give me some hints about this problem?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Exponential solution worked in 0.01
In my solution, I use two lists for every street/avenue, one for each direction. For example s[1][0] tells me what should i change if i want s1 to go right, and s[1][1] to go left.
For a pair s1,a1  s2, a2, there are two possible routes. If the street/ave of one route will be chosen to be oriented in the wrong way, it is clear that the other route will be chosen, so we know a street's and an avenue's direction for sure. That is how i create the lists (its something like a list of conflicts or something).
Then i start out a 2^60 back, when choosing a direction recursively going through the lists. It worked quite well.
For a pair s1,a1  s2, a2, there are two possible routes. If the street/ave of one route will be chosen to be oriented in the wrong way, it is clear that the other route will be chosen, so we know a street's and an avenue's direction for sure. That is how i create the lists (its something like a list of conflicts or something).
Then i start out a 2^60 back, when choosing a direction recursively going through the lists. It worked quite well.
Re: 10319  Manhattan
How to solve a 2cnfsat problem?Joe Smith wrote:That won't work, because as you say, there are two paths for each pair, and many pairs, so it's possible that you have 3 pairs where for any 2 of those there's a way to avoid a conflict, but then that choice conflicts with the 3rd pair.ShihChia Cheng wrote:I try to formulate this problem as a twocoloring problem.
My idea is that I treat each pair of input point as a single node.
And for each pair of node, if their desired paths may conflict, they are
joined by an edge. Then I just check this graph to see if it is twocolorable.
But this idea seems not to work...since there are many cases of relation between a pair of nodes described above. Is my idea totally wrong?
I think 2SAT should work...Any better formulation for this problem?
10319
I know it can be formulated as a 2SAT problem, but It seems a little different with the typical 2SAT problem. Can someone give me a solution?
Happy every day!
I try brute force backtracking but I get WA. Does anyone have any good test cases? Thank you.
My own cases
[edit] accepted.
My own cases
Code: Select all
2
30 30 10
2 2 1 3
3 3 1 3
5 3 3 3
1 2 4 3
4 1 2 3
4 2 1 3
4 2 5 3
6 1 5 3
2 1 5 3
2 1 1 5
30 30 10
2 2 1 3
3 3 1 3
5 3 3 3
1 2 4 3
4 1 2 3
4 2 1 3
4 2 5 3
6 1 5 3
2 1 5 3
2 1 1 2
Code: Select all
Yes
No