0
$\begingroup$

This is the FinalTurn task of the Manganum 2017 challenge. This is the problem and I need to solve it in a timely and performance-efficient manner, which I have not been able to do so far:

A checker game on an infinite board between players A and B is in progress. There are two types of pieces in checkers: pawns and queens. Pieces can move only diagonally and forward. A queen can move any number of steps in one of these two directions. If there is a piece belonging to player B on the line of player A's queen's movement, player A can beat it by leaping over it and optionally passing some more empty fields. Player A can beat only one of player B's pieces in one move. After beating one of player B's pieces in this way, player A can continue his turn and make another move, but only if he can beat another piece. Player A gains 1 point for beating a pawn and 10 points for beating a queen. Player A is left with his last piece: a queen. Now it is A's turn − the last turn in the game. Player A wants to know the maximum number of points he can score in a single turn. Can you help?

$T is a string of N characters with pieces values. "p" and "q" represent player B's pawn and queen, and "X" represents player A's queen. Arrays $X and $Y are the x and y coordinates of pieces.

For example, given:

$X = [3, 5, 1, 6];
$Y = [1, 3, 3, 8];

$T = "Xpqp";

the function should return 10

Do you know a good DP (dynamic programming) algorithm that would find the solution for the problem efficiently? In my solution: -I used the buffer for already found maximum possible scores for individual fields, so I don't do double checks.
-Also, I put all enemy (player B) pieces in a two dimensional array, for easier detection if there is enemy piece on a certain field (if [x][y] is not set, then there isn't).
-I am doing the check for each field that it didn't cross the border of no possibility of getting any more points (no more pieces to be beaten beyond this point), so there are three borderlines:
a) one that limits the height (if we are on the same level as the highest enemy piece, no use checking if any more can be beaten, because there isn't)
b) two borders that are left and right diagonal that form the imagined border angle.
Despite this, I only got 46% on the assessment online test.

$\endgroup$
  • $\begingroup$ This kind of problem screams dynamic programming. $\endgroup$ – Stella Biderman Dec 1 '17 at 4:46
  • 1
    $\begingroup$ @qvian I have flagged this post as in need of moderator intervention because it is a copy-and-paste of an on-going challenge problem. This is strictly forbidden on this website, and completely wrong. $\endgroup$ – Stella Biderman Dec 1 '17 at 15:18
  • 2
    $\begingroup$ @StellaBiderman It's good to point out that a question is an ongoing challenge problem, because some people don't wish to answer those. It would be more helpful to say what the challenge is and when it finishes. You may also want to report to the challenge organizers in case it's forbidden by their rules. But it is not forbidden by this site's rules. $\endgroup$ – Gilles 'SO- stop being evil' Dec 1 '17 at 17:57
  • 3
    $\begingroup$ This is part of the Magnum 2017 challenge. The rules say that you’re supposed to solve the problem in an uninterrupted and timed 120 minute session. The rules state that “During the test you should work on your own, you may not consult anyone.” $\endgroup$ – Stella Biderman Dec 1 '17 at 18:13
  • 1
    $\begingroup$ @VladimirDespotovic although having someone solve the problem is not against a strict interpretation of the exact wording, it is very clearly against the intent of the rules of the challenge. The reason why posing this is wrong is that it breaks the rules of the competition and gives you an unfair advantage. It also harms the competition as a whole to have the solution easily findable online. Finally, when you submit the solution you’re representing it as your own work. In my mind, copying a solution or the fundamental idea of a solution without attribution in this way is plagiarism. $\endgroup$ – Stella Biderman Dec 1 '17 at 18:15
2
$\begingroup$

Some hints since I can't comment: I'd suggest trying to rotate the board by 45 degrees. Then your problem essentially reduces to your queen going right/upwards. The rest can then be solved with Segment Tree or Treap.

$\endgroup$
  • 1
    $\begingroup$ Now that I googled the statement, isn't this part of an ongoing challenge? $\endgroup$ – qvian Dec 1 '17 at 15:11
  • $\begingroup$ Yes. I am waiting for administrator's decision on whether I should remove the question or not. I didn't know I shouldn't give bounty if question is "in an ongoing challenge" .... $\endgroup$ – Vladimir Despotovic Dec 1 '17 at 17:09
  • 1
    $\begingroup$ @VladimirDespotovic waiting for administrator's decision there is moderation. $\endgroup$ – greybeard Dec 3 '17 at 8:56
  • $\begingroup$ No problem. I wait for someone who will give a good answer so I can give him the bounty and close the question. $\endgroup$ – Vladimir Despotovic Dec 5 '17 at 3:47
2
+50
$\begingroup$

If you want to try the challenge yourself first, please don't read further

From what you described I believe your solution to be correct, but with too bad time/space complexities. Of course there might be some implementation errors/typos, bad memory handling or any of the million problems that are so popular on StackOverflow.

Worst case space complexity should be O(N) so you cannot use your 2D array for the lookup of pieces. You can instead use other container, e.g. map (O(log(N)) lookup)(or hash map if you really want to keep at least the O*(1) complexity) with pair of integers for keys or don't use anything at all, since finding if a set of coordinates contains a piece is trivially O(N) thus not hurting our asymptotic complexity.

Your worst case time complexity depends on implementation details you did not share. Specifically after you take a piece, what positions you try to compute, if you compute all possibilities from the spot right behind enemy piece all the way to the border the complexity gets really bad and is not even dependand on N. After each jump you need to precompute the positions where you can jump and still continue getting pieces and check only those. Furthermore you should not do this for all pieces, because you can have some arrays where you have sorted the pieces based on right/left diagonal, thus knowing, which are already unattainable (are behind you at any given point). You also need to realize that if you decide to jump for example to right, all points on this diagonal between two pieces have the same possible value in that direction.

I must say I am not completely sure about the time complexity being O(N*log(N)) and proof might be beyond my abilities, but I believe it might be.

I would also advise you to use the visualisation qvian propses in his answer. Note though that Segment Trees have spacial complexity O(n*log(n)). I am not familiar with Treaps so I cannot comment on those.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.