Given an NxM chessboard, you have a knight at some position and your opponent also has a knight, Find number of squares reachable to your knight in exactly K moves without being captured by opponent.There is no other piece other than 2 knights mentioned. You move first. Both players play optimally. Obvious solution would be to recursively try out each possibility for both knights but that would be too slow. Is there deterministic polynomial time solution ?

Given an array, we can generate an array which stores all the pairwise absolute difference of elements of original array. How can we find median of this new array. For example : A = {1,2,3,4} then we can generate difference array as G = {1,1,1,2,2,3} then median is 1.can it be done in better than quadratic time? Also what if we don't take absolute value of difference?

I observed that some of the coin sets for coin change problem(getting minimum number of change coins for given amount) gives same solution with dp solution and greedy solution. I was wondering what is necessary and sufficient condition for getting optimal solution using greedy approach?