You are not logged in. Please login at www.codechef.com to post your questions!

×

ACM14KP1 - Editorial

0
1

PROBLEM LINK:

Practice
Contest

Author: Jingbo Shang
Tester: Anudeep Nekkanti
Editorialist: Jingbo Shang

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Sort, Divide and Conquer

PROBLEM:

Given N points in a plane, find out three points A, B and C such that |AB| + |BC| + |CA is smallest.

EXPLANATION:

Classical 2 points (Closest Points)

This is a classical problem that finding out the closest 2 points. We can deal with that using divide and conquer.

Initially, we sort all the points P[1..N] by their X values, from small to large.

Now, suppose we are handling the answer in points between indices l and r, i.e. the closest points in P[l..r].. First of all, we divide them into 2 parts and recursively calculate the closest points problem. That is, find out the answer in P[l..m] and P[m+1..r]. Assume the minimum answer is A. Then, we try to update the answer using the points from different parts, i.e. |P[i] – P[j]|, where l <= i <= m < j <= r. Instead of bruteforce enumeration, we can use the current answer A to prune. It is easy to prove that there are only a small constant of points within the square [P[i].x, P[i].x + A] X [P[i].y, P[i].y + A] (Otherwise, the current minimum should be less than A). Therefore, we can further sort the points in P[l..r] in the order of Y coordinate, scan them one by one, and use the bruteforce enumeration inside the small square to update the answer.

If we use quick sort every time, the time complexity should be O(Nlog^2N). However, we can apply merge sort for the sorting of Y values, and thus the time complexity could be reduced to O(NlogN).

Original Question

Similar ideas could be applied to 3 points. The only difference is that the constant bound of the points in that small square may be different.

It is an accident that both setter and tester did not realize there existed a same problem in Google Codejam 2009 Finals. You can also check their editorials for more information.

AUTHOR'S AND TESTER'S SOLUTIONS:

Solutions will be available soon.

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 01 Dec '14, 09:24

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446172
accept rate: 0%

edited 01 Dec '14, 12:24

admin's gravatar image

0★admin ♦♦
17.4k347486515


please correct me.. what I did was for the problem was that I compute a side and then i keep track of the minimum three sides thus obtained, i am getting a wrong answer for the problem. https://ideone.com/1x1AfI thanx in advance :)

link

answered 28 Oct '15, 00:46

smitthakkar's gravatar image

3★smitthakkar
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,081
×102
×40
×2

question asked: 01 Dec '14, 09:24

question was seen: 3,149 times

last updated: 28 Oct '15, 00:46