
MOOSACO 2024 July Contest, Iron
Problem 2. Bullies
Contest may or may not have ended. We don't know.
Analysis mode
Farmer John's cows each live in a square in his N by N pasture ($1 \leq N \leq 10,000$). Each cow located at position ($i, j$) has a strength value of $a_{i,j}$ ($1 \leq a_{i,j} \leq 10^9$). However Farmer John has recently noticed a bullying problem among his cows. Thus, he recently rearranged his cows onto a grid and would like to know if the bullying problem will persist in his new arrangement of cows.
Each cow at position ($i, j$) will graze a square around them. Specifically, a cow ($i, j$) will graze all squares ($x, y$) if max(abs(x-i), abs(y-j)) is strictly less than a number $R$ ($1 \leq R \leq N$).
A cow will bully another cow if and only if both of the following conditions are true:
- one of the cows is located at a square that the other will graze
- the positive difference between their strength values is greater than $D$ ($1 \leq D \leq 10^9$).
For each test case, please output whether a cow will get bullied.
INPUT FORMAT (input arrives from stdin):
First line $T$, the number of test cases ($1 \leq T \leq 10$)
For each test case: Line 1 has three integers $N$, $R$, and $D$.
Next $N$ lines have $N$ integers each, denoting the strength value of cow ($i, j$).
OUTPUT FORMAT (send output to stdout):
For each test case, please output "uh oh!" (without the quotes) if a cow will get bullied, or "you're safe this time bucko" (without the quotes) if no cow will get bullied.
SAMPLE INPUT:
2 4 2 5 1 1 1 1 1 3 3 3 1 3 7 3 1 3 3 3 4 2 5 1 1 1 1 1 1 3 3 1 3 7 3 1 3 3 3
SAMPLE OUTPUT:
you're safe this time bucko uh oh!
In the second test case, the cow at location (2, 2) has a strength value of 1, and the cow located at position (3, 3) has a strength value of 7. 7 - 1 = 6, which is greater than 5, so the cow at (2, 2) will get bullied.
Note: I haven't made any test cases beside the sample case so you might want to check again later if you want to solve the problem.
Problem credits: rotator.cf