MNMXPATH  Min Max 01 Path
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) (1based indexing) Rowi and Columnj 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 (i1,j), (i+1,j), (i,j1), (i,j+1) in one step. I want a path of minimum length from topleft cell (1,1) to bottomright 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
1  1  0 
0  0  0 
0  0  0 
1  1  0 
Case 1 : A Minimum path in bold
1  1  0 
0  0  0 
0  0  0 
1  1  0 
hide comments
darryl:
20131118 17:34:39
nice problem. need to consider A LOT of cases. Last edit: 20131118 17:35:18 

:D:
20110326 15:27:03
"I want a path of minimum length (...)" 

Gurpreet Singh:
20110326 15:25:02
I cant understand the maximum path.

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