10984 - Double NP-hard

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

Moderator: Board moderators

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

10984 - Double NP-hard

Post by Monsoon » Sun Jan 22, 2006 5:09 pm

Hi,

could someone give some test cases, i don't know what i'm doing wrong :-?

thanks

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 22, 2006 5:22 pm

Try this:

Code: Select all

2
6 4
1 2
1 3
5 4
5 6
6 5
1 2
1 3
1 5
5 4
5 6
Correct output is: (edited to make it correct)
Case #1: Impossible
Case #2: Impossible
Last edited by Adrian Kuegel on Sun Jan 22, 2006 6:11 pm, edited 2 times in total.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Sun Jan 22, 2006 5:38 pm

hmm, possible i missunderstood something, but second test is something like this:
__3
|
1--2
|
5--4
|
6

so maximum independent set is {2,3,4,6} and minimum vertex cover is {1,5}, so answer is impossible?

Am i rigth? Or simple so stupid that i haven't understood this task?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jan 22, 2006 5:42 pm

-- Post removed by Observer --
Last edited by Observer on Sun Jan 22, 2006 5:58 pm, edited 1 time in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 22, 2006 5:53 pm

Actually, it seems my program is wrong.
I agree the largest independant set for the second test case should be {2, 3, 4, 6}, and minimum vertex cover {1,5}.
I wonder why I got Accepted.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sun Jan 22, 2006 5:57 pm

Hmm... probably the problemsetter has mistaken "maximum" as "maximal" then.. or maybe the test cases are just too simple ?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Jan 22, 2006 6:07 pm

Edit: spoiler removed
Last edited by Adrian Kuegel on Mon Jan 23, 2006 12:25 am, edited 1 time in total.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Sun Jan 22, 2006 6:15 pm

exactly i do the same ;) and i'm sure that this is correct algo


(***cut after acc***)

edit:
almost sure :D
Last edited by Monsoon on Sun Jan 22, 2006 8:54 pm, edited 1 time in total.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Jan 22, 2006 6:34 pm

This problem is wrong. I'll fix it today.

Actually, just so that I don't screw it up again, Adrian or Monsoon, could you send me your solution please? (abednego at gmail)

igor
If only I had as much free time as I did in college...

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Thu Jan 26, 2006 10:21 am

pls anyone give some hits to solve this problem.

Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon » Thu Jan 26, 2006 3:00 pm

one hint: think what is when graph is bipartite and what is when it's not

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Fri Jan 27, 2006 4:31 pm

Monsoon wrote:one hint: think what is when graph is bipartite and what is when it's not
thx for the hit. i already think that. But if the given graph is bipartite, then it's not sure that there is an answer. am i right ? Now tell me :

1. if the total node is odd, then its "Impossible".
2. if the graph is bipartite and the given graph has an answer, then the output will be left part of the bipartite graph(i.e which part contais 1st node).

Am i right ?

Now tell me abt the minimum vertex cover portion. what's the way to handle this part ? A graph has no answer if not bipartite or it's minimum vetex set size != total node / 2. right ?

hope u get my problem.
pls help.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Fri Jan 27, 2006 4:49 pm

You are right.
For minimum vertex cover, there exists an efficient algorithm if the graph is bipartite (which you can check first). Hint: Think about how you can find a lower bound for the minimum number of nodes in the vertex cover (it turns out, if you find the right lower bound, that it is in fact the solution).
I guess, that the algorithm is also mentioned in some books about graph theory.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Jan 27, 2006 6:52 pm

Hmm. 1 Accepted and 34 Presentation Errors. Could it be that the judge has the wrong format? I'm (almost) sure my output is correctly formatted, but it's one of the 34.
No big deal, just want to mention it.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Jan 27, 2006 10:51 pm

I had the same problem with presentation error, I don't know what's wrong, but definitely there's some problem with the judge's output format. I'm sure mine is correct.

Post Reply

Return to “Volume 109 (10900-10999)”