BAT4 - BATMAN4

Batman: "A hero can be anyone. Even a man doing something as simple and reassuring as putting a coat around a little boy's shoulder to let him know that the world hadn't ended."

THE BOMB IS TRIGGERED !!, IT WOULD BLOW UP IN A FEW MINUTES !!

BATMAN resorts to his BAT and decides to head towards the ocean with the bomb.

However in front of him lies a huge grid of tall buildings. Starting from the top-leftmost grid he needs to move to the bottom right-most grid to reach the ocean. Since the fuel of BAT has nearly exhausted, BATMAN decides to chose a path where the maximum up distance travelled at a time is minimized. However, each movement of the BAT up or down the building takes one unit of time. (Horizontal movements can be made in no time). The clock keeps ticking, So BATMAN decides to choose a path reaching the destination minimizing the maximum up distance and with as much time left as possible.

Every Hero Has a Journey. Every Journey Has an End !

CatWoman : "You don't owe these people anymore. You've given them everything"
BatMan : "Not everything, Not Yet. "

NOTES :

BatMan requires to take the first jump on (1,1)
Print NO is no time is left
minimum max up-distance is the first priority.

Input

The first line contains T, the number of testcases.

In each testcase, the first line contains N (the size of the grid) and M (the time left).

The next N lines contain N integers, denoting the heights of the building.

Output

If BATMAN could reach the destination, print "YES", the maximum up distance travelled and the maximum time left with BATMAN.

If he could not reach the destination within time, print "NO".

Constraints

1 <= N <= 20

1 <= M <= 100

Example

Input:
1
3 40
2 4 3
4 5 3
2 4 6

Output:
YES : 2 32

Added by:Romal Thoppilan
Date:2013-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2021-06-15 20:57:23
"maximum up distance travelled at a time is minimized" what is meant by at a time and why is it not 2 34 because from (1,1)=>(1,2)
(1,2)=>(2,2) (2,2)=>(3,2) (3,2)=>(3,3) so total time remaining is 34 and max up distance covered at a time = 2


Last edit: 2021-06-15 21:04:06
2020-04-30 07:36:52
Moreover, I found two more errors
1. That there are no test cases where the solution is checked for arrays of size n=1.

2. There is no test case when reaching with 0 time left is checked.
Because my solution of 0 time left prints yes and it is getting accepted.

I seriously believe that this problem could have been real gold considering the different priorities in order and meanwhile minimizing one based only on some conditions and other constraints. I mean the thought of setting this problem was good but then the test-cases and poor problem description ruined it.

Last edit: 2020-04-30 08:25:39
2020-04-30 06:42:11
Checkout this testcase:

1
4 100
1 10 11 12
2 10 11 12
3 10 11 12
1 2 3 4

The Correct answer according to the problem description should be
YES : 1 92
When I was submitting a solution for the above, it was WA 4 times.
Then I submitted a solution for
YES : 2 92
and it gave AC.
Bad problem. This problem accepts solution which requires you to find the minimum of maximum abs difference in heights at a time and not just up the building.
2020-03-20 00:29:09
1) consider only right and down movement.
2) reaching with 0 time left is "NO"
3) integer is sufficient no long int required
4) only minimize max-up movement
2018-05-22 20:19:04
Could someone explain what question is demanding ? Very tricky and ambiguous language, poor description.
2018-01-07 23:15:08
considering all 4 directions - tle
considering down and right - accepted
poor problem description
2017-10-06 00:25:24
This is horrible, SPOJ should really let people other than the author edit problem statements
2017-06-22 19:32:54
Spoj Toolkit is also giving incorrect results as to the case of Rohit Kumar my solution is also giving YES : 12 76
and I think its correct
2017-05-20 12:37:47
Problem is very badly described. It surely deserves a downvote.
2017-02-17 07:53:38
The toughest part of the problem was the problem statement itself. Please edit it so that it could be easily understandable.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.