11095 - Tabriz City

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

Moderator: Board moderators

Post Reply
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

11095 - Tabriz City

Post by joeluchoa »

Is it possible to solve this problem with graph coloring(two colors)???
I've used this and got WA!!
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

smile2ka10
New poster
Posts: 13
Joined: Wed Oct 26, 2005 10:14 pm
Location: Iran
Contact:

Post by smile2ka10 »

no it is not bicoloring!
It is vertex cover problem.

Ferdous
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

Post 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"
I am destined to live on this cruel world........

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post 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
In being unlucky I have the record.

joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa »

Ok, AC now!!
Thanks
http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

fernando
New poster
Posts: 21
Joined: Sat Mar 18, 2006 8:21 pm

Post 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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post 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?

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post 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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post 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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Help Needed...

Post 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.
regards,
nymo

MIB
New poster
Posts: 3
Joined: Tue Apr 08, 2003 10:39 am
Location: Dhaka, Bangladesh

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

getting WA now...

Post 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.
regards,
nymo

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Post by nymo »

Thanks MIB. I 've got ACC :D
regards,
nymo

okz
New poster
Posts: 3
Joined: Fri May 25, 2007 3:54 am

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

Post Reply

Return to “Volume 110 (11000-11099)”