10052  Inviting Politicians
Moderator: Board moderators

 New poster
 Posts: 27
 Joined: Thu Feb 14, 2002 2:00 am
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!
Anyone could help? Does anyone know interesting input or where I could find them?
Txs a lot!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

 Learning poster
 Posts: 57
 Joined: Sun Sep 29, 2002 12:00 pm
 Location: in front of the monitor :)
 Contact:
hello. this is how i solved the prob:
hope this helps.
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

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
judge is wrong
I wanna say something.
first, the judge is wrong.
actually i think this is an NPcomplete 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!
first, the judge is wrong.
actually i think this is an NPcomplete 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!

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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 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)
Born from ashes  restarting counter of problems (800+ solved problems)
I don't realize your methodAdil wrote:hello. this is how i solved the prob:
hope this helps.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
Could you give me an example?

 Experienced poster
 Posts: 151
 Joined: Wed Aug 21, 2002 12:07 am
 Location: Seoul, Korea
 Contact:
I also tackled this problem with backtracking (I believe this problem is NPcomplete, 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]
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

 Learning poster
 Posts: 83
 Joined: Wed Feb 27, 2002 2:00 am
 Location: Taiwan
Re: judge is wrong
I think the judge's special correction program goes wrong somewhere, too.wyvmak wrote:I wanna say something.
first, the judge is wrong.
actually i think this is an NPcomplete 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!
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.

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
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.
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?
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 4color a planar graph. But I can't find any algorithm to color a 4colorable 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.
Yes, I know given a general graph, finding the minimum number to color it is NPC. But if we are given that the graph is kcolorable, is kcoloring it still NPC?
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.
Yes.
If you are given a graph G which you are not sure is kcolorable, you can send it to your kcoloring algorithm A which works given that G is kcolorable. If G really is kcolorable, A will succeed (and you have successfully determined that G is kcolorable, without knowing so from the beginning), otherwise it will fail no matter what (and you have successfully determined that G is not kcolorable).
The guarantee that the input graph is not 3colorable doesn't make the problem easier (in the sense of being nonNPcomplete) either, which you can assure yourself of by a similar trick: simply add K_4 to the graph.
If you are given a graph G which you are not sure is kcolorable, you can send it to your kcoloring algorithm A which works given that G is kcolorable. If G really is kcolorable, A will succeed (and you have successfully determined that G is kcolorable, without knowing so from the beginning), otherwise it will fail no matter what (and you have successfully determined that G is not kcolorable).
The guarantee that the input graph is not 3colorable doesn't make the problem easier (in the sense of being nonNPcomplete) either, which you can assure yourself of by a similar trick: simply add K_4 to the graph.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
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:
Given that this is a NPcomplete 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.
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
Check input and AC output for thousands of problems on uDebug!