## 10052 - Inviting Politicians

Moderator: Board moderators

### 10052 - Inviting Politicians

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!
uzioriluzan
New poster

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

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)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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

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

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)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

### judge is wrong

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!
wyvmak
Experienced poster

Posts: 110
Joined: Thu Dec 13, 2001 2:00 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)
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

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.

Could you give me an example?
windows2k
Experienced poster

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

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][i] == 1)
{
group[i][count[i]++] = me;
for(j = 0; j < degree[me]; j++)
available[graph[me][j]][i]--;
if(backtrack(no+1))
return 1;
for(j = 0; j < degree[me]; j++)
available[graph[me][j]][i]++;
count[i]--;
}
marked[me] = 0;
return 0;
}[/c]
JongMan @ Yonsei
Whinii F.
Experienced poster

Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea

### Re: judge is wrong

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.
LittleJohn
Learning poster

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

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.

Where's the "Any" key?
Solaris
Learning poster

Posts: 99
Joined: Sun Apr 06, 2003 5:53 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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.
..
A great helper

Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

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.
Per
A great helper

Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

### Re: 10052 - Inviting Politicians

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

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

Next