Log inSign up
Problems / A021

Placing the knights

300 ptsCases 14Set by dongbinna
Added October 30.
1 solved1 attempted1 submissionssolvers took 1.0 tries on average

Statement

K knights are placed on an N×N board, and you want to rearrange their positions to score as high as possible. Each knight can stay where it is or move to one of 8 positions relative to its current position. Every knight may move at most once, and no knight may leave the board. Also, after the rearrangement no single position (cell) on the board may hold two or more knights.

On the starting board, every position holding a knight is marked 0. Every place without a knight is marked with a number greater than 0, which stands for a score. A score is always a natural number from 1 to 100. When a knight moves onto a cell that holds a score (a cell with a number greater than 0), it gains that value as score. As noted above, each knight may move from its starting position to one of 8 positions if it wants to, and it moves the same way a knight moves in chess or in janggi (Korean chess).

Write the position of each cell on the board as (row, column), and assume indices start from 0. When one knight is at position (3, 3), the positions it can move to are drawn below. Specifically, it can move to (1, 2), (1, 4), (2, 1), (2, 5), (4, 1), (4, 5), (5, 2) and (5, 4). In the figure below, the 8 shaded positions are the ones it can move to.

●●
●●
0
●●
●●

The table above is a grid of 7 rows and 7 columns with the knight (0) at (3, 3). In the original, the 8 reachable positions were marked only by shading, so no cell values survived the text extraction. The list of positions written in the body has been copied over unchanged and marked with ●.

Next, assume a situation with N=7 and K=3. In the grid below, the positions holding knights are shaded.

2065784
5778745
8596596
7945087
9859788
7074374
7995843

As noted above, when a knight moves it gains score equal to the number written on the position it moved to. Our goal is to place the knights well and make the sum of the scores as large as possible. In this example, if the knight at (0, 1) moves to position (1, 3), the knight at (3, 4) moves to position (2, 2) and the knight at (5, 1) moves to position (4, 3), the total comes to 8 + 9 + 9 = 26. Taking every possible case into account, this is the maximum score that can be obtained.

The figure below shades in red the positions the knights reach to get that maximum possible score.

2065784
5778745
8596596
7945087
9859788
7074374
7995843

Again, with 3 knights at positions (0, 1), (3, 4) and (5, 1), suppose this time they move to positions (0, 1), (1, 5) and (6, 3). The knight at position (0, 1) did not move and chose to stay where it was. In this case the total score is 0 + 4 + 5 = 9, so only 9 points can be obtained. As this shows, the score you can obtain changes greatly depending on how each knight's position is chosen.

2065784
5778745
8596596
7945087
9859788
7074374
7995843

So, given the board, write a program that returns the maximum sum of scores that can be obtained by placing the knights well.

Input and Output Examples

Example 1

Input

7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]

Output

26

Input

  • First the board size N is given as a natural number. N is a natural number from 5 to 30.

  • Next, the number of knights K is given as a natural number. K is a natural number from 3 to 7.

  • After that, an array board holding the N×N board information is given. On the starting board every position holding a knight is marked 0, and a score is always a natural number from 1 to 100.

Output

  • Place the K knights well and return the maximum sum of scores that can be obtained, as a natural number.

Requirements

  • You must write a solution(N, K, board) function and return the answer
  • Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
  • The languages you can use are Python and JavaScript
  • The memory limit is 256MB. The browser does not measure it, it only states it
  • The time limit is set by measuring the setter's reference solution on the same runtime
  • On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
  • The output has to match the expected value down to the character. A space inside a line counts the same as any other character.
  • There are 14 cases, and 4 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
  • You have to pass all 14 cases to solve this.
Read the requirements carefully before solving. Tampering with the grading to make a submission look like a pass can get you sanctioned if caught. The code you submit is published on the leaderboard along with the result.

Examples

4 public cases. Judging also uses hidden cases. You have to pass all 14 cases to solve this.

Input
Expected output
7, 3, [[2, 0, 6, 5, 7, 8, 4], [5, 7, 7, 8, 7, 4, 5], [8, 5, 9, 6, 5, 9, 6], [7, 9, 4, 5, 0, 8, 7], [9, 8, 5, 9, 7, 8, 8], [7, 0, 7, 4, 3, 7, 4], [7, 9, 9, 5, 8, 4, 3]]
26
18, 3, [[35, 39, 93, 56, 5, 42, 68, 55, 56, 6, 73, 4, 71, 2, 51, 21, 37, 86], [40, 58, 20, 16, 52, 62, 0, 86, 23, 80, 5, 93, 70, 68, 12, 65, 95, 87], [38, 77, 11, 56, 5, 11, 85, 18, 78, 86, 2, 47, 95, 93, 77, 56, 83, 88], [11, 64, 88, 71, 93, 64, 50, 25, 9, 46, 61, 50, 10, 89, 38, 8, 79, 58], [94, 2, 6, 18, 40, 60, 13, 82, 3, 37, 88, 15, 79, 92, 22, 30, 45, 58], [10, 75, 59, 41, 36, 92, 56, 77, 12, 91, 69, 5, 38, 11, 58, 95, 0, 43], [76, 20, 27, 3, 59, 24, 76, 18, 30, 17, 53, 95, 96, 12, 26, 88, 15, 21], [39, 84, 12, 65, 27, 61, 83, 8, 75, 64, 83, 80, 23, 31, 60, 21, 45, 93], [60, 10, 29, 32, 68, 99, 1, 100, 1, 14, 85, 45, 98, 48, 43, 92, 81, 51], [20, 89, 90, 47, 42, 0, 37, 5, 11, 54, 40, 4, 12, 69, 96, 77, 49, 14], [54, 85, 39, 43, 38, 26, 7, 86, 57, 33, 4, 50, 2, 46, 11, 79, 22, 76], [50, 33, 58, 41, 19, 23, 52, 45, 22, 37, 70, 93, 84, 97, 74, 86, 99, 24], [44, 83, 76, 33, 29, 35, 84, 98, 96, 70, 31, 40, 60, 3, 59, 100, 85, 74], [29, 26, 81, 69, 15, 34, 40, 7, 51, 50, 80, 13, 4, 69, 18, 64, 99, 97], [39, 100, 2, 19, 72, 4, 8, 11, 70, 29, 33, 91, 36, 89, 88, 23, 94, 30], [37, 16, 73, 9, 72, 43, 74, 21, 59, 60, 2, 72, 99, 96, 47, 2, 91, 68], [9, 35, 82, 26, 41, 56, 74, 94, 65, 73,

... cut off here (1,305 chars in total)
271
25, 7, [[52, 57, 36, 63, 3, 34, 44, 62, 2, 22, 50, 51, 13, 53, 93, 90, 22, 36, 33, 68, 40, 97, 72, 36, 28], [44, 13, 26, 79, 13, 34, 25, 6, 64, 65, 10, 56, 41, 87, 65, 95, 64, 70, 58, 83, 22, 67, 68, 88, 64], [74, 23, 29, 12, 47, 16, 47, 43, 91, 53, 20, 7, 15, 82, 58, 40, 35, 19, 90, 75, 42, 47, 39, 22, 19], [26, 18, 67, 64, 96, 15, 93, 38, 70, 5, 68, 74, 81, 92, 97, 27, 46, 31, 1, 86, 7, 0, 56, 44, 54], [66, 50, 8, 78, 61, 31, 50, 21, 27, 46, 89, 13, 20, 75, 65, 13, 76, 39, 60, 26, 90, 35, 73, 93, 16], [35, 66, 50, 58, 32, 96, 41, 81, 88, 100, 15, 2, 71, 23, 72, 1, 98, 92, 72, 45, 27, 82, 27, 63, 19], [17, 10, 61, 38, 34, 13, 82, 33, 62, 36, 57, 96, 21, 87, 51, 73, 37, 65, 58, 99, 51, 39, 87, 91, 51], [41, 23, 63, 81, 4, 78, 1, 74, 69, 89, 90, 82, 72, 97, 91, 6, 41, 8, 88, 11, 0, 38, 85, 97, 0], [99, 56, 15, 60, 35, 91, 89, 3, 56, 78, 85, 67, 20, 52, 7, 61, 42, 63, 74, 60, 82, 11, 80, 31, 21], [80, 87, 65, 16, 98, 84, 32, 32, 19, 45, 35, 4, 64, 26, 67, 71, 30, 3, 55, 81, 53, 97, 62, 78, 42], [59, 48, 86, 44, 84, 26, 6, 10, 62, 24, 84, 46, 80, 9, 11, 78, 65, 83, 58, 52, 30, 60, 68, 73, 36], [6, 71, 25, 52, 37, 40, 95, 24, 7, 79, 96, 93, 16, 13, 39, 92, 58, 98, 79, 17, 82, 84, 84, 6

... cut off here (2,511 chars in total)
613
26, 4, [[75, 87, 64, 64, 75, 64, 96, 17, 11, 27, 38, 19, 46, 88, 64, 72, 11, 66, 93, 89, 52, 60, 18, 98, 6, 31], [47, 17, 4, 39, 21, 72, 88, 79, 53, 20, 36, 30, 88, 46, 64, 98, 27, 53, 39, 31, 36, 84, 70, 50, 56, 96], [15, 27, 14, 81, 19, 66, 63, 70, 78, 80, 92, 61, 36, 82, 97, 83, 50, 38, 94, 64, 89, 78, 72, 79, 61, 65], [79, 95, 59, 52, 97, 7, 64, 26, 28, 21, 48, 76, 36, 48, 89, 48, 86, 86, 69, 55, 29, 4, 100, 31, 66, 22], [42, 67, 23, 80, 56, 90, 54, 76, 64, 3, 44, 61, 16, 82, 88, 84, 81, 20, 49, 32, 20, 44, 83, 40, 48, 33], [79, 93, 1, 12, 52, 50, 9, 25, 78, 69, 40, 16, 79, 15, 96, 11, 58, 90, 99, 81, 2, 22, 16, 65, 8, 80], [0, 32, 51, 9, 81, 2, 18, 37, 31, 75, 68, 94, 68, 63, 68, 48, 99, 28, 94, 52, 85, 41, 67, 33, 5, 6], [24, 35, 79, 36, 53, 83, 99, 59, 95, 77, 63, 31, 23, 82, 53, 65, 51, 79, 89, 21, 50, 44, 49, 97, 25, 78], [87, 3, 66, 57, 96, 3, 71, 9, 85, 96, 34, 43, 47, 80, 7, 31, 58, 13, 21, 76, 40, 34, 6, 47, 69, 20], [56, 26, 55, 46, 19, 27, 70, 47, 80, 85, 66, 97, 42, 62, 84, 73, 13, 76, 50, 76, 72, 15, 56, 12, 32, 59], [37, 32, 21, 72, 100, 92, 92, 9, 51, 83, 83, 22, 33, 23, 58, 0, 64, 30, 89, 94, 47, 33, 87, 97, 91, 68], [49, 85, 39, 25, 79, 41, 12, 43, 31, 78, 62, 

... cut off here (2,708 chars in total)
340

Notes

Background that helps with solving. The rules you have to follow are in the input and output specs and the requirements above.

This is problem 3 of practice test 7 in the original.

Solution

Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.

0 chars1 lineMemory 256MB (recorded only)Reference 1.38s

Submitting requires you to log in. Running against the public cases works without one.

You can test with 4 public cases. Submitting runs the hidden cases too.

People who solved this problem

The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.

1bampal22ms1001 charsPythonWindows NT 10.0 / Chrome/156.0.0.0 / 8코어 / 16GB

Input read time 7ms (excluded from the ranking)

Log in and you can see the code once you solve this problem.