Problem Statement |
| | You will lead a group of knights into a dungeon to rescue some princesses and to kill some monsters while you're at it. Unfortunately, the dungeon is fairly old and not equipped with proper surveillance and communication systems, so while the knights are inside they don't get updates on locations of princesses and monsters. You have to come up with a way to accomplish your mission with the scarse information you have!
The dungeon is an SxS grid of rooms, in which all pairs of horizontally or vertically adjacent rooms have doors between them. Four rooms at the corners of the dungeon are entrances/exits.
Before your team enters the dungeon, you get information about the starting locations of princesses and monsters. After that, you choose which knights to send to each of the entrances, and the mission begins.
The simulation works as follows. It consists of at most S^3 turns, and each turn consists of the following phases:
-
Knights move to adjacent rooms or stay in their current rooms per your instructions (see Implementation section).
-
Princesses move: if a princess is escorted by a knight, she follows that knight's movement, otherwise she moves to an adjacent room or stays in her current room randomly.
-
Monsters move to adjacent rooms or stay in their current rooms randomly. During the movements no interaction occurs: if two characters swap rooms, or one character enters a room while the other one is leaving, they don't see each other.
-
Princesses and knights who are in exit rooms leave the dungeon. They can not reenter it at a later time. The monsters can not use exits. If two characters end their moves at the same exit, they don't interact, since they leave the dungeon before they can interact.
-
Knights fight monsters in each room where they encounter each other. If there are A knights and B monsters in the room, the fight between them is simulated step-by-step. At each step, either a knight or a monster dies; a knight dies with probability B/(A+B), otherwise a monster dies. After the character to die is chosen, the values of A and B are updated, and the process is repeated. The fight stops when either all knights in the room are dead or all monsters in the room are dead. Each time a knight has to die, the knight with the highest index in the room dies.
-
Monsters kill princesses in each room where they encounter each other (after the previous step monsters stay in the room only if all knights are eliminated).
-
The knight with the lowest index in the room starts escorting all the princesses in that room. If a princess was previously escorted by a knight with a higher index, she is transferred.
The simulation will end early if all knights have left the dungeon.
Your goal is to lead as many princesses out of the dungeon and kill as many monsters as possible while losing as few knights as possible in the process. Note that any knights left in the dungeon after S^3 turns are considered to be lost!
Example
An animated example of a simulation is available.
Implementation
Your code has to implement two methods: initialize and move.
initialize(int S, int[] princesses, int[] monsters, int K) will be called once in the beginning of the simulation to give you the information about the dungeon:
-
S gives you the size of the dungeon.
-
princesses gives you the starting positions of the princesses. It will contain 2 * P elements, row and column coordinates (0-based) of the room in which princess i starts will be given by elements 2*i and 2*i+1, respectively. Multiple princesses can start in the same room.
-
monsters gives you the starting positions of the monsters, in the same format as princesses parameter. Multiple monsters can start in the same room. Monsters can start in the same room with princesses, though it is unlikely (in this case they don't interact until the first turn).
-
K is the number of knights prepared to descend in the dungeon.
The return from initialize is a String of length K which sends each of the knights to one of the entrances to the dungeon. It must contain exactly K characters, character i giving the index of the entrance for knight i to use. The entrances are numbered in clockwise order, starting with top left corner: '0' is top left corner, '1' is top right corner, '2' is bottom right corner, and '3' is bottom left corner.
move(int[] status, int P, int M, int timeLeft) will be called up to S*S*S times, once per simulation step. The input parameters to this method are:
-
status gives you the current status for each knight. status[i] gives the status of knight i and can have the following values:
-
0 for a live knight which is not escorting any princesses;
-
-1 for a dead knight;
-
-2 for a knight who left the dungeon;
-
x > 0 for a live knight which is escorting x princesses.
-
P and M give you the current total numbers of princesses and monsters in the dungeon, respectively. Note that changes to these numbers is the only way for you to get information about princesses dying or leaving the dungeon or monsters dying in fights with the knights.
-
timeLeft gives the number of milliseconds left of the time limit for your solution to use.
The return from move is a String which gives the list of commands for the knights to follow. It must contain exactly K characters, character i giving instruction for knight i. Possible instructions are:
-
'N' to decrement row coordinate,
-
'S' to increment row coordinate,
-
'W' to decrement column coordinate,
-
'E' to increment column coordinate,
-
any other character to stay in place.
The knight will also stay in place if following the instruction would take it outside of the dungeon limits (but not in one of the exit rooms). If the knight is already outside of the dungeon or dead, his instruction will be ignored.
Scoring
The raw score for a test case is the number of points you get. You get 1 point for each monster killed by the knights and 100 points for each princess escorted out of the dungeon (if a princess escapes on her own, you don't get points for this), and you lose 5 points for each knight killed by the monsters or left in the dungeon at the end of simulation. You don't lose points for princesses killed by the monsters or left in the dungeon. If your return had invalid format, or your solution crashed or timed out, your raw score for that test case is -10^9.
Your overall score will be calculated as follows. For each test case where your score is not -10^9, you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is greater 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.
Tools
An offline tester is available here. You can use it to test/debug your solution locally. Please refer to its source code for exact implementation of test case generation and simulation. That page also contains links to useful information and sample solutions in several languages. |
| |
Definition |
| | | Class: | PrincessesAndMonsters | | Method: | initialize | | Parameters: | int, int[], int[], int | | Returns: | String | | Method signature: | String initialize(int S, int[] princesses, int[] monsters, int K) | | | | Method: | move | | Parameters: | int[], int, int, int | | Returns: | String | | Method signature: | String move(int[] status, int P, int M, int timeLeft) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | The time limit is 20 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing. |
| - | The match is rated. |
| - | Top-5 participants and 5 random participants (based on final standings) will win a Topcoder T-shirt. |
| |
Constraints |
| - | The size of the dungeon S will be between 10 and 50, inclusive. |
| - | The number of knights K will be between 20 and 100, inclusive. |
| - | The number of princesses P will be between S/5 and S, inclusive. |
| - | The number of monsters M will be between S and S*S/5, inclusive. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
Dungeon size = 10
Number of princesses = 10
Number of monsters = 10
Number of knights = 20
" | |
|
| 1) | |
| | | Returns:
"seed = 2
Dungeon size = 50
Number of princesses = 50
Number of monsters = 500
Number of knights = 100
" | |
|
| 2) | |
| | | Returns:
"seed = 3
Dungeon size = 18
Number of princesses = 4
Number of monsters = 58
Number of knights = 74
" | |
|
| 3) | |
| | | Returns:
"seed = 4
Dungeon size = 21
Number of princesses = 5
Number of monsters = 39
Number of knights = 65
" | |
|
| 4) | |
| | | Returns:
"seed = 5
Dungeon size = 39
Number of princesses = 37
Number of monsters = 162
Number of knights = 68
" | |
|
| 5) | |
| | | Returns:
"seed = 6
Dungeon size = 43
Number of princesses = 10
Number of monsters = 332
Number of knights = 77
" | |
|
| 6) | |
| | | Returns:
"seed = 7
Dungeon size = 14
Number of princesses = 12
Number of monsters = 28
Number of knights = 28
" | |
|
| 7) | |
| | | Returns:
"seed = 8
Dungeon size = 27
Number of princesses = 18
Number of monsters = 115
Number of knights = 35
" | |
|
| 8) | |
| | | Returns:
"seed = 9
Dungeon size = 30
Number of princesses = 7
Number of monsters = 45
Number of knights = 44
" | |
|
| 9) | |
| | | Returns:
"seed = 10
Dungeon size = 25
Number of princesses = 23
Number of monsters = 112
Number of knights = 33
" | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.
