Task Authors: Monika Steinová (CHE/SWK), Michal Forišek (SWK)

This is known to be a hard problem. No general polynomial algorithm is known for this problem, that is, no algorithm has been discovered that is guaranteed to solve each problem instance in a time polynomial in the size of the problem (area of the corn field).

This is also the reason why this task was offered as an output-only task, where the contestants were given 10 specific instances (corn fields) to tackle. They could do this by hand, or write programs to analyze these mazes, and write yet other programs (potentially, a different program for each field) to produce a long(est) path. Note that the path need not be optimal; points could also be scored for (good) approximations.

Here are some characteristics and results by Tor Myklebust (HSC member) for the 10 instances that the contestants had to tackle:

Characteristics Tor's result Instance Dimensions Obstructions Path length Score 1 10x10 8 20 10.00 2 100x100 1766 4026 10.15 3 100x100 3216 3740 8.61 4 100x100 2283 3733 8.58 5 100x100 1357 4738 8.86 6 11x11 0 54 10.00 7 20x20 210 33 10.00 8 20x20 122 95 10.00 9 11x21 10 106 10.45 10 200x200 15224 7506 9.17 Total 95.82