Kaosar and Grid (Editorial)

Problem Author: Al Kaosar Hussain

Prepared by: Al Kaosar Hussain

Solution:

Key observations:

A $90$ rotation permutes coordinates and flips signs, means if your are currently at $(x,y)$ then ccw $90$

degree rotation will be (-y,x) again $90$ degree rotation will be (-x,-y) so if we start at

(x,y)->(-y,x)->(-x,-y)->(y,-x)->(x,y)

these four reachable positions are the four "corners" of an axis-aligned rectangle with sides $|x|$ and $|y|$.

The police move in Manhattan metric. The Manhattan distance from origin to any corner is

d=|x|+|y|. Rotation changes which corner police must aim for and the player can

force police to spend extra moves when the player alternates corners cleverly.

Now if you are at coordinate |x|=|y|=1 then if you have $n$ rotation then at max you can survive is 2(n+1)

police moves. Look at the picture here green is the optimal path for the police and purple points are where

you can shift and red path isn't the optimal path

and if you are now |x|=|y|>1 then if you choose the optimal way to shift then you can survive at max

|x|(2n+1) + |y| police moves

and if you are at any $(x,y)$ then you can survive at max 2n(max(|x|,|y|)-1)+|x|+|y| police moves

for _ in range(int(input())):
    n, k = map(int, input().split())
    x, y = map(int, input().split())
    res = "No"
    if abs(x) == abs(y) and abs(x) == 1:
        if 2 * (n + 1) <= k:
            res = "Yes"
    elif abs(x) == abs(y):
        if abs(x) * (2 * n + 1) + abs(y) <= k:
            res = "Yes"
    else:
        if 2 * n * (max(abs(x), abs(y)) - 1) + abs(x) + abs(y) <= k:
            res = "Yes"
    print(res)