Locating point on a closed path to maximize sum of distances to a sample of weighted points

Question

I'm doing AI for a simple puzzled game and need to solve the following problem efficiently (less than 1 sec for the range specified since I need to do many iterations in a game).

A sample of N (1 to 100,000) monsters with strength from 1 to 10,000 are distributed on the sides of a square (0 to 200,000,000) at 1 unit interval starting from the upper left corner. Move hero to a point X on the square to maximize sum of the weighted distances to the monsters. A weighted distance to each monster is calculated by MonsterStrength*ShortestDistanceToX (by going clockwise or anticlockwise). X must also be on the 1 unit interval mark and the monsters and hero move on the sides of the square only

I have tried several approaches but none are fast or accurate enough.

The possibly complementary of this problem (minimizing the sum of distances to set of points at furthest distance from each corresponding monsters in the original set) seems to related to finding the geometric median, facility location problem, Weber problem etc.

Linear programming is also possible but might be too slow and overkilled.

Does anyone have any idea for a good approach?

---

Here is an illustration on a square of sides of length 3:

1-------2(M/3)-------3------4(M/1)
|                              |
12(M/2)                        5
|                              |
11(M/1)                        6
|                              |
10--------9---------8(X)-------7

if you put a monster of strength 3 at 2, one with strenth 1 at 4, one with strength 2 at 12 and one with strength 1 at 11 and the hero(X) at 8. the sum of weighted distane is: 3*6 + 1*4 + 1*3 + 2*4 = 33, which is also the maximum in this case

Answer 1

I have found a pretty good solution for this. For anyone who is interested, here is my C/C++ code for unit testing of the algorithm. Input format: N L monster1_pos monster1_strength monster2_pos monster2_strength ....
Correctness is tested against a bruteforce algorithm on smaller cases
Large cases are generated randomly
Program run from 44 ms to 84 ms on Intel core i3 running Ubuntu Linux for largest test cases

#include <stdio.h>
#include <stdlib.h>

#define MAXH 100000

int num_monster, side;
int half, total;
int monster[MAXH][2]; //col0: monster pos, col1: strength
int opp[MAXH][3]; //col0: opp pos, col1: num people in opp monster, col2: index of opp monster
int boundaryMonster = -1;

int min (int a, int b) {
    return a<b?a:b;
}

int getOpp(int pos) {
    return (pos==half)?total:(pos+half)%total;
}

int getDist(int from, int to) {
    return min(abs(to-from), total-abs(to-from));
}

int totalsum(int pos) {
    int result = 0;
    for (int i = 0; i < num_monster; i++) {
        result += getDist(pos, monster[i][0])*monster[i][1];
    }
    return result;
}

//find sorted sequence of pos where monster exists at opposite pos
void oppSeq() {
    int count = 0;
    for (int i = boundaryMonster; i < num_monster; i++) {
        opp[count][0] = getOpp(monster[i][0]);
        opp[count][1] = monster[i][1];
        opp[count][2] = i;
        count++;
    }
    for (int i = 0; i < boundaryMonster; i++) {
        opp[count][0] = getOpp(monster[i][0]);
        opp[count][1] = monster[i][1];
        opp[count][2] = i;
        count++;
    }
}

int main() {
    FILE *input, *output;

    input = fopen("monster.in", "r");
    output = fopen("monster.out", "w");

    fscanf(input, "%d %d", &num_monster, &side);
    for (int i = 0; i < num_monster; i++) {
        fscanf(input, "%d %d", &monster[i][0], &monster[i][1]);
        if (boundaryMonster == -1 && monster[i][0] >= (1+2*side))
            boundaryMonster = i;
    }

    fclose(input);

    if (num_monster == 0) { 
        fprintf(output, "%d", 0); 
        fclose(output);
        return 0; 
    }

    half = 2*side;
    total = 4*side;

    oppSeq();

    int cur_sum = totalsum(1);
    int cur_monster = 0, cur_opp = 0;
    int prev_pos = 1;

    int delta = 0;
    for (int i = 0; i < num_monster; i++) {
        int mid = 1+half;
        if (monster[i][0] > 1 && monster[i][0] <= mid) 
            delta -= monster[i][1];
        else delta += monster[i][1];
    }

    if (monster[0][0] == 1) cur_monster = 1;
    if (opp[0][0] == 1) cur_opp = 1;

    int best = cur_sum;
    while (cur_monster < num_monster || cur_opp < num_monster) {
        if (cur_monster < num_monster && cur_opp < num_monster) {
            //going clockwise with both `monster` and `opp` *similar to merge sort merge phase
            if (monster[cur_monster][0] < opp[cur_opp][0]) {
                //update sum going from prev to cur_monster
                cur_sum += delta*(monster[cur_monster][0]-prev_pos);
                //start moving away from cur_monster->update delta
                delta += 2*monster[cur_monster][1];
                prev_pos = monster[cur_monster][0];
                cur_monster++;
            } else if (opp[cur_opp][0] < monster[cur_monster][0]) {
                cur_sum += delta*(opp[cur_opp][0]-prev_pos);
                //starting moving towards opposite monster
                delta -= 2*monster[ opp[cur_opp][2] ][1];
                prev_pos = opp[cur_opp][0];
                cur_opp++; 
            } else if (opp[cur_opp][0] == monster[cur_monster][0]) {
                cur_sum += delta*(monster[cur_monster][0]-prev_pos);
                //starting towards opp monster and away from current monster;
                delta += 2*(monster[cur_monster][1] - monster[ opp[cur_opp][2] ][1]);
                prev_pos = monster[cur_monster][0];
                cur_opp++; cur_monster++;
            }
        } else if (cur_monster < num_monster) {
            cur_sum += delta*(monster[cur_monster][0]-prev_pos);
            delta += 2*monster[cur_monster][1];
            prev_pos = monster[cur_monster][0];
            cur_monster++;
        } else {
            cur_sum += delta*(opp[cur_opp][0]-prev_pos);
            delta -= 2*monster[ opp[cur_opp][2] ][1];
            prev_pos = opp[cur_opp][0];
            cur_opp++; 
        }
        if (cur_sum > best) best = cur_sum;
    }

    fprintf(output, "%d", best);
    fclose(output);

    return 0;
}

---

Here is a brief explanation for the code above:

• We have a sequence of monsters' positions: e.g. 2 4 11 12

• Function oppSeg() generates a sorted sequence of positions opposite to that of the monsters in O(N) time by going through the monsters clockwise starting with monsters in the second half of the shape (start with boundaryMonster found in input loop)
  e.g. we obtained the sequence: 5 6 8 10

Here are the main algorithm after the oppSeq() function in main():

• Put the hero at intial position 1 and calculate the initial sum of weighted distance
• Calculate delta which is the change in the sum as the hero move 1 step clockwise
• It can be seen that delta only changes when the current position of the hero or his opposite position contains monsters.
• Going through the relevant positions (with monsters or monsters at opposite position) by using a procedure similar to the merging phase of merge sort on the monsters positions sequence and the opposite positions sequence
• update delta, cur_sum, best sum so far accordingly
• delta = 2*monster_strength__at_current_pos - 2*monster_strength_opposite_at_pos
  *start moving away from monsters at current position and towards monsters at opposite position in the next step
• cur_sum = (current_position - previous_position)*delta

The main part also takes O(N) time and the program uses O(N) space overall