Can anybody tell me how to proceed for problem Delete DAG? or any editorial?
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,
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
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.
@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.