JERRYTOM - Editorial (Unofficial)

editorial
, , ,
1

PROBLEM LINK
Contest
Practice

DIFFICULTY:
Medium

PRE-REQUISITES:
Graph Representation through Adjacency List.

PROBLEM:
In a given chordal graph, Jerry can start from any vertex and move to any neighbouring vertex throughout the chase. You have to find the minimum number of cats Tom needs, to corner Jerry after a finite number of rounds. Tom can, however, choose any set of vertices, independent of the chosen vertices in the previous rounds.

QUICK EXPLANATION:
Let us assume, the minimum number of cats required to be K. To find K, we can start somewhat in a greedy way. The minimum value of K can be 2. So, we can erase all vertices having degree 1 (because if Jerry lands upon any of these vertices, he is sure to get cornered). If there still exists some vertices, we can conclude, that 2 cats are not enough to catch Jerry. So, we increase K to 3 and repeat the same procedure.

EXPLANATION:

For Subtask #1 and #2:
Proceed in the exact same way, as explained in “QUICK EXPLANATION”.

Click to view
  1. Arrange all the vertices in increasing order of their degree.
  2. Remove all the vertices having the lowest degree, along with their edges.
  3. If there are still any vertex left, go to Step 1.
  4. ‘K’ is 1 + degree of the last removed vertex.

40pts Solution

For Subtask #3:
The most expensive step in the previous algorithm which results in TLE verdict is the step where the list of vertices is sorted. Also, the vertex removal step is quite expensive if done on an ‘ArrayList’ or ‘vector’.

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.
Furthermore, we can improve the ‘sorting’ step by maintaining a ‘TreeSet’, or a ‘PriorityQueue’ (Binary Heap) for lg(N) insertion and deletion. However, the heap needs to be updated after each deletion of the vertices.

40pts Solution (With ‘HashSet’ in graph representation))
100pts Solution (With ‘TreeSet’ for efficient and online sorting).

ALTERNATIVE APPROACH:
This problem is also equivalent to finding the maximum chordal clique in the graph. For this implementation you can have a look at this solution.

This is my first editorial. Please do comment, and point out any error you find.

7 Likes
2

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!

3

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 ,:slight_smile: XD

4

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.:slight_smile: 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.:wink:

5

What is the implication of this statement mentioned in problem:
The graph has a special property: for each simple cycle containing at least four vertices, there is an edge which is not part of this cycle, but connects two distinct vertices on the cycle.
@vivek_1998299 is this solution for a unique case( because of above statement) of npc problem ?

6

I cant actually prove its optimality,but its quite hard to find a countercase for this approach.

7

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

1 Like
8

You can corner Jerry with 3 cats.

J: 1, C: (2, 1, 5)
J: 2, C: (3, 4, 2) --> J: 1
J: 3, C: (3, 4, 5) --> J: 2
J: 4, C: (3, 5, 4) --> J: 2
J: 5, C: (4, 3, 5) --> J: 1

Jerry is always cornered.

9

The cat makes the first move(thats what made the question hard :slight_smile: ,as jerry can think what to do based on cats move):

So if C:(2,1,5),then J:3

Similarly other cases also

10

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 2-5(best chordal completion graph of G).

And now for modified graph ,max clique size is 4(2-3-4-5)

11

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)

12

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

1 Like
13

Yes, my mistake… Sorry.