@sudheerays123
For ZIO 2007 Q3
I’ve updated my answer and removed the phrase 'weighted average. I used it to indicate that you were looking in the right direction. But looks like it led to some confusion. My apologies for that. (a more accurate phrase for what I did would be 'median with conditions; but actually its not even median for the z axis. I don’t know what it is called 
)
You wanted to know that how I came up with the formula. What It’s doing that its dividing the data in four parts and selecting 3 (or 1) part from it. Hence the (3+1) in denominator. I’ve explained everything below. Also know that my solution is not a ‘general’ solution. It’s an exploitation of the fact that the testcases are given to us, and I just did the most logical process at each step. You may scroll down in this post to read the flaws I’ve mentioned.
The procedure I’ve come up with isn’t something I would call intuitive or anything that would strike you while reading the question. I came up with that solution by looking at the given coordinates for each of the three parts.
I’ll detail it out here
I was very inclined towards taking an average but obviously that meant that the answer may come out in decimal, which cannot be possible. Now, there could’ve been some method to handle decimal coordinates, but I wanted to explore all options that would straight away give me an integer answer , before I tried to think what to do with decimals.
Then I thought of taking median. This would give me an integer answer in all three cases. As there are odd number of people in each part, the median would be one of the given coordinates, i.e. an integer.
Next step was some practical thinking. Let’s say you want to meet a friend at one of the many restaurants which lie on the road connecting his home to yours. Your car uses 1 litre of fuel for every 10 km, while your friend’s car uses 1 litre of fuel for every 15 km. You want to minimize the total amount of fuel used. For the same amount of petrol, your friend covers larger distance than you. So the restaurant you choose to meet should be more closer to your home. I hope you understand this part.
I applied the same logic to the z-axis. Going up takes 3 units of fuel; down takes 1 unit. So more people should go down than up in the optimal situation.
Finally I had to come up with a number which will be my answer. I divided my coordinates into (3+1) parts = 4 equal parts. 3 groups of these people will go down, 1 group will move up. Now you’d realize that the number of people in all cases in odd. Hence dividing by 4 will give decimal answer, which i wanted to avoid from the very beginning. However, I observed that in all cases if you subtract 1 from the number of people, you get a multiple of four.
Even in x and y axis, The cost is 2 and 2 for either direction. So I need to divide data into 2+2= 4 groups. And (n-1) is divisible by 4.
Now, everyone except one person has to move either up or down. What happens to this one person who is left out? Well, he is already on the optimal coordinate for the specific axis. And that coordinate is the answer.
For the x and y axis, median works, because even if you’re using my procedure, you’d be indirectly calculating the median.
Some flaws to prove my solution wrong
- My procedure works ONLY when
n can be represented as 4k + 1. Otherwise you get a decimal answer. And not getting a decimal answer was the first motivation to think in whatever direction I did.
- My solution is not a generalized algorithm. I exploited the fact that I had testcases, in this case three testcases. This is much like the things you do in an MCQ test.
- The solution implicitly assumes that one of the people is already in the optimal coordinate. In other words, the optimal coordinate must be one of the coordinate where there is a person. However this is neither guaranteed in the question, nor I have proved this fact. So, mathematically speaking, my solution is unacceptable because it uses unproved facts to prove something else.
Yet I posted my solution here, because it gave correct answer for all three parts. It may inspire someone else to reach at a solution which is actually correct.
Or maybe, my solution is totally different from what you’re actually supposed to do :-p
.
and this is the only problem where logarithm was used i guess so what should i do ? 