Given N points in 2D plane, (from 1 to n)

X[ 1…n ]

Y[ 1…n ]

Select K points P_1...P_k to maximize the following value

Value = \sum_{i=1}^{k} (X_i * \sum_{j=1}^{i-1} Y_j)

The K points is a permutation of subset C_{K}^{N}

Given N points in 2D plane, (from 1 to n)

X[ 1…n ]

Y[ 1…n ]

Select K points P_1...P_k to maximize the following value

Value = \sum_{i=1}^{k} (X_i * \sum_{j=1}^{i-1} Y_j)

The K points is a permutation of subset C_{K}^{N}

1 Like

I believe the naive approach would be C_{K}^{N} * P_{K}^{K} * K

I wonder if there is a faster approach?

What was the required complexity?

1 Like

Adding an example

Input: N, K, X[ 1…n ], Y[ 1…n ]

Output: Maximum Value Possible

Example:

N = 4

K = 3

X = [1, 5, 2, 8]

Y = [9, 7, 4, 3]

Maximum Value Possible: 173

Where the points sequence is {1, 9}, {5, 7}, {8, 3}

the Value is 1\times0 \ + \ 5\times9 \ + \ 8\times(9+7) \ = \ 173