10052 - Inviting Politicians

[uzioriluzan]

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]

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

[Adil]

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]

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

[wyvmak]

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]

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

[windows2k]

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

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]

[LittleJohn]

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]

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.

[..]

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.

[Per]

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

[..]

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?

[Per]

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]

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.