Contest: ICO Preparatory Series Contest 1
Setter: Istasis Mishra
Tester: Udit Sanghi
This would be an apology rather than an editorial. You can find the solution by just googling “Cuboid ant”. I deeply regret that I have put up this problem up for this contest. It was brought to my attention that this problem’s solution is googlable 2.5 hours into the contest.
I hope the community will accept my apology and I promise this won’t happen again. I will make sure my problems are original from now on and only then put it up for a contest.
Anyway, below is the editorial.
Problem
Given a cuboid find the shortest path from one of its corners to the corner which is diagonally opposite to the first corner.
Solution
For subtask 1, since one dimension is 0, it is just a rectangle, the shortest path being the diagonal.
For subtask 2, we basically need the ant to travel on 2 faces, connecting the current point to the opposite. Note that there are 3 ways to do it, that is taking the L \times B, B \times H faces, L \times H, B \times H faces and L \times B, L \times H faces. We need to find the minimum length path from these pairs.
But how do we find the minimum for a particular choice of faces?
There are 2 ways to approach this:
We need to fix a point ‘a’ on the edge connecting the 2 faces. This way, our path length becomes initial point to ‘a’, and ‘a’ to final point. For an L \times H, B \times H pair we fix a point on the height and lets say its height is X. Using pythagoras theorem, we can find that the path length is:
We could use ternary search to find the minima on this.
Do this for all 3 pairs of faces, take the minimum of these minima, you get your answer.
However this is what we call the ‘ugly’ approach even though it would easily pass the constraints.
Let us look for something better,
It is common knowledge that the shortest distance from one point to another is a straight line between the points. But how do we use this when the ant can’t fly? Well, we use it on the faces. How do we do this? Just open the net of the cube for visualization purposes, and mark a straightline This gives us a path in which the ant always moves on the faces. You can think of it as a box which you can open p and then paint a red line through the path you wanna take. You just fold the cuboid back up and then ask the ant to follow the red line you drew.
The formula for this path in the first scenario for an l \times b, l \times h pair is \sqrt{l^2+(b+h)^2}. You can similarly compute for the other other pairs and take the minimum.
Author’s solution: here