| | You are playing an abstract wargame against one or several AI opponents. The landscape is represented by a plane which contains B bases at the given points. Each base is occupied by a certain number of units and is controlled by one of the players.
The players can perform only one kind of action: pick a base controlled by this player, create a troop of half of the units which occupy that base and send this troop to another base. The troops move in a straight line between their base of origin and target base and don't interact with any other entities they might encounter on the way. Upon troop arrival to the target base, one of two scenarios occurs. If the target base is controlled by the same player as the troop, the units of the troop join the units of the base. If the target base is controlled by a different player, a battle occurs, in which either the units of the base win and eliminate the troop or the troop overpowers the base and the base changes ownership.
Your task is to maximize the percentage of units controlled by you throughout the game (see Scoring section for an exact definition).
Implementation
Your code should implement two methods init and sendTroops.
Method init(int[] baseLocations, int speed) will be called once before the simulation starts.
-
baseLocations gives you the locations of the bases on the plane. If there are B bases, baseLocations will contain 2*B elements, and the i-th base will have coordinates (baseLocations[2*i], baseLocations[2*i+1]).
-
speed gives you the speed of troop movements. If the distance between the base of origin and the target base is D, and the troop is created at time step T, it will arrive to the target base at time step T+ceil(D/speed).
-
You can return any int from init method, it will be ignored.
Method sendTroops(int[] bases, int[] troops) will be called once on each simulation step.
-
bases gives you information about the current state of the bases. It will contain 2*B elements: bases[2*i] will give the index of the player who controls the i-th base, and bases[2*i+1] will give the number of units occupying the i-th base.
-
Your index is 0, and AI indices are 1 through the number of opponents.
-
troops gives you information about the troops which are moving between bases. If there are M troops, troops will contain 4*M elements: troops[4*i] will be the index of the player who controls the i-th troop, troops[4*i+1] will be the number of units in the i-th troop, and the i-th troop will have coordinates approximately (troops[4*i+2], troops[4*i+3]).
-
You must return a int[] representing the troops you intend to create on this step. If you want to create N troops, your return must contain 2*N elements, i-th troop will be created at base with index ret[2*i] and will target base with index ret[2*i+1]. The troops are created in the order in which they are listed in return: if several troops are created on the same base on the same time step, the first troop will have half of the base's units, the second troop - half of the units left after the first troop departed, etc.
-
You can create at most B new troops on each step (B is the total number of bases on the map) regardless of how many bases you control. Source and target bases for each troop must be different. Source bases must be controlled by you. Note that as long as your return contains an even number of integers less than or equal to 2*B, it will be considered valid, and each individual action of creating a troop will be ignored if it is invalid.
You can use Server.getRemainingTime library method to get the remaining time in milliseconds. This is the time that was left before your solution was called last, and the result will only change when sendTroops method is called again. You can pass any integer to this method. Please note that there is some overhead in calling this method which will be part of your 15 seconds time limit. It is advised not to call this method within every sendTroops call.
Simulation
There will be 2000 simulation steps for each test case. Each simulation step consists of the following stages:
-
The step starts.
The number of units on each base which has at least one unit is increased depending on growth rate for that base and the current number of units on it: an extra (growthRate + numberOfUnits / 100) units are added. If the number of units on any base exceeds 1000, it is reduced to 1000. Coordinates of troop positions are updated based on their progress towards their target bases: an exact position is rounded down to the nearest integer coordinates.
-
The troops which are going to arrive to their target bases on this step arrive (in the same order as they were created).
The units of the troop either join the units of the base (if controlled by the same owner) or fight them (if controlled by a different owner). Each player has a "strength" of a unit: your units have strength of 1.0, and AI units have random strength between 1.0 and 1.2. The "strength" of troop/base is defined as (the number of units in it) * (the strength of the player's unit). If the strength of the base is greater than or equal to the strength of the troop, the base wins and loses the minimal number of units that has combined strength greater than or equal to the strength of the troop; otherwise, the troop wins, occupies the base and loses units following the same rule. If the number of units on any base exceeds 1000 at any point of time, it is reduced to 1000.
-
Each player receives information about the bases/troops and creates new troops.
Note that the troops are created in increasing order of player indices but all players get the same information about the troops/bases which doesn't include troops created on this step by players with smaller indices.
-
The player's score is updated.
On each step you get (number of units in bases/troops controlled by you)/(total number of units in all bases/troops) points. If at some step you control all units in the world or control none of them, the simulation stops, and you get the points for the rest of the steps (1 or 0 per step, respectively) without going through simulation.
-
Please see visualizer source code for AI strategy and the exact implementation of simulation.
Scoring
Your score for an individual test case will be the sum of (number of units in bases/troops controlled by you)/(total number of units in all bases/troops) values over each of the 2000 simulation steps. If your return has invalid format, your score for the test case will be -1.
Your overall score will be calculated in the following way: for each test case where your score is not -1, you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is larger than this competitor's score) and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1), then multiplied by 1000000 and divided by the number of test cases.
Test Case Generation
-
The number of the bases B is selected between 20 and 100, inclusive.
-
The coordinates of each base are selected between 1 and 598, inclusive, so that no two bases have same coordinates.
-
For each base the starting number of units on it is selected between 1 and 10, inclusive.
-
For each base the growth rate is selected between 1 and 3, inclusive.
-
Movement speed speed is selected between 1 and 10, inclusive.
-
The number of opponents NOpp is selected between 1 and 4, inclusive.
-
For each base the player who controls it initially is selected between 0 and NOpp, inclusive.
-
All values are chosen uniformly and independently, at random.
-
Please see visualizer source code for the exact implementation of test case generation.
Tools
An offline tester/visualizer is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation, simulation and score calculation.
|