PROBLEM LINK
DIFFICULTY
EASY-MEDIUM
PREREQUISITES
Dynamic Programming
PROBLEM
You are given a M by N matrix of integers, say A. Each value is between 0 and 9, inclusive.
You select a number P, at the beginning, such that you can optimize your goal (which will be described later).
Now, you can perform the following operation on any row or column of A (at most once per row and once per column).
- Add P to all the values in the row / column.
- Replace each value in A, say v, with v % 10. Meaning, each value in the matrix must be stored modulo 10.
You have to choose the correct P, and perform the operations on the correct set of Rows and Columns such that, there is as long a possible sequence as described below, after performing the operations.
Sequence: { Ar1c1, Ar2c2, …, Arkck }
Where,
- Ar1c1 ≥ Ar2c2 … ≥ Arkck
- r1 ≤ r2 … ≤ rk
- c1 ≤ c2 … ≤ ck
QUICK EXPLANATION
If the operation could be performed as many times as you wish on any rows and columns, the answer would always be M+N-1.
It is intuitive that we can iterate for P from 0 to 9, inclusive and see which value of P gives the best results. But finding the longest sequence for any value of P was of course the hard detail of the problem.
The problem is a typical Dynamic Programming problem. In the explanation section below, we will see how a state can be retrived from smaller substates in the state-space specified by the following tuple.
(r, c, x, y, d)
Where, (r, c, x, y, d) is the length of the longest sequence that follows the above conditions, and
- The last element appears on or before row r
- The last element appears on or before columnn c
- The operation has been performed x times on row r.
- x is either 0 or 1
- P has been chosen in the beginning.
- The operation has been performed y times on column c.
- y is either 0 or 1
- P has been chosen in the beginning.
- The last element in the sequence is more than or equal to d.
The answer would of course be
max ( (R,C,0,0,0),
(R,C,0,1,0),
(R,C,1,0,0),
(R,C,1,1,0) )
Each value in the state space can be calculated in constant time using sub-states. The over-all complexity of the algorithm would be O(10*M*N*2*2*10).
EXPLANATION
Consider the following expression
1: (r,c,x,y,d) = 2: if d > 9 3: return 0 4: else 5: v = (A[r,c] + x*P + y*P) % 10 6: return max( (r,c,x,y,d+1), 7: (r-1,c,0,y,d), 8: (r-1,c,1,y,d), 9: (r,c-1,x,0,d), 10: (r,c-1,x,1,d), 11: (r-1,c-1,0,0,d), 12: (r-1,c-1,0,1,d), 13: (r-1,c-1,1,0,d), 14: (r-1,c-1,1,1,d) ) 15: + (v == d ? 1 : 0)
Line 2 and 3
- This guard ensures that we do not consider digits greater than 9, since digits cannot be greater than 9.
Line 5
- This is the value of the digit at position (r,c) with the operation applied to the row r, x times, and to the column c, y times.
Line 6
- Since (r,c,x,y,d) returns the length of the longest sequence which ends in a digit more than or equal to d.
- Hence we consider the sub-state that has larger value of d.
Line 7 and 8
- Since (r,c,x,y,d) returns the length of the longest sequence that end before or at row r.
- We can consider the sequences that end at row r-1, column c (or before)
- At column c, it will depend upon y, whether the operation was applied or not
- At row r-1, the operation could or could not have been applied; both are valid situations.
- Hence we consider these two sub-states.
Lines 9 and 10
Similar to the argument for considering row r-1, column c
- This case considers the sequences that end at row r, column c-1 (or before)
- At row r, it will depend upon x, whether the operation was applied or not
- At column c-1, the operation could or could not have been applied; both are valid situations.
- Hence we consider both the sub-states.
Lines 11 - 14
- This case considers the sequences that end at row r-1, column c-1 (or before)
- Now, since we are considering separate rows / columns, we have full degree of freedom with regard to application of the operation
- At row r-1, the operation may or may not have been applied
- At column c-1, the operation may or may not have been applied
- Hence we consider the 4 sub-states.
Lines 15
We did not consider the element at position (r,c) yet. We consider that value if and only if the value of the element (influenced by x and y) is equal to d.
There are several small optimizations that are possible. Using 5D arrays is highly dependent on the implementation. Look at the Tester’s solution for a faster implementation of this approach. Look at the Setter’s solution for an implementation that avoids 5D arrays altogether.
The problem is solved by iterating over P, and running the above Dynamic Programming formulation for each chosen value of P. P = 0, takes care of the condition where the operations are not applied at all.
SETTERS SOLUTION
Can be found here.
TESTERS SOLUTION
Can be found here.
