The Little Elephant from the Zoo of Lviv believes in magic. He has a magic board

Question

The Little Elephant from the Zoo of Lviv believes in magic.

He has a magic board A that consists of N rows and M columns. Each cell of the board contains an integer from 0 to 9 inclusive. The cell at the intersection of the i-th row and the j-th column is denoted as (i; j), where 1 %u2264 i %u2264 N and 1 %u2264 j %u2264 M. The number in the cell (i; j) is denoted as A[i][j].

The Little Elephant owns the only magic operation which can be described as follows. He chooses some integer P and some row or column, after that for each cell in the chosen row or column he adds number P to the number in this cell and take the result modulo 10 in order to keep numbers in the range {0, 1, ..., 9}. Our Little Magician wants to perform series of such operations to achieve some board for which certain characteristic called level of the board is maximal possible.

So what is the level of the board? Bluntly speaking it is the length of the longest non-increasing subsequence of cells of the board. Formally, the level of the board is the maximal integer K such that there exists such sequence of different cells (i1; j1), (i2; j2), ..., (iK; jK) for which

1 %u2264 i1 %u2264 ... %u2264 iK %u2264 N,
1 %u2264 j1 %u2264 ... %u2264 jK %u2264 M,

and

A[i1][j1] %u2265 A[i2][j2] %u2265 ... %u2265 A[iK][jK].

Though, the magic operation, the Little Elephant owns, is quite powerful, there are some restrictions dictated by the Association of Cursed Magicians (ACM):

Without these stupid restrictions of this stupid Association our hero could always achieve the maximal possible level M + N %u2212 1. But now he is confused and asks you for help. Find the maximal level of the board A after making arbitrary number of magic operations according to the restrictions of ACM.

The first line of the input contains a single integer T, the number of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and M, the sizes of the board. Each of the following N lines contains M one-digit numbers without spaces. The i-th line among them contains the numbers A[i][1], ..., A[i][M].

For each test case output a single line containing a single integer, the maximal possible level of the board that Little Elephant can achieve under the restrictions of ACM.

1 %u2264 T %u2264 10
1 %u2264 N %u2264 100
1 %u2264 M %u2264 100
0 %u2264 A[i][j] %u2264 9

Case 1. The board already has a sequence of 3 cells that satisfies all required constraints (without applying any operation). For example, one can choose, the sequence (1; 1), (1; 2), (2; 2). It is also shown in the figure below (chosen cells are made bold):

Let's formally validate this sequence of cells. Inequality 1 %u2264 i1 %u2264 ... %u2264 iK %u2264 N takes the form 1 %u2264 1 %u2264 2. Inequality 1 %u2264 j1 %u2264 ... %u2264 jK %u2264 M takes the form 1 %u2264 2 %u2264 2. Finally, inequality A[i1][j1] %u2265 A[i2][j2] %u2265 ... %u2265 A[iK][jK] takes the form 1 %u2265 1 %u2265 0. So all of them is satisfied, which means that the level of this board is at least 3. But clearly, we can't have the required sequence of cells of length more than 3. So 3 is the actual level of this board.

Case 2. The desired sequence of length 5 can be achieved by several values of P. Consider, for example, P = 3. At first let's apply the magic operation to the 1st row. We get the following transformation:

Now let's transform the 1st column by the magic operation. We get:

Finally we modify the 2nd column:

Now we can take the following sequence of 5 cells to satisfy all needed constraints: (1; 1), (2; 1), (2; 2), (3; 2), (3; 4) (see the figure below):

Just to reiterate we note that the inequality A[i1][j1] %u2265 A[i2][j2] %u2265 ... %u2265 A[iK][jK] takes the form 9 %u2265 7 %u2265 5 %u2265 4 %u2265 3 for this sequence. One can check (for example, by brute force), that sequences of length more than 5 can't be achieved. So 5 is the answer.

Explanation / Answer

#include <cstdio>

#include <cstring>

const int MAXN=100;

int A[MAXN][MAXN];

int dp[MAXN][MAXN][2][2][10];

int main()

{

int T, t;

int n, m, p, i, j, r, c, d0, d;

int ans, tans, tmp;

char buf[MAXN+1];

scanf("%d", &T);

for(t=1; t<=T; ++t)

{

scanf("%d%d", &n, &m);

for(i=0; i<n; ++i)

{

scanf("%s", buf);

for(j=0; j<m; ++j)

A[i][j]=buf[j]-'0';

}

ans=0;

for(p=0; p<10; ++p)

{

memset(dp, 0, sizeof(dp));

for(i=0; i<n; ++i)

for(j=0; j<m; ++j)

for(r=0; r<2; ++r)

for(c=0; c<2; ++c)

{

for(d=0; d<10; ++d)

{

tans=0;

if(i)

{

tans=dp[i-1][j][r][c][d];

tmp=dp[i-1][j][0][c][d];

if(tans<tmp)

tans=tmp;

tmp=dp[i-1][j][1][c][d];

if(tans<tmp)

tans=tmp;

}

if(j)

{

tmp=dp[i][j-1][r][0][d];

if(tans<tmp)

tans=tmp;

tmp=dp[i][j-1][r][1][d];

if(tans<tmp)

tans=tmp;

}

dp[i][j][r][c][d]=tans;

}

d=(A[i][j]+(r+c)*p)%10;

tans=dp[i][j][r][c][d];

if(tans==0)

tans=1;

for(d0=9; d0>=d; --d0)

{

if(i)

{

tmp=dp[i-1][j][0][c][d0]+1;

if(tans<tmp)

tans=tmp;

tmp=dp[i-1][j][1][c][d0]+1;

if(tans<tmp)

tans=tmp;

}

if(j)

{

tmp=dp[i][j-1][r][0][d0]+1;

if(tans<tmp)

tans=tmp;

tmp=dp[i][j-1][r][1][d0]+1;

if(tans<tmp)

tans=tmp;

}

}

dp[i][j][r][c][d]=tans;

}

for(r=0; r<2; ++r)

for(c=0; c<2; ++c)

for(d=0; d<10; ++d)

if(ans<dp[n-1][m-1][r][c][d])

ans=dp[n-1][m-1][r][c][d];

}

printf("%d ", ans);

}

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.