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