PROBLEM LINKS
DIFFICULTY
SIMPLE
PREREQUISITES
Simple Math
PROBLEM
You are given an N × 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 × 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*) maxC = max(maxC, totalColIncrement*) println(maxR + maxC)
SETTER'S SOLUTION
Can be found here.
TESTER'S SOLUTION
Can be found here.