The_SSU's blog

Explain the solution please!!
By The_SSU, history, 4 years ago, In English

https://mirror.codeforces.com/problemset/problem/1175/C can anyone explain the solution of this problem please? why should we check for the range of consecutive k elements here? solution is here 55178770

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

Hello. We are given that the array A is sorted.

  1. If you spend a bit of time, you can understand that Fk(x) denotes the distance of (k+1)th nearest point from x.

  2. Observe that nearest points of x are chronological neighbours of x. For example, if we are looking at the Nth nearest point of X, and we have a list of (N-1) nearest points with us, some on left of x and some on right of x, then the required point will either be to the immediate left of an existing point, or immediate right of an existing point (i.e. no gaps). (Let know if you want a proof)

  3. Therefore, by spending a little time, we can observe that (K+1) nearest points of any point x must correspond to a sliding window of size K+1 in the array.

  4. Once that is established, we know that x can be chosen by us. What is the distance of x from each point in the sliding window? Note that it decreases till it reaches the nearest integer to x, and then starts increasing again. Therefore D_(k+1) (the required (k+1)th distance) must be the max of D1 and D2 where D1 is distance of x from the first element in the window and D2 is distance of x from last element in the window.

  5. Now, we need to minimize this distance. You can observe that there is a tradeoff between these 2 distances D1 and D2. As we move x to the left, D1 decreases and D2 increases. (with D1+D2 =constant at all times). The minimum distance must occur at the middle.

Happy to elaborate on any of the numbered points that is not clear.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can't understand the second point. Can you give the proof?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I will proof this by a simple contradiction argument Assume that at least one of the N nearest neighbours of x does not belong to a continuous window of size N containing x. Let us assume this nearest neighbour is Aj. Without loss of generality, assume Aj<x (same proof works for Aj>x). As the window is not continuous as per our assumption, there must exist some element Ak between Aj and x which is not a nearest neighbour of x. But distance of Ak from x is clearly less than distance of Aj from x. So if Aj is a nearest neighbour, Ak must also be a nearest neighbour. That contradicts our assumption.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

if we know that the best point have xl limit on the left and xr limit from the right and by limit I mean the limit of numbers that form the first k + 1 distances.

for example if the array is given (note that the array is given is sorted) 1 3 4 5 6 7 and k = 2 if we choose the point x to be 2 that mean the left limit is 1 and right limit is 4 from 1 to 4 those are the numbers that form the first k+1 distances after sorting as we can see 1 — 2, 3 — 2, 4 — 2 which is 1, 1, 2, and we only care about first k + 1 distances because we want to make k+1 th minimal.

now suppose we know what is xl (left limit ) and what is xr so it's greedy to choose x as (xr + xl ) / 2 now let's try every array[i] as the left limit then we are forced to make array[i + k] the right limit and we take the best x from every array[i] we try to take as the left limit.

→ Reply