You are not logged in. Please login at www.codechef.com to post your questions!

×

Help needed in DLDAG (December Long Challenge)

Problem : https://www.codechef.com/DEC18A/problems/DLDAG/

Can someone please let me know what is wrong in my code. Basically, what I did was, first I deleted all those vertices which don't have an edge to any other vertices (labeled as the vector freed in the code). I maintained two vector arrays, one for the children and other for the parent of a vertex. Initially, for the already free vertices, I removed them from their parents' adjacency list and checked if any node got free of all its children nodes, if yes, push it into the stack, make it the next to be deleted and repeat the same process till all vertices are deleted. I grouped the 1st two elements of the stack (if there were >=2 elements at a time in it) to be deleted together (because since they are in the stack, that implies they don't have any children nodes), or left a solitary 1 node to be deleted alone(in case only 1 element was left in the stack).

I tried with several possible DAGs, solved the sequence for them with hand and matched with the output of my code. Everything was right, but I still got WA. If someone could kindly find any case which I might have missed out, it would be really thankful.

Edit : @vijju123 can you please close this question. Reason: Question answered, need to learn Topological sort :p

asked 19 Dec '18, 14:27

kshitij_07's gravatar image

4★kshitij_07
364
accept rate: 6%

edited 29 Dec '18, 17:47


Actually in your code , you are selecting any random leaf node and starting your dfs from that node. But according to the question you have to minimize the number of steps. And your solution does not guarantee that nodes would be removed optimally.

According to the question , nodes which are at the farthest and is a leaf node should be removed first. So in my solution , I kind of calculated distance of all nodes from all leaf nodes and removed nodes which are at the farthest distance.

My solution link is Solution Link. Hope this helps. :)

link
This answer is marked "community wiki".

answered 19 Dec '18, 14:56

sorcerer48's gravatar image

5★sorcerer48
1084
accept rate: 36%

Okay, now I understood what the question asked. Initially, I thought that the question being Challenge should give AC for any number of steps provided they are in proper order, hence started at any node, and to my sad luck, the examples I took worked too for the same logic. Will try again. Thanks for the help.

(19 Dec '18, 21:47) kshitij_074★

@kshitij_07 I used the same approach initially. I also misunderstood the question. But, finally did something with topological sort and got a few points.

(20 Dec '18, 12:06) black_truce5★

In my solution Here I stored indegrees and outdegrees of each vertex and used Kahn topological sort. Then, I started at the end of the topological sort and tried removing vertices with outdegree 0 in pairs, and if not possible, remove only one (There is always one vertex with outdegree 0). After removing, you decrement the outdegree of each removed vertices parent... This will create other vertices with outdegree 0 to be removed in the next step...

The vertices with outdegree 0 won't necessarily be at the end, so the topological sort is important to reduce the overall complexity, which otherwise would be quadratic.

link

answered 28 Dec '18, 22:01

phoemur's gravatar image

3★phoemur
11
accept rate: 0%

Thanks for the suggestions, time to read Topological sort :p

(29 Dec '18, 17:37) kshitij_074★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×376

question asked: 19 Dec '18, 14:27

question was seen: 318 times

last updated: 29 Dec '18, 17:47