Page **1** of **1**

### 10319 - Manhattan

Posted: **Sat Jul 06, 2002 2:39 pm**

by **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?

### Re: 10319 - Manhattan

Posted: **Sat Jul 06, 2002 5:31 pm**

by **Joe Smith**

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

Posted: **Sun Jul 07, 2002 1:12 am**

by **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

Posted: **Thu Jul 18, 2002 2:06 pm**

by **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?

Posted: **Sun Jul 21, 2002 11:36 pm**

by **Joe Smith**

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?

Posted: **Mon Jul 22, 2002 1:40 am**

by **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.

### Exponential solution worked in 0.01

Posted: **Mon Oct 07, 2002 9:06 pm**

by **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.

### Re: 10319 - Manhattan

Posted: **Sun Dec 07, 2003 6:26 pm**

by **Ken Lin**

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?

### 10319

Posted: **Fri Jun 30, 2006 11:40 am**

by **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?

Posted: **Wed Sep 05, 2007 2:00 pm**

by **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
```

[edit] accepted.