scar_face's blog

Need ideas in this problem.
By scar_face, history, 4 years ago, In English

I was asked this problem in Bytedance OA.

N points are given on a line and K special points can be setup anywhere. You have to find the sum of shortest distances for each point to any special point. I know a solution like grouping points, and then for each group, sum of distances to their median, but it didn't work that time. I am thinking some DP but unable to figure out.

Constraints are N, K <= 100

Coordinates of points 1 <= C[i] <= 10^4.

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

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

What is the problem with brute force $$$O(NK)$$$?

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

Auto comment: topic has been updated by scar_face (previous revision, new revision, compare).

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

check this one

1283D
→ Reply