LEMAGIC - Editorial

PROBLEM LINK

Practice
Contest

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.

6 Likes

Wasn’t the time limit a bit strict? My solution’s complexity was 4*(judge solution’s complexity), which was given time limit exceeded verdict.

2 Likes

i tried solving this problem as given in the editorial, but it was not giving right answer for even the test case. Is it right ?

Why do we consider the position (r, c) if and only if v == d? Shouldn’t it be v <= d?

It is not necessary to consider P=0 since for each other value of P we also consider the case when no operations will be applied.

The author’s solution consumes only 0.3 seconds on maximal test. The tester’s solution consumes 0.43. So TL is set about 10 times higher than maximal time of our both solutions. So I believe it is quite loyal. We can’t predict all slow solutions with the same complexity, sorry. But I see during the contest several solutions with DP having additional 2 dimensions that get AC.

1 Like

Is this problem statement missing a constraint??
I think with the specified constraints, length of largest possible sequence would be infinite. You stay at the same cell all the time, hence A(i,j) >= A(i,j) is achieved. Also the other constraints, (r1 >= r2) and (c1 >= c2) are satisfied. I think the missing constraint is either (r1 > r2) or (c1 > c2). Or am I missing something??

Exactly for contestants like you the word “different” is made bold in the sentence: “Formally, the level of the board is the maximal integer K such that there exists such sequence of different cells” :slight_smile:

So we can’t stay at the same cell.

I had similar problem in the contest, but finally understood it well. I have no idea how to write it better.

@anton_lunyov: Thanks man. :slight_smile: