vamaddur's blog

USACO 2015 Gold January Contest Grass Cownoisseur: Longest Path on a DAG... With a Twist
By vamaddur, history, 7 years ago, In English

Problem: http://www.usaco.org/index.php?page=viewproblem2&cpid=516 Official Solution: http://www.usaco.org/current/data/sol_grass_gold.html

I was able to reduce the problem to solving it on a weighted DAG after compressing the graph into strongly connected components. However, I am not able to handle the caveat of being able to traverse a reversed edge at most once.

Is there a way to solve this final step of the problem without dynamic programming? If not, can someone explain what exactly is going on in the "solve" function and calls to it?

Please help, and thanks in advance!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I believe the final step requires DP. Here is my code, hopefully the comments clarify things. Unfortunately I still used java back then.

https://pastebin.com/yGCUVMq3

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @farmersrice I understand the DP part now, but I am confused as to how it accounts for following no path backwards.

    "She wonders how much grass she will be able to eat if she breaks the rules and follows UP TO ONE PATH in the wrong direction." — Problem Statement

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Correct me if I am wrong, but this is my explanation for the above:

      The SCC graph is now a DAG, which means it has no cycles. A path back to the starting node cannot be found unless an edge is traversed backwards. If no edge is actually traversed backwards, the best possible answer is the size of the SCC that contains the starting node.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I think this is the important part:

                barn.barnancestor = false;
        for (int i = 0; i < vertices.length; i++) {
            if (!vertices[i].barnancestor) {
                for (int j = 0; j < vertices[i].parents.size(); j++) {
                    if (vertices[i].parents.get(j).barnancestor) {
                        answer = Math.max(answer, vertices[i].distance + vertices[i].parents.get(j).distance + barn.pastureCount);
                    }
                }
            }
        }

        This should be taking the answer of the parent distance + cur distance + cur pasture count (I think cur pasture count is to account for some weird way I counted the cows per pasture). The parent's distance is only checked if it is a barn ancestor, which means that it's possible to traverse upwards from the barn to get to that node. If so, then we have a loop of going from parent, through the barn, down the normal way to the current node, and then taking the reversed edge back up to the parent to form a cycle.

        → Reply