• Oil company is planning a large pipeline from east to west (x-axis) across its oil field
• The field has n wells
• The company wants to connect each well directly to the large pipeline with smaller pipelines, running north-south (y-axis)
• Your task is to calculate the optimal position (on the y-axis) of the large pipeline, so that the total length of all smaller pipelines is shortest
• (If the large horizontal pipeline has the same y-coorindate as a well, length of smaller pipeline that is needed for that well is 0)
• You have the information about the positions of each well on the y-axis
• takes as input
• on the first Hne, the number of wells n, n>=2, n<1000000
• on each consecutive line (from 2nd to (n+1)-th line), the y-coordinate of one well (integers in the range 0 to 1000000000)
• returns on output
• a single number: the y-coordinate where the pipeline should be built (an integer in the range 0 to 1000000000)
• only this one number, no comments, prompts for input etc,
• Use Standard I/O to read input and write the result
• In Java, it's System.in for input, System.out for output
• Usage in Linux/MacOS:
> javac cmsc401.java
> cat someInput.txt lava cmsc401> result.txt
• Make sure the program compiles
Example of a correct result:
Length of connecting pipelines: 10. There are no y-positions for the large pipeline with total length of connecting pipelines smaller than 10. However, some other results also lead to 10.
Length of connecting pipelines: 7.
There is a better y-position, with the total length of connecting pipelines equal to 5.
• OLJ should go through two phases:
• Abstract problem solving
• What is the general rule that leads to the solution
• Go through a couple of examples, try to come with a simple rule
• Algorithm design & coding
• Once you know what your solution is mathematically, think about howto find it quickly using an algorithm
• Threat the y-coordinates for n wells as an array A of the size n
• Design a divide & conquer method to solve the problem
• On Ar the algorithm should use Partition function from quicksort
• The whole structure should be recursive but different from quicksort
• Try to use the asymptotically fastest method possible B in terms of the expectedlaverage-case running time - aim at expected linea time
• slow methods vvill get lower score even if correct
• There may be several correct solutions that are equally good, return on output only one of them