ISTA2001 - Editorial

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. :slight_smile:


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 imes B, B imes H faces, L imes H, B imes H faces and L imes B, L imes 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 imes H, B imes 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:

\sqrt{l^2-x^2}+\sqrt{b^2-(h-x)^2}

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 :wink: 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 imes b, l imes 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

3 Likes

It would be really helpful if you could post an explanation. I’m finding it hard to get the ones given online.

Geometry problems? :frowning: Ugh!

Even if its googleable, you ought to tell your approach for the problem. There might be a portion of people who need further assitance than what google has to offer.

Sure, will linking the resources help? :frowning:

I think you can describe it in your words. Yeah, linking should help, but not act as a substitute to your perception, even if they are same.

If you want you can give the solution of it using 3-D calculus and differentiation :3

Oh no, the solution I intended is exactly the ones available on the web. :stuck_out_tongue: I dont know 3D calculus and differentiation.

Hey, sure, I will edit it right now!

This one is quite elementary if you look at the editorial :stuck_out_tongue:

PS : the editorialist couldn’t solve it on its own.

1 Like