MNMXPATH - Min Max 01 Path

no tags 

I have been asked to set a problem by spoj, what do I do now ? Lets see the standard stuff in most of the programming contests and make one problem out of it. Hmm... many problems are having Binary digits, Grids, Paths, Coins, Maximize or Minimize something, so let me mix them all now in to one problem, the one problem to rule them all ;)

Lets have a grid of size N x M having N rows and M columns, and put gold coins in it. How many in each cell ? , lets involve binary here. I'll give you two binary strings A[1...N] and B[1...M]. Cell (i,j) (1-based indexing) Row-i and Column-j in the grid contains A[i] * B[j] gold coins. From a cell (i,j), you can move to any of the 4 adjacent cells (i-1,j), (i+1,j), (i,j-1), (i,j+1) in one step. I want a path of minimum length from top-left cell (1,1) to bottom-right cell (N,M), and the value of this path = number of gold coins it covers. Find the maximum value of such a path. Not every one wants to become a Raja, also find the minimum value of such a path.

Input

First line contains T [ number of test cases, around 10 ]. T cases follow, each having 2 lines, "N A" and "M B" (quotes for clarity only). [ 1 <= N,M <= 100,000 and each character in A, B is either 0 or 1 ]

Output

For each test case, print the maximum value of a path followed by the minimum value of a path, in the same line, separated by a single space. Output of each case should be in a separate line.

Example

Input:
2
4 1001
3 110
5 01111
3 110

Output:
3 1
5 0

Explanation:
Case 1 : A Maximum path in bold
110
000
000
110

Case 1 : A Minimum path in bold
110
000
000
110


hide comments
darryl: 2013-11-18 17:34:39

nice problem. need to consider A LOT of cases.

Last edit: 2013-11-18 17:35:18
:D: 2011-03-26 15:27:03

"I want a path of minimum length (...)"

Gurpreet Singh: 2011-03-26 15:25:02

I cant understand the maximum path.
Why shouldn't it be such as to collect all the gold coins.....
And whats the significance of the statement " Not every one wants to become a Raja. "????

RE1: ThanQ zukow........

Re2: nice nice nice very nice problem, I was very happy after getting AC!!! Lots of cases to be taken care of!!!!

Re3: Glad that you liked the problem. About the statement, "Not every one wants to become a Raja.", its just a pun intended to relate to some one ( who was an Indian minister ;) )

Last edit: 2011-05-02 13:44:53

Added by:Anil Kishore
Date:2011-02-25
Time limit:0.291s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeMutants 2011 , DA-IICT, India