My approach to INMAT was to use a ‘quad search’, which is a two-dimensional version of a binary search, where we search recursively one quadrant at a time. This took only a maximum of 0.04 seconds per test to earn 60 points. I expect that it took more than 4000 queries in some of the later test cases.
It looks as if the method needs polishing somehow, to reduce the number of queries.
Here is my code https://www.codechef.com/viewsolution/19740240
We still have to find gcd of some x^n and |a-b|. How does this make it simpler? We still need to use the gcd(a, b) = gcd(b, a % b) property.
I’ll share my (partial) solution for princess and dragons that helped me get AC on sub-tasks 0,4,6,8.
You start by reverse sorting the strength array, and define the largest value as the anchor. For each i, let the dragon with the anchor strength be at the ith position.
For P <= anchor, output is n for each i. Similarly for sum-over-strengths < anchor, output is 0 for each i.
For other non-trivial cases you iterate over the reverse sorted strength array trying to form two groups of sets such that the sum of strengths in each group when added to the anchor is just larger than P. We do this such that the size of the first set is <= size of the second set. Here again we have two cases : (1) We are able to get both sets, (2) we are able to get only one set. Other cases are eliminated by the two trivial cases on the above paragraph. We should aim to find set 1 and set 2 such that they have minimum size, while their sum being larger than P.
For case (1): We keep the set 1(that has the smaller size) on such a side of the ith position that allows it protects maximum dragons after it. Hence, we keep the smaller set on the larger side(if it fits there). We then try to adjust the larger set after it, either on the smaller side or the larger side.
For case (2): We keep set 1 on the larger side of the ith position, again so that it protects maximum positions. If that is not possible we return a string of n 0’s.
There are other subtleties too, such that the last element of the first set should be chosen such that the sum just equals P, and that we don’t waste strength that can be used in set 2.
Although this approach works for larger test-cases, it couldn’t even clear the smaller sub-tasks and hence I think I’m missing some conceptual point here that was tested in some test cases.
You can check my final code here : https://www.codechef.com/viewsolution/19707035
Thank you @john_smith_3 . I converted your comment to answer so that proper credit can be given to it 
Thanks for pointing it out.
That shouldn’t be a problem earlier too since input was only till 14 edges and a single case was there.