Ant Query

Scientists from the planet Krypton have figured out a way to grow artificial sugar in space. They have constructed a huge 3-dimensional steel grid upon which they will produce artificial sugar. Each sugar stock will be attached to a point on the grid. A cosmic ant wants to crawl from stock X to stock Y along the grid line.

This is a companion discussion topic for the original entry at https://toph.co/p/ant-query

Shouldnât the answer of case #2 query no 4 be 8? Itâ's the maximum distance the ant has to travel whuch is from the 3rd sugar stock, isnât it?

@hjr265 āĻ­āĻžāĻāĨ¤ āĻŽāĻ¨ā§ āĻšā§ āĻāĻŋāĻ¸āĻŋāĻ¤ā§ āĻ­ā§āĻ˛ āĻāĻā§āĨ¤ āĻĒā§āĻ°āĻļā§āĻ¨ā§ āĻŽāĻŋāĻ¨āĻŋāĻŽāĻžāĻŽ āĻŦāĻ˛āĻž āĻĨāĻžāĻāĻ˛ā§āĻ āĻ¸āĻŦāĻžāĻ āĻŽā§āĻ¯āĻžāĻā§āĻ¸āĻŋāĻŽāĻžāĻŽ āĻĻāĻŋā§ā§ āĻ¸āĻ˛āĻ­ āĻāĻ°ā§āĻā§āĨ¤ āĻāĻāĻŋ āĻ¨āĻŋāĻļā§āĻā§āĻ āĻāĻžāĻĢāĻŦāĻžāĻ¸āĻŋāĻĻā§āĻ° āĻŦāĻŋāĻ­ā§āĻ°āĻžāĻ¨ā§āĻ¤ āĻāĻ°āĻžāĻ° āĻāĻāĻāĻŋ āĻāĻā§āĻ°āĻžāĻ¨ā§āĻ¤āĨ¤ āĻŦāĻŋāĻˇā§āĻāĻŋ āĻāĻ¤āĻŋā§ā§ āĻĻā§āĻāĻžāĻ° āĻāĻ¨ā§āĻ°ā§āĻ§ āĻāĻ°āĻž āĻšāĻ˛ā§āĨ¤

1 Like

@touhidur Let me get in touch with the roundâs coordinator and get some insights.

1 Like

âThe cosmic ant always chooses the shortest possible path along the grid lines while going from stock X to stock Y. The ant has an Energy capacity, and he loses 1 unit energy in walking 1 unit of distance.â

Here shortest path on grid line means manhattan distance.

âThen they will ask you to find out the minimum required energy capacity for the ant such that the ant can visit any sugar stock from any other sugar stock.â

And here minimum required energy capacity for visiting any point to any other point on grid means that minimum manhattan distance between farthest two points available on the grid. So you have to calculate the maximum of minimum distance between all possible pair of points on the grid.

Lastly all test cases are correct and You can have a look on the editorial for the solution idea.

2 Likes

āĻ¸āĻ°āĻŋ, āĻāĻŽāĻŋ āĻ­ā§āĻŦā§āĻāĻŋāĻ˛āĻžāĻŽ āĻļāĻ°ā§āĻā§āĻ¸ā§āĻ āĻĒāĻžāĻĨā§ āĻ°āĻŋāĻā§ā§āĻžāĻ°āĻĄ āĻāĻ¨āĻžāĻ°ā§āĻāĻŋ āĻāĻžāĻ¨āĻ¤ā§ āĻāĻžāĻā§āĻž āĻšā§ā§āĻā§āĨ¤ āĻāĻ¨āĻžāĻ°ā§āĻāĻŋ āĻ¸ā§āĻāĻ āĻāĻŽāĻ¨ āĻšāĻŦā§ āĻ¯āĻžāĻ¤ā§ āĻ¯ā§āĻā§āĻ¨ā§ āĻ¨ā§āĻĄ āĻĨā§āĻā§ āĻ¯ā§āĻā§āĻ¨ā§ āĻ¨ā§āĻĄā§ āĻ¯ā§āĻ¤ā§ āĻĒāĻžāĻ°ā§ āĻŦāĻŋāĻˇā§āĻāĻŋ āĻā§ā§āĻžāĻ˛ āĻāĻ°āĻŋāĻ¨āĻŋāĨ¤ āĻĒā§āĻ°āĻŦāĻ˛ā§āĻŽ āĻ¸ā§āĻā§āĻ¯āĻāĻŽā§āĻ¨ā§āĻāĻāĻŋ āĻŦā§āĻāĻŋā§ā§ āĻĻā§ā§āĻžāĻ° āĻāĻ¨ā§āĻ¯ āĻ§āĻ¨ā§āĻ¯āĻŦāĻžāĻĻāĨ¤ āĻāĻ° āĻŽāĻžāĻ§ā§āĻ¯āĻŽā§ āĻāĻžāĻĢāĻŦāĻžāĻ¸āĻŋāĻ°āĻž āĻŦāĻŋāĻ­ā§āĻ°āĻžāĻ¨ā§āĻ¤āĻŋ āĻĨā§āĻā§ āĻŽā§āĻā§āĻ¤āĻŋ āĻĒāĻžāĻŦā§ āĻāĻ¨āĻļāĻžāĻāĻ˛ā§āĻ˛āĻžāĻšāĨ¤

If anyone need detail explanation with code here

Sorry i misunderstood the question. I thought it was asking for maximum manhattan distance from a single point to other points not from any point to any other point. Please forgive my silliness.