Jaadu mailed me this problem today. I was able to solve it and I am happy. This is an "intelligent" problem. Solution so elegant that you will fall in love with it. :)

Assume 100 ants are moving in 1 dimensional plane, all move with the same speed. Some are moving towards the positive x axis and some towards negative. If a collision occurs between two ants both ants changes the direction. If you are given direction of motion of each ant, what is the number of collision that will occur? Give an algorithm. :)

Update (11/12/09): Solution by A Rustle (Prathmesh, CSE, IITB) in comments !!

Assume 100 ants are moving in 1 dimensional plane, all move with the same speed. Some are moving towards the positive x axis and some towards negative. If a collision occurs between two ants both ants changes the direction. If you are given direction of motion of each ant, what is the number of collision that will occur? Give an algorithm. :)

Update (11/12/09): Solution by A Rustle (Prathmesh, CSE, IITB) in comments !!

For an ant moving right, count the number of ants to its right moving left. Add this number for every right moving ant. That is the number of collisions.

ReplyDeletehint: on every collision, assume that the two ants don't change direction but simply cross each other.

@Rustle

ReplyDeleteGreat!! Correct!! Nice solution..

nice solution good question

ReplyDeleteIts a nice problem. i was thinking of writing about...(trying to cp u)

ReplyDelete:)

ReplyDeleteyo dharme!!