ROWCOLOP - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice

Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Simple Math

PROBLEM

You are given an N &times N grid, initially filled by zeroes. The rows and the columns are numbered 1 through N. Then, you are given several operations, each being one of two types:

  • RowAdd R X: increase all numbers in row R by X.
  • ColAdd C X: increase all numbers in column C by X.

Determine the largest number in the grid after performing all operations.

EXPLANATION

It should be obvious that we cannot create a real N × N grid since it will take too much memory. Also we cannot simulate the operations directly since it will take too long time. We have to be more clever to solve this problem.

Imagine we have performed all operations. What is the final number in row r, column c? As the increment in rows is independent to the increment in columns, it will be (total increment in row r) + (total increment in column c).

We can calculate the total increment as follows. Create two arrays: totalRowIncrement[] and totalColIncrement[], each having N elements. Then,

  • For each RowAdd R X operation, add X to totalRowIncrement[R].
  • For each ColAdd C X operation, add X to totalColIncrement[C].

Therefore, the value of row r, column c after performing all operations is totalRowIncrement[r] + totalColIncrement[c]. Hence, the maximum number in the final grid is:

max {totalRowIncrement[r] + totalColIncrement[c] | 1 ≤ r, c ≤ N}

By iterating over all pairs (r, c) we can obtain the maximum number in O(R &times C). However, this is too much. We can notice that rows and columns are independent, so the above equation can be rewritten as:

max {totalRowIncrement[r] | 1 ≤ r ≤ N} + max {totalColIncrement[c] | 1 ≤ c ≤ N}

Now, the above version can be calculated in O(R + C) time. Here is a sample pseudocode for the solution.

readln(N, Q)
for q := 1; q ≤ Q; q++:
    readln(operation)
    if operation is "RowAdd R X":
        totalRowIncrement[R] += X
    else if operation is "ColAdd C X":
        totalColIncrement[C] += X

maxR := 0
maxC := 0
for i := 1; i := N; i++:
    maxR = max(maxR, totalRowIncrement[i])
    maxC = max(maxC, totalColIncrement[i])

println(maxR + maxC)

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

12 Likes
2

The solution can be improved from O(Q+R+C) to O(Q).

readln(N, Q)
maxR := 0
maxC := 0
for q := 1; q ≤ Q; q++:
    readln(operation)
    if operation is "RowAdd R X":
        totalRowIncrement[R] += X
        maxR = max(maxR, totalRowIncrement[R])
    else if operation is "ColAdd C X":
        totalColIncrement[C] += X
        maxC = max(maxC, totalColIncrement[C])

println(maxR + maxC)
7 Likes
3

Actually you still need to declare arrays totalRowIncrement[] and totalColIncrement of size N so IMHO this solution is still O(Q + N). But if you are using maps instead then you can get rid of N but it will cost you log Q factor - the complexity will be O(Q log Q).

The main advantage of such approach it that it allows to answer count_max query after each add query. I was thinking to use such mixed version but thought that it could be too hard for the second problem. Now I see that I was wrong :frowning:

4

Can’t we have only a single array ,where the elements are used for storing the total increment calculated either by RowAdd operation or ColAdd operation ?

2 Likes
5

No. Since we need to find max separately for rows and cols. The example when the solution with one array and finding max for it fails is the following:

2 4
RowAdd 1 3
RowAdd 2 1
ColAdd 1 1
ColAdd 2 3
4 Likes
6

Beautifully explained! But I believe the second for loop has a typo.
You wrote the condition as i := N

Shouldn’t it be i <= N ?

1 Like
7

i like the constrains of this probleam