Problem Link: ZIO 2007 Proble 3
Prerequisites: Logical-Thinking
Problem Statement:
Given N students, each depicted by a three-dimensional(3D) point in the form of (x,y,z), the effort of moving from (x,y,z) to either of its fours neighbouring points (x+1,y,z), (x-1,y,z), (x,y+1,z) and (x,y-1,z) is 2 units each. But the effort of moving from (x,y,z) to (x,y,z-1) and (x,y,z+1) is 1 unit and 3 unit respectively. Find the optimum point where all the N students can be moved to with minimum effort.
Observation 1:
If we observe carefully then this problem can be solved for x,y and z coordinates independently as the coordinates are not dependent on each other. So the problem reduces to N points in a straight line.
Observation 2:
For points on x or y coordinate the optimal point will be the median of all the points. For example:
-
N=3, points={3,30,300}. Then the optimal point will be 30. Let us prove this. Effort to move all students to point 30= 2*(30-3) + 2*(30-30) + 2*(300-30) = 634. If we move to point 31 then this effort will increase by 2. Similarly if we move to point 29 this effort will increase by 2. So whenever we move away from the median the effort increases as we move closer to a smaller set of points and move away from a larger set of points.
-
N=4, points={1,10,100,1000}. Here the optimal point can be any point ranging from [10 - 100] as we have two middle elements(because N is even) and moving around from point 10 to point 100 will have the set of points on either side of it have the same number of elements.
So we can say that if there are N points sorted in ascending order, then:
- If N=2*k+1, optimal point= (k+1)th point
- If N=2*k, optimal points= [kth -(k+1)th] point
Observation 3:
For points on the z-coordinate the effort to move from (z) to (z+1) is 3 times the effort to move from (z) to (z-1). So our optimal point must be closer to smaller z values rather than larger z values. If we arrange our set of points in increasing order and divide it into (1+3) equal parts then the optimal point must lie between the 1st and 2nd part. Examples are:
-
N=5, points={1, 10, 30, 60, 100}. Here the optimal point must be the second point 10. Effort to reach 10= 3*(10-1) +(10-10) + 1*(30-10) + 1*(60-10) + 1*(100-10) = 187. Moving closer to 1st point or the 3rd point will increase this effort.
-
N=6, optimal point =2nd point if points are sorted in ascending order.
-
N=7, optimal point =2nd point if points are sorted in ascending order.
-
N=8, optimal point may lie at any point from the 2nd to the 3rd point.
So we can say that if we have N points sorted in ascending order:
- If N=4*k+1, optimal point= (k+1)th point
- If N=4*k+2, optimal point= (k+1)th point
- If N=4*k+3, optimal point= (k+1)th point
- If N=4*k, optimal points= [(kth) - (k+1)th] point
Subtask A
N=13
Points are: (36,90,7), (77,69,7), (75,22,7), (43,30,7), (75,62,7), (70,23,7), (76,30,7), (25,28,7), (95,56,7), (3,25,7), (51,98,7), (2,11,7), (46,46,7).
x coordinates sorted in ascending order:
[2, 3, 25, 36, 43, 46, 51, 70, 75, 75, 76, 77, 95]
so optimal x coordinates will be 7th point= 51
y coordinates sorted in ascending order:
[11, 22, 23, 25, 28, 30, 30, 46, 56, 62, 69, 90, 98]
so optimal y coordinate will be 7th point= 30
All z coordinates as equal to 7 and hence optimal z coordinates= 7
Optimal point to reach with minimum effort: (51,30,7)
Subtask B
N=25
Points are: (51,1,73), (61,1,33), (1,1,34), (46,1,38), (23,1,94), (91,1,89), (11,1,89), (10,1,70), (37,1,73), (96,1,93), (44,1,50), (16,1,81), (50,1,28), (50,1,84), (55,1,60), (48,1,97), (3,1,62), (92,1,84), (27,1,22), (100,1,51), (59,1,31), (8,1,39), (55,1,47), (50,1,1), (33,1,45)
x coordinates sorted in ascending order:
[1, 3, 8, 10, 11, 16, 23, 27, 33, 37, 44, 46, 48, 50, 50, 50, 51, 55, 55, 59, 61, 91, 92, 96, 100]
so optimal x coordinate will be 13th point= 48
All y coordinates are equal to 1 and hence optimal y coordinate= 1
z coordinates sorted in ascending order:
[1, 22, 28, 31, 33, 34, 38, 39, 45, 47, 50, 51, 60, 62, 70, 73, 73, 81, 84, 84, 89, 89, 93, 94, 97]
Here n =25 (4*k+1) form, k=6
Hence optimal z coordinate = (k+1)th point= 7th point= 38
Optimal point to reach with minimum effort: (48,1,38)
Subtask C
N=21
Points are: (18,72,69), (12,81,43), (40,19,33), (40,60,48), (2,78,66), (14,78,84), (70,25,3), (48,59,43), (29,4,10), (12,96,1), (89,13,74), (57,26,54), (100,32,39), (99,38,65), (13,40,43), (79,20,20), (28,91,12), (98,38,37), (40,34,41), (16,46,36), (18,1,16)
x coordinates sorted in ascending order:
[2, 12, 12, 13, 14, 16, 18, 18, 28, 29, 40, 40, 40, 48, 57, 70, 79, 89, 98, 99, 100]
so optimal x coordinate will be 11th point= 40
y coordinates sorted in ascending order:
[1, 4, 13, 19, 20, 25, 26, 32, 34, 38, 38, 40, 46, 59, 60, 72, 78, 78, 81, 91, 96]
so optimal y coordinate will be 11th point= 38
z coordinates sorted in ascending order:
[1, 3, 10, 12, 16, 20, 33, 36, 37, 39, 41, 43, 43, 43, 48, 54, 65, 66, 69, 74, 84]
Here n=21 (4*k+1) form, k=5
Hence optimal z coordinate =(k+1)th coordinate= 6th point= 20
Optimal point to reach with minimum effort: (40, 38, 20)
Silly trick to save time:
If you know you have to find the ith point in the sorted order among N elements then you don’t need to sort the entire set finding the minimum point one by one. You just need to find till the ith smallest point and you are done!
Program:
Programming enthusiasts can look at very simple code to examine their own set of 3D coordinates here.
I would like to thank Sudheera Y S for motivating me to write my first editorial on CodeChef. If you have any doubt, comment below!
