Delete DAG

Can anybody tell me how to proceed for problem Delete DAG? or any editorial?

1 Like

The main idea is

1.Apply Topological sorting to graph
For suppose after applying topological sorting you have results like 2 4 5 6 7 8 9 10,

2.Process from last, take two vertices U(from above 10) and V(from above 9) if U is connected to v then you can’t delete two vertices at once.first you delete U and then Delete V(Total two steps).

Output: 1 10,
1 9

3.if both u and v are not connected you can delete two vertices in one go
Output:2 10 9

This idea give you score>89.I hope you got the some idea.

My Submission https://www.codechef.com/viewsolution/21994112

1 Like

What I did was determine the maximum distance of each node from any roots. For the example, those distances are:

1 = 0
2 = 1
3 = 2
4 = 3
5 = 3
6 = 1

I then just removed the nodes with the greatest possible distance. I had this idea in my head that doing this was optimal, though apparently not. It did get me 93.22 though.

My solution

@gopikrishna_p1, I tried this exact same method and I just got 28 points xD

@black_truce can you share the link to your submission?

I’ve got 99.5 points with this approach :

Doing a kind of topological sorting (which can be done using a queue and pushing in the queue a node when its outdegree is 0) but insted of using a queue I used a priority queue , so we could give a criterion to decide which nodes we should delete first.

Which criterion ?
The idea is deleting the nodes which have a parent that can be deleted sooner (than other parents) in next steps.

To achieve that, I did the following :

  • First , we need to define the “height” of a node. All the nodes that has outdegree 0 has height 0. Then for the other nodes : height[ node ] = (max height of all its childs ) + 1.

  • And the criterion : we would give more priority( for deleting ) to the nodes which has a parent with less height.

I believe that maybe it could be possible to get 100 points defining another kind of height but instead of starting with nodes with outdegree 0 , you can start with those with indegree 0. And then weigh these 2 criteria.

My solution