ANTS - a simple approach

general
1

What is the best way to approach the challenge problem ANTS in the 2020 August Long Challenge? I took the following approach, which earned me about 80 points. I found these points easier to obtain than from all but one of the other problems this month.

My method is broadly as follows. There are a few extra details which you can find in the code if you are interested.

  1. Choose as the root any node which has at least one incoming edge.
  2. Build a tree by following edges backwards by DFS, so that each node has an edge which runs towards its parent. Store the depth with each node, and a list of nodes at each level, where they have the same depth. It is important for step 5 below that no two nodes on the same level have an edge linking each other. If we find one, we assign the latest node to the next level.
  3. A few nodes may be missed, where the node has no outgoing edge. If we have missed any this way, set each such node to have as its parent the node with the lowest depth to which any of its edges is linked, and reverse the parent edge. There are more details here which I won’t go into at this stage, but if you are interested, please ask.
  4. We want to keep the number of instructions of type 2 down, so if there are only a few nodes at the last level we may be able to reassign these nodes to different nodes and so reduce the total number of levels. Reversing an edge typically costs 1 to 50, average 25.5, and reducing depth of a node requires edge reversal half the time, so we try this reassignment when 13 * number of nodes on least level < S the cost of moving ants with an instruction of type 2.
  5. Move the ants one level at a time. Working up from the last level, first reverse edges so that for each node the only edge pointing away is towards its parent. Then issue an instruction of type 2, so that all ants on the current level move to the level above.
  6. As all the above takes only a small fraction of the allowed time, try the whole sequence for each of a series of root nodes, and choose the one with minimum total cost.

You can find my solution at CodeChef: Practical coding for everyone

1 Like
2

Ohk so, after trying DFS a lot, i switched to BFS.
The problem doesn’t mention anything about the connectedness of the graph, there could be different components too… So i assumed, there could be so.
Here’s my approach:

  1. First, find components.
  2. Now for each connected component, i used two dfs to find the diameter ( though it could be cyclic, i know, i will not visit any visited nodes, so it would be more like a tree with omitted edges)
  • Step 2 isn’t much helpful in cyclic components but it is in directed components.

  1. I didn’t care the directions of the edge, bcz i can flip any edge which i think helps, but just gave preference to incoming edges rather than outgoing edges.

  2. Now, for each component, I used bfs on the approximate center node on diameter. ( this helps me in 82.7 points).

  3. What i am going to do is just to level up the ants, for that, i have a parent of every node and hold number attached with every node.

  • hold number tells the number of child nodes of the parent node having ants
  1. The simpleants() method- Just pick a node which has hold[node] = 0 and level up the node, In order to level up, we should make all the edges incoming except the edge connecting it to its parent. When we levelled up a node decrease hold[parent[node]] by 1
  • Problem 1 - When we make all the edges incoming(except one) there could be a case where two nodes have 0 hold values sharing an edge. So it was simple, just continue with 1 node and pause levelling up of other nodes adjacent to it having hold = 0,
  • Observation 1 - There could be no adjacent nodes having ants and outgoing edges=1 ( at least two nodes should be there, one the parent and other the node sharing the edge)
  1. Repeat step 6 while “nodes having ants”>k

Submission

Edit:Submission link added

@therealnishuz

1 Like