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