What would be simplest naive solution?

I tried swapping knights one by one, using simple bfs to find paths between 2 knights. It passed most tests except one. (Then my laptop battery was running out, I was panic and submitted dozens of times without passing :D)

For me the biggest challenge with the approximation problem was to get my solution Accepted on all the tests :) First of all, I should say that I think the constraints for the placement of the knights were not satisfied. The statement says that white knights are at positions (i,j) with j <= N/2 and black knights at positions (i,j) with j>N/2. I initially had a solution which tried to slightly take advantage of this, but kept failing. I added some asserts and noticed that the coordinates didn't match the condition from the problem statement. After that I switched to considering that the knights could be placed anywhere on the board (maybe even mixed among themselves) and I was able to get my first Accepted solution.

Now, about the idea: I repeatedly chose two knights (a white one and a black one) and swapped them.

I will discuss first about the swapping strategy. I ran a BFS from the white knight and allowed it to pass only through empty cells or cells with other white knights (passing through a cell with another white knight meant that, actually, the other knight would continue the journey towards the destination). I also made sure that the path contained at least one empty cell (to be able to make some moves — this may not be very important except in some very special cases). Then I chose a neighbor of the black knight with the lowest BFS distance and made moves until a white knight reached that neighbor. Note that this means that now the original position of the white knight is empty. I then ran BFS from the black knight and moved it along the shortest path to the original position of the white knight (allowing it to pass through empty cells or cells occupied by other black knights). Finally, I finalized the moves of the white knights — I moved one white knight to the initial position of the black knight (now empty) and all the other knights whose movements were "stuck" because this white knight didn't go all the way in the first pass. Using a full BFS lead to TLE on 6-7 test cases, so I used a heuristic. Whenever the distance of a cell was "too far" from the target, I wouldn't add that cell to the BFS queue. I defined "too far" if the number of moves to the cell + the Manhattan distance from the cell to the target was larger than the Manhattan distance from the source to the target plus some slack. This made things sufficiently fast to pass all tests.

Regarding the strategy for picking a pair of white and black knights to swap, I actually tried several, as long as time permitted. The first one simply iterated through the matrix in row-major order and picked the first white and the first black knights (with an extra condition that they shouldn't be "very close", since I was getting WA on a test case without this). If time permitted, I tried other strategies — iterating in order of decreasing rows — increasing columns, decreasing rows — increasing columns, picking pairs of knights randomly, etc.

My score during the contest was 51150, but there, in the swapping strategy, when moving the white knight towards the black knight I picked some random neighbor of the black knight instead of the one with the shortest BFS distance. I was planning to change this at some point, but in the end I forgot about it :) I remembered about it some time after the contest, made the change to pick the neighbor with the smallest BFS distance and resubmitted for practice — the new score was 50298, which is about 1.6% better than my winning score during the contest. I'm glad this silly oversight didn't cost me the victory, since the runner-up was pretty close.

I'm certain much smarter approached could have been tried at this problem — at the very least some min cost — perfect matching algorithm could have been used for pairing white and black knights for swapping. If min-cost perfect matching were too slow, then perhaps something close to it but faster could have been used. I would have liked to try something like this, but didn't have enough time. I was visiting some relatives during the first 6 hours of the contest and then, somewhere between the 9h and 10h mark I received a visit myself. So I didn't have too much time to try very smart solutions for pairing knights. So I chose a greedy-based pairing. Nevertheless, I think that what was important for this problem was to completely separate the pairing strategy from the swapping strategy. This way, after getting an initial solution accepted, I could update them independently (e.g. like trying multiple pairing strategies within the time limit).

Finally, I would like to mention again that the reason for which I participate in these Hackerearth monthly "clashes" is the fact that they have an approximation problem — I really like challenge/approximation problems :) This month's problem was more difficult even to get Accepted than last month, but I still enjoyed it quite a lot (even if it was a bit stressful, with my first Accepted solution being, if I remember well, less than 1h before the end of the contest).

I had less than an hour to spend on approximate problem and seeing that there is just one passing submission and few people trying hard to get any score was intimidating. So my only goal was to code a passing solution. Approach was to move all black knights one turn in random direction, then for each white knight check if there are reachable initial black knight positions and move to the nearest one using BFS, then do the same for black knights, if some knights weren't in correct positions after that, repeat BFS for them. Tests were gracious enough so that my solution always worked, 7.5s out of 8s time limit worst case though, so I consider myself lucky :)

If I recall correctly this was the first time when approximate problem used non-linear scoring function, allowing all tests have more or less same weight in the total score, so kudos for that and it always should be done like this.

All in all, it was a great contest with diverse and fun problem set (Frames is my favourite). Thanks to everyone involved.

Thanks a lot for the feedback. We will disable these emails when the contest is running.

Thanks again!

Check those problems in practice area — if you are looking at some problem in a contest, at the top there is a link which leads to same problem in practice area, and at that page you may switch to editorial.

Yes, we will ask for your address.