https://stackoverflow.com/questions/18102245
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianI will try to point out a strategy that you can follow to achieve the required 1 second response time. Of course, it must be implemented to ensure it fits this requirement.
The solution relies on the following fact:
Basically, given the sum of weighted distance WP for a position P, each monster will contribute to the sum of weighted distances of a P neighbor by adding or subtracting 1 time it strength to WP. The strength is added if the neighbor is nearer to the monster than P or subtracted if it is farther.
With this fact in mind, the solution resides in compute sum of weighted distance for some initial position on a initial step, and compute the sum of weighted distance for the other positions based on the value previously computed for its neighbor.
Besides compute the value for the initial position, we must define on the initial step:
- a direction (eg. clockwise) on which we will traverse the positions to compute the sum of weighted distances
- the sum of the strenght (SADD) of the monsters which we will get farther (to add) when traversing on the defined direction;
- the sum of the strenght (SSUB) of the monsters which we will get nearer (to subtract) when traversing on the defined direction;
Then, starting on the neighbor of the initial position, we traverse all position on the defined direction, and for each one, we update SADD and SSUB (when we traverse the circular path, some monster that were getting nearer starts to get farther and vice versa) and add (SADD - SSUB) to the value computed for the previous neighbor.
Thus, we can compute the sum of weighted distances for all positions without having to iterate over all monsters for each position.
I implemented an initial version of the solution in Java.
The following class represents a monster:
class Monster {
private long strenght;
private int position;
// omitting getters and setters...
}
And the following class represents the square side positions:
class SquareSidePositions {
private List<Monster>[] positionWithMosters;
private List<Monster> monstersOnSquareSides = new ArrayList<Monster>();
@SuppressWarnings("unchecked")
public SquareSidePositions(int numberOfPositions) {
positionWithMosters = new LinkedList[numberOfPositions];
}
public void add(int position, Monster monster) {
if (positionWithMosters[position] == null) {
positionWithMosters[position] = new LinkedList<Monster>();
}
positionWithMosters[position].add(monster);
monster.setPosition(position);
monstersOnSquareSides.add(monster);
}
public int size() {
return positionWithMosters.length;
}
public boolean hasMonsters(int position) {
return positionWithMosters[position] != null;
}
public long getSumOfStrenghtsOfMonstersOnThePosition(int i) {
long sum = 0;
for (Monster monster : positionWithMosters[i]) {
sum += monster.getStrenght();
}
return sum;
}
public List<Monster> getMonstersOnSquareSides() {
return monstersOnSquareSides;
}
}
And finally, the optimization is performed in the following method:
public static int findBest(SquareSidePositions positions) {
long tini = System.currentTimeMillis();
long sumOfGettingNearer = 0;
long sumOfGettingFarther = 0;
int currentBestPosition;
long bestSumOfWeight = 0;
long currentSumOfWeight;
final int numberOfPositions = positions.size();
int halfNumberOfPositions = numberOfPositions/2;
long strenghtsOnPreviousPosition = 0;
long strenghtsOnCurrentPosition = 0;
long strenghtsOnPositionStartingGetNearer = 0;
int positionStartGetNearer;
// initial step. Monsters from initial position (0) are skipped because they are at distance 0
for (Monster monster : positions.getMonstersOnSquareSides()) {
// getting nearer
if (monster.getPosition() < halfNumberOfPositions) {
bestSumOfWeight += monster.getStrenght()*monster.getPosition();
sumOfGettingNearer += monster.getStrenght();
} else {
// getting farther
bestSumOfWeight += monster.getStrenght()*(numberOfPositions - monster.getPosition());
sumOfGettingFarther += monster.getStrenght();
}
}
currentBestPosition = 0;
currentSumOfWeight = bestSumOfWeight;
// computing sum of weighted distances for other positions
for (int i = 1; i < numberOfPositions; ++i) {
strenghtsOnPreviousPosition = 0;
strenghtsOnPositionStartingGetNearer = 0;
strenghtsOnCurrentPosition = 0;
positionStartGetNearer = (halfNumberOfPositions + i - 1);
if (positionStartGetNearer >= numberOfPositions) {
positionStartGetNearer -= numberOfPositions;
}
// monsters on previous position start to affect current and next positions, starting to get farther
if (positions.hasMonsters(i-1)) {
strenghtsOnPreviousPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i-1);
sumOfGettingFarther += strenghtsOnPreviousPosition;
}
// monsters on current position will not affect current position and stop to get nearer
if (positions.hasMonsters(i)) {
strenghtsOnCurrentPosition = positions.getSumOfStrenghtsOfMonstersOnThePosition(i);
currentSumOfWeight -= strenghtsOnCurrentPosition;
sumOfGettingNearer -= strenghtsOnCurrentPosition;
}
// monsters on position next to a half circuit start to get nearer
if (positions.hasMonsters(positionStartGetNearer)) {
strenghtsOnPositionStartingGetNearer = positions.getSumOfStrenghtsOfMonstersOnThePosition(positionStartGetNearer);
sumOfGettingNearer += strenghtsOnPositionStartingGetNearer;
sumOfGettingFarther -= strenghtsOnPositionStartingGetNearer;
}
currentSumOfWeight += sumOfGettingFarther - sumOfGettingNearer;
// if current is better than previous best solution
if (currentSumOfWeight > bestSumOfWeight) {
bestSumOfWeight = currentSumOfWeight;
currentBestPosition = i;
}
}
final long executionTime = System.currentTimeMillis() - tini;
System.out.println("Execution time: " + executionTime + " ms");
System.out.printf("best position: %d with sum of weighted distances: %d\n", currentBestPosition, bestSumOfWeight);
return currentBestPosition;
}
To setup the input you used as example, you can use:
SquareSidePositions positions = new SquareSidePositions(12);
positions.add(1, new Monster(3));
positions.add(3, new Monster(1));
positions.add(10, new Monster(1));
positions.add(11, new Monster(2));
On a preliminary test, this method took 771 ms to execute, for 100,000 monsters and 200,000,000 possible positions, on a Intel Core i5-2400 running Windows 7.
I employed the following code to generate this input:
// I used numberOfMosters == 100000 and numberOfPositions == 200000000
public static SquareSidePositions initializeMonstersOnPositions(int numberOfMonsters, int numberOfPositions) {
Random rand = new Random();
SquareSidePositions positions = new SquareSidePositions(numberOfPositions);
for (int i = 0; i < numberOfMonsters; ++i) {
Monster monster = new Monster(rand.nextInt(10000)+1);
positions.add(rand.nextInt(numberOfPositions), monster);
}
return positions;
}
I hope it helps you!
