10319 - Manhattan

[Shih-Chia Cheng]

I try to formulate this problem as a two-coloring 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 two-colorable.
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?

[Joe Smith]

I try to formulate this problem as a two-coloring 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 two-colorable.
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?

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.

Any better formulation for this problem?

I think 2-SAT should work...

[Shih-Chia Cheng]

Yeah! I think you are right.
This problem can be formulated as a 2-SAT problem
and use dynamic programming to solve it. Thanx

[dh3014]

I'm working with this problem now.
I did use method similar with 2-SAT 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?

[Joe Smith]

I'm working with this problem now.
I did use method similar with 2-SAT 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?

I can't get my 2-SAT solution to work either. I am sure the 2-SAT 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 "2-SAT and SCC"... I don't understand why one would need to use SCC. Is there something wrong with my approach?

[Adrian Kuegel]

What about s1 == s2 or a1 == a2? Then you also have to add some edges to the graph. First I forgot that, too.

[scythe]

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.

[Ken Lin]

I try to formulate this problem as a two-coloring 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 two-colorable.
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?

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.

Any better formulation for this problem?

I think 2-SAT should work...

How to solve a 2-cnf-sat problem?

[ahpc.Sad]

I know it can be formulated as a 2-SAT problem, but It seems a little different with the typical 2-SAT problem. Can someone give me a solution?

[tobby]

I try brute force backtracking but I get WA. Does anyone have any good test cases? Thank you.

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

[edit] accepted.