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.
- Choose as the root any node which has at least one incoming edge.
- 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.
- 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.
- 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.
- 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.
- 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 https://www.codechef.com/viewsolution/36845217