## 10319 - Manhattan

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Shih-Chia Cheng
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 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
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

### Re: 10319 - Manhattan

Shih-Chia Cheng wrote: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
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:
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
New poster
Posts: 26
Joined: Wed Apr 17, 2002 5:56 am
dh3014 wrote: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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
What about s1 == s2 or a1 == a2? Then you also have to add some edges to the graph. First I forgot that, too.

scythe
New poster
Posts: 12
Joined: Mon Oct 07, 2002 12:25 pm

### 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.

Ken Lin
New poster
Posts: 1
Joined: Sun Dec 07, 2003 6:18 pm
Location: Taiwan

### Re: 10319 - Manhattan

Joe Smith wrote:
Shih-Chia Cheng wrote: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
New poster
Posts: 2
Joined: Fri Jun 23, 2006 3:33 pm
Contact:

### 10319

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?
Happy every day!

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
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``````
 accepted.