Register
Submit a solution
The challenge is finished.

Challenge Overview

Challenge Forum : apps.topcoder.com/forums/?module=ThreadList&forumID=703392

Important Links

Please Note: the submission-review app will load a little slower than it usually does, but it will show up the details within 90 seconds(max). Also when you click on the artifacts section in the submission-review app it might initially show you an error message that you don't you have access - please stay on the same page for a while(90 seconds at max) and it will show up automatically.
  • Submission-Review You can find your submissions artifacts here. Artifacts will contain output.txt's for both example test cases and provisional test cases with stdout/stderr and individual test case scores. 
  • Other Details For other details like Processing Server Specifications, Submission Queue, Example Test Cases Execution etc.

Problem statement

Place chess pieces from C different players on a NxN board such that no piece of one player attacks any piece of another player. Note that pieces from the same player are allowed to attack each other. The chess pieces available are king, queen, rook, bishop and knight. Depending on its type, each piece gives it's player some predetermined number of points. Your task is to maximize the total number of points obtained by the lowest-scoring player. The board has walls which sliding pieces (queen, rook and bishop) cannot attack through (see attack rules below).

Here is a solution for seed=1 with N=8, C=4 and points=(8, 31, 18, 13, 4). Walls are shown as grey cells. The pieces of each player are shown in a different colour. This solution obtains a raw score of 83 since this is the score of the lowest-scoring players (3 and 4).

 

Implementation

Your code will receive as input the following values:
  • N, the size of the board.
  • C, the number of players.
  • NxN single-character lines describing the input grid, where line r*N+c represents the cell in row r and column c. Empty cells are '.' and walls are '#' (without the quotes).
  • 5 lines, each containing the points assigned for each piece, in the following order: king, queen, rook, bishop and knight.
Your code should write to output the following:
  • On the first line, 2xNxN - twice the number of cells in the grid.
  • NxN single-character lines describing the piece type of the output grid, where line r*N+c represents the cell in row r and column c. Cells should be one of the following characters (without the quotes):
    • '.' represents an empty cell of the input grid. You can only place chess pieces in these locations.
    • '#' represents a wall of the input grid. Walls cannot be added or removed.
    • 'K' represents a king.
    • 'Q' represents a queen.
    • 'R' represents a rook.
    • 'B' represents a bishop.
    • 'N' represents a knight.
  • NxN single-character lines describing the piece player id of the output grid, where line r*N+c represents the zero-based player id of the piece in row r and column c. The player id of empty ('.') and wall ('#') cells will be ignored.

Attack rules

We use classic chess attacking rules, modified to allow for walls. A piece cannot attack through a wall or a friendly piece:
  • A king can attack exactly one cell horizontally, vertically or diagonally.
  • A queen can attack any number of cells horizontally, vertically or diagonally until it reaches a wall or a friendly piece.
  • A rook can attack any number of cells horizontally or vertically until it reaches a wall or a friendly piece.
  • A bishop can attack any number of cells diagonally until it reaches a wall or a friendly piece.
  • A knight can attack one cell horizontally followed by two cells vertically, or one cell vertically followed by two cells horizontally.

Scoring

Your raw score for a test case is the total number of points obtained by the lowest-scoring player. If your return was invalid (pieces attacking enemy pieces, added/removed walls, invalid return length, invalid player id or invalid characters etc.) then your raw score on this test case will be -1.

If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is YOUR/MAX, where YOUR is your raw score and MAX is the largest positive raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is normalised to 100.

Test case generation

Please look at the visualizer source code for the exact details about test case generation. Each test case is generated as follows:
  • The grid size N is randomly chosen between 8 and 50, inclusive.
  • The number of players C is randomly chosen between 2 and 8, inclusive.
  • The wall probability wallP is randomly chosen beetween 0.15 and 0.65, inclusive.
  • Randomly place walls with probability wallP.
  • Generate points for each piece type:
    • King: randomly chosen between 3 and 8, inclusive.
    • Queen: randomly chosen between 3N and 4N, inclusive.
    • Rook: randomly chosen between 3N/2 and 5N/2 (integer division), inclusive.
    • Bishop: randomly chosen between N and 2N, inclusive.
    • Knight: randomly chosen between 2 and 8, inclusive.
  • All generated values are chosen uniformly at random.

Notes

  • The time limit is 10 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.
  • 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.

Languages Supported

C#, Java, C++ and Python
 

Submission Format

Your submission must be a single ZIP file not larger than 500 MB, with your Source Code only:
Please Note: Please zip only the file. Do not put it inside a folder before zipping, you should directly zip the file.

Make sure you name your Source Code file as MultiplayerChessPieces.<appropriate extension>

- Java Source Code - MultiplayerChessPieces.java
- C++ Source Code - MultiplayerChessPieces.cpp
- Python3.6 Source Code - MultiplayerChessPieces.py
- C# Source Code - MultiplayerChessPieces.cs

Sample Submissions

Tools

Submission format and an offline tester are available below. You can use it to test/debug your solution locally. You can also check its source code for an exact implementation of test case generation and score calculation. You can also find links to useful information and sample solutions in several languages.

DOWNLOADS

HELPFUL INFORMATION

OFFLINE TESTER / VISUALIZER

In order to use the offline tester/visualizer tool for testing your solution locally, you'll have to modify your solution by adding the main method that interacts with the tester/visualizer via reading data from standard input and writing data to standard output.

Here are example solutions for different languages, modified to be executed with the visualizer. They all implement the same approach:place kings such that they don't attack each other���. To run the tester with your solution, you should run: 
java -jar tester.jar -exec "<command>" -seed <seed>

Here, <command> is the command to execute your program, and <seed> is seed for test case generation. If your compiled solution is an executable file, the command will be the full path to it, for example, "C:\TopCoder\solution.exe" or "~/topcoder/solution". In case your compiled solution is to be run with the help of an interpreter, for example, if you program in Java, the command will be something like "java -cp C:\TopCoder Solution".

Additionally, you can use the following options:
  • -seed <seed>. Sets the seed used for test case generation, default is seed 1.
  • -novis. Turn off visualization.
  • -debug. Print debug information.
  • -size <cell size>. Use custom grid size, default is 20 pixels.

Finally, you can print any debug information of your solution to standard error, and it will be forwarded to the standard out of the tester.

ELIGIBLE EVENTS:

2020 Topcoder(R) Open

ID: 30104784