DIFFICULTY: PREREQUISITES: PROBLEM: QUICK EXPLANATION: EXPLANATION: For Subtask #1 and #2: For Subtask #3: We can improve this by using a 'HashSet' or a hash function to design the adjacency list, so that any insertion or deletion can be carried out in O(1) time complexity. 40pts Solution (With 'HashSet' in graph representation)) ALTERNATIVE APPROACH: This is my first editorial. Please do comment, and point out any error you find. asked 21 Jul '18, 15:51

What is the implication of this statement mentioned in problem: answered 21 Jul '18, 22:10
I cant actually prove its optimality,but its quite hard to find a countercase for this approach.
(21 Jul '18, 22:23)
1
here's a countercase for non chordal graph: 1 5 7 1 2 2 3 3 4 4 5 5 1 2 4 3 5 expected output:4 His output:3
(21 Jul '18, 22:29)
You can corner Jerry with 3 cats. J: 1, C: (2, 1, 5) Jerry is always cornered.
(21 Jul '18, 22:46)
The cat makes the first move(thats what made the question hard :) ,as jerry can think what to do based on cats move): So if C:(2,1,5),then J:3 Similarly other cases also
(21 Jul '18, 22:52)
proof: the answer for visible cops and robber game for graph G is treewidth+1 which is min(maximum clique among all chordal completion of G) Now the minimum value of maximum clique is obtained upon adding edge 25(best chordal completion graph of G). And now for modified graph ,max clique size is 4(2345)
(21 Jul '18, 23:04)
Wait wait, I just showed that any of the vertex is unsafe for Jerry. I couldn't get you. Even if the cats choose first, I can't see any escape route for Jerry. C: (2, 1, 5), then J: 3, C: (3, 4, 5), J: 2, C: (3, 4, 2), J: 1, C: (2, 1, 5)
(21 Jul '18, 23:43)
1
When cat went for (3,4,2),Jerry could have gone to 5,making it same as the case C:(3,4,5),J:2
(22 Jul '18, 00:14)
Yes, my mistake... Sorry.
(22 Jul '18, 11:44)
showing 5 of 8
show all

Great Editorial !
I think you should just mention the fact that this problem was also equivalent to finding the maximum chordal clique in the graph. For this implementation you can have a look at this solution.
Thanks!
Wow!!
If possible can u prove that this strategy always yields the correct ans?
Cause this strategy doesn't takes the benefit of graph being chordal,which means it could be applied on any graph,but since its an NPC problem for normal graphs
does it mean u solved an NPC problem ,:) XD
Thanks for your feedback.
@pieliedie I'm mentioning it, but I practically have no idea what a 'chordal' graph or a 'clique' is. I think, it'll be better if you prove the equivalence in the 'comment' or 'answer' section.
@vivek_1998299 Thanks a lot.:) But, I think, this solution will work only for chordal graphs. I feel, there exists some graph, in which you can approach strategically with less cats and force Jerry to a particular vertex. Maybe, you need a complicated DP, or maybe it's an unsolvable one.;)