Page 1 of 1

11095 - Tabriz City

Posted: Thu Sep 21, 2006 10:06 pm
by joeluchoa
Is it possible to solve this problem with graph coloring(two colors)???
I've used this and got WA!!

Posted: Thu Sep 21, 2006 11:04 pm
by smile2ka10
no it is not bicoloring!
It is vertex cover problem.

Posted: Fri Sep 22, 2006 6:38 am
by Ferdous
I think it would have been a bicoloring problem if the constraint was "If a junction has a tourist information centre, no adjacent junction can have another one" instead of "at least one of two junctions at the end of each street have a tourist information center"

Posted: Fri Sep 22, 2006 4:08 pm
by arsalan_mousavian
try this input

Code: Select all

1
15
20
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 3
6 3
6 4
8 9
9 10 
10 11
11 12
11 13
12 13
13 14
8 14
8 11
9 14
the answer should be:

Code: Select all

Case #1: 8
1 3 5 6 9 11 13 14
hope it helps

Posted: Sat Sep 23, 2006 12:09 am
by joeluchoa
Ok, AC now!!
Thanks

Posted: Sun Sep 24, 2006 2:15 am
by fernando
After i have read what vertex cover problem is, i agree this problem asks for the vertex cover, but how can you compute it?, specially when this is a NP problem whit n=30, do you have to make some kind of backtracking with pruning or something like that?, thanks in advance

Posted: Tue Sep 26, 2006 1:36 pm
by mamun
Probably I haven't understood the problem clearly. Aren't we supposed to find the minimum number of information centers needed to form so that all the junctions have a center either at it or adjacent to it?

If so, for the graph posted by arsalan_mousavian 6 centers should be enough, I think. Don't 1 3 5 8 10 12 take care of all the junctions?

Posted: Tue Sep 26, 2006 2:12 pm
by Hisoka
He wants to do this in a way that at least one of two junctions at the end of each street have a tourist information center

Posted: Tue Sep 26, 2006 8:10 pm
by mamun
So it's the streets that must ensure that at least one end has a center. Yes, my previous assumption would have missed streets (4 6) and some more. Thank you Hisoka.

Posted: Tue Sep 26, 2006 8:14 pm
by Vexorian
It is NP complete but the input size is quite small. BTW, if you read the graph as an array of edges the solution is kind of straight forward

Help Needed...

Posted: Fri Jun 01, 2007 6:44 pm
by nymo
What kind of optimization do you do in this problem? I have represented the graph using adjacency matrix; I am using bit field for marking... I am getting TLE, the code is basically a bruteforce search ... I select a node, mark all edges incident to it and then try other nodes, after returing from other nodes I simpy unmark the edges and try starting with other nodes... Can you share some of your tricks??? Thanks.

Posted: Mon Jun 04, 2007 11:15 pm
by MIB
thanks to Vexorian... I got accepted easily by reading the graph as an array of edges... :D

the solution is obviously brute force search...
nymo, The only optimization that I did, was: whenever I decided not to take a vertex as an information centre, I marked all the adjacent vertices as taken. Hope it will help...

getting WA now...

Posted: Tue Jun 05, 2007 10:35 am
by nymo
Thanks to MIB and Vexorian, I am now getting WAs... I try some test cases... they are okay. Can someone post some more test cases???
Thanks.

Posted: Wed Jun 06, 2007 5:49 pm
by nymo
Thanks MIB. I 've got ACC :D

Posted: Thu Jun 14, 2007 11:02 pm
by okz
help me plz...
i use the approach of computing the nodes combination from small to large
in another word,try taking all possible 1 node and test ,then try taking 2 nodes combination,then 3...and more
but it become very slow after 8 nodes combination
i just got lots of TLE in online-judge...
plz tell me how should i design the brute force approach
will it be better if i use binary searching?
thx.