10052 - Inviting Politicians

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

Moderator: Board moderators

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

10052 - Inviting Politicians

Post by uzioriluzan » Mon Jul 01, 2002 4:22 pm

Is there any trick with this problem? I've put a '\n' character in the last line of the output, is that ok? I've tried to solve it using baktracking but I always get wrong answer after 1 sec. I used the most constrained variable heuristics: ordering of the "nodes" by the number of "edges" so as to reduce the time of execution.

Anyone could help? Does anyone know interesting input or where I could find them?

Txs a lot! :)

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue May 06, 2003 12:11 pm

Could anyone tell me something about this problem ?
I try to solve it in the same way as 10475 (which I've got accepted), but I got WA many times ....
So, is there any special case in input ? Could anyone help me ?

Thanks
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Tue May 06, 2003 9:52 pm

hello. this is how i solved the prob:

Code: Select all

a. make all the politicians available
b. for each of the four days
     1. consider an empty list (L) of politicians for that day.
     2. add the first available politician to L.
     3. for every other available politician, add him/her in L only if s/he is in good terms with all the politicians already in L.
     4. make all the politicians in L unavailable
hope this helps.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed May 07, 2003 7:43 am

I try to do this in the same way (I use similar algorithm - I use DFS to do this). But I got WA ...
Could you look at my code ? I don't know why it's not accepted :(

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

judge is wrong

Post by wyvmak » Thu May 08, 2003 5:56 am

I wanna say something.

first, the judge is wrong.
actually i think this is an NP-complete problem,
but Adil's algorithm works, which is polynomial running time.
i first guess this is just an approximation algorithm,
but, after the algorithm, i verified that it doesn't invite all the politicians!
the judge is wrong, but this incorrect algorithm can be accepted.

second, don't output the line between consecutive cases, at least if i remove that line of code to put the extra line, the difference is WA and PE!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu May 08, 2003 8:48 am

I observe the same:
if I print
CASE 1:
<data>
<empty line>
CASE 2:
...
and so on I got WA, when I remove empty lines I got Acc P.E.

and to wyvmak:
I think that this algorithm is correct . The same result I got using DFS, so I think that it isn't NP problem :). One additional thing, which I must check after doing DFS is when number of groups is less than 4. So time complexity of this problem is, I think, O(N+E) + O(1) => time complexity of DFS :)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Wed Jul 02, 2003 7:54 am

Adil wrote:hello. this is how i solved the prob:

Code: Select all

a. make all the politicians available
b. for each of the four days
     1. consider an empty list (L) of politicians for that day.
     2. add the first available politician to L.
     3. for every other available politician, add him/her in L only if s/he is in good terms with all the politicians already in L.
     4. make all the politicians in L unavailable
hope this helps.
I don't realize your method :(
Could you give me an example?

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Thu Aug 07, 2003 3:29 pm

I also tackled this problem with backtracking (I believe this problem is NP-complete, too) and consistently receiving TLEs.

How can I avoid them? Any efficient branching methods to apply? I'm currently sorting nodes with regard to their degrees and try to assign them the least number available.

Following code is pretty straightforward to explain the algorithm:
[c]int backtrack(int no)
{
int i, j, me = index[no];
if(no >= n) return 1;
marked[me] = 1;
for(i = 0; i < 4; i++)
if(available[me] == 1)
{
group[count++] = me;
for(j = 0; j < degree[me]; j++)
available[graph[me][j]]--;
if(backtrack(no+1))
return 1;
for(j = 0; j < degree[me]; j++)
available[graph[me][j]]++;
count--;
}
marked[me] = 0;
return 0;
}[/c]
JongMan @ Yonsei

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Re: judge is wrong

Post by LittleJohn » Fri Sep 05, 2003 5:23 am

wyvmak wrote:I wanna say something.

first, the judge is wrong.
actually i think this is an NP-complete problem,
but Adil's algorithm works, which is polynomial running time.
i first guess this is just an approximation algorithm,
but, after the algorithm, i verified that it doesn't invite all the politicians!
the judge is wrong, but this incorrect algorithm can be accepted.

second, don't output the line between consecutive cases, at least if i remove that line of code to put the extra line, the difference is WA and PE!
I think the judge's special correction program goes wrong somewhere, too.
Since there're so many people AC, not PE.
But using the algo above we can only get PE.
Maybe we should invite all politicians, not just partial.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Fri Aug 27, 2004 9:03 pm

Its really strange that just the omission of "\n" changes the reply from WA to PE. But many people has got AC too. Can someone tell me how he got AC.

I also used the algorithm specified by Adil and received PE. I have checked that none of my sets were empty.

TO WYVMAK:
I myselft aint sure about the correctness of the algo. Can you post a case where this algo fails. And if it is really NP complete then what can be the soln.

thnx in advance.
Where's the "Any" key?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Sep 24, 2004 10:31 am

Could anyone still get accepted after rejudge tell me, do you assume that the input graph is planar?? I find that there are some good algorithm to 4-color a planar graph. But I can't find any algorithm to color a 4-colorable general graph using 4 colors. :(
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Sep 24, 2004 5:07 pm

That's because there are no efficient algorithms known, the problem is NP-complete.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Sep 24, 2004 5:12 pm

Yes, I know given a general graph, finding the minimum number to color it is NP-C. But if we are given that the graph is k-colorable, is k-coloring it still NP-C?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Fri Sep 24, 2004 5:28 pm

Yes.

If you are given a graph G which you are not sure is k-colorable, you can send it to your k-coloring algorithm A which works given that G is k-colorable. If G really is k-colorable, A will succeed (and you have successfully determined that G is k-colorable, without knowing so from the beginning), otherwise it will fail no matter what (and you have successfully determined that G is not k-colorable).

The guarantee that the input graph is not 3-colorable doesn't make the problem easier (in the sense of being non-NP-complete) either, which you can assure yourself of by a similar trick: simply add K_4 to the graph.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10052 - Inviting Politicians

Post by brianfry713 » Thu Apr 26, 2012 1:05 am

The corrector program has been updated and there was a rejudge, see:
http://acm.uva.es/board/viewtopic.php?t=6394

The algorithm posted by Adil may fail on this input:

Code: Select all

1
6 12
A
B
C
D
E
F
A D
A E
A F
B C
B D
B E
C D
C E
C F
D E
D F
E F
Given that this is a NP-complete problem, how did you solve it? I'm getting TLE. I'm able to assign 4 different initial colors to politicians, and then check for politicians that can have any color, can only have one color, or can have any color but one, and assign a color to them. My recursive backtracking approach to assign the remaining politicians a color takes too long.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”