Why Did the Cow Cross the Road?

Source: USACO 717

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
2. How would you solve the problem if Bessie ate the grass in every field she visited, rather than every third?
   • What is the graph, i.e. what are the vertices and edges?
   • Encode the time taken in moving between vertices as purely an edge weight (so as to avoid vertex weights).
   • Formulate the problem in terms of paths in this graph.
3. Design an algorithm to solve this simplified problem.
   • Which famous algorithm is most suitable to find the desired path?
   • What information is necessary to encode a state in the search performed by this algorithm?

4. Analyse the time complexity of your algorithm and estimate its running time.

5. Implement this algorithm in code.
   • Note that the input and output use files visitfj.in and visitfj.out, not stdin and stdout. Include the <cstdio> header and begin your program with the commands freopen("visitfj.in","r",stdin); and freopen("visitfj.out","w",stdout);.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.

Now we can return to the original problem, where Bessie only eats from every third field.

1. Adapt your earlier algorithm to solve the full problem.
   • At each step of the search, what extra information would be needed to determine whether Bessie spends time eating or not?

2. Analyse the time complexity of your new algorithm and estimate its running time.

3. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
4. Submit your program for judging!
   • Debug as required.