Index of "Algorithms: Design and Analysis"

Rook Attack

Given a N x M chessboard, where every cell has a value assigned to it denoted by 
 (Cell in the ith row from top and jth column from left).

Find the position (x, y) where we should place the rook, just the sum of cells which are under attack of rook is maximum possible. The rook can not attack the cell on which it is placed.

If there are more than one positions for (x, y), return the position where x is as minimum as possible. If there are more than one positions with equal x, return the position where y is as minimum as possible.

Note:

-> 1 based indexing is followed.
-> A rook can attack all the cells which are either in horizontal or vertical direction to the rook's position.
Input

First line contains two space separated integers denoting N and M.

Next N lines contains M space separated integers denoting the values of array A.

Output

Print two space separated integers x and y denoting the rook's position.

Constraints

1 ≤ N, M ≤ 10**6
1 ≤ A[i][j] ≤ 10**4

Sample Input
2 2
4 1 
3 1

Sample Output
1 2

Time Limit: 1.5
Memory Limit: 256
Source Limit:

Explanation

If we place the rook at (1, 2) position, the cells under attack of rook will be
(1, 1), (2, 2)
The sum of these cells will be
4 + 1 = 5, which is maximum possible.

Brute-Force Thinking....

Iterate through each cell of the chessboard and for each cell, calculate the sum of values in its row and column, excluding the value of the cell itself. Keep track of the maximum sum found and the corresponding position. If a new maximum is found, update the position. If the same maximum is found, check for the smallest row and column indices.


My Code:


N, M = map(int, input().split())

A = [list(map(int, input().split())) for _ in range(N)]

rowSum = [0] * N
colSum = [0] * M

for i in range(N):
    for j in range(M):
        rowSum[i] += A[i][j]
        colSum[j] += A[i][j]

best_score = -1
best_row = -1
best_col = -1

for i in range(N):
    for j in range(M):
        score = rowSum[i] + colSum[j] - 2 * A[i][j]

        # print("Score: ", score)
        # print(best_score, best_row, best_col)

        if score > best_score or (score == best_score and (i + 1 < best_row or (i + 1 == best_row and j + 1 < best_col))):
            best_score = score
            best_row = i + 1
            best_col = j + 1

print(best_row, best_col)

BEFORE I GIVE YOU CHATGPT'S THOUGHT: I WOULD LIKE TO TELL YOU THAT CHATGPT MADE A MISTAKE -- SAME MISTAKE REPEATEDLY WHEN TALKING ON A POINT ON MULTIPLE OCCASIONS

You see that when score is computed a cell: the value A[i][j] should be subtracted twice because it is counted in both rowSum and colSum. However, in the code and hints provided by ChatGPT, it is subtracted only once. 

So the correct formula for score should be:
score = rowSum[i] + colSum[j] - 2 * A[i][j

ChatGPT's Thoughts

Explain the solution to this problem in layman terms. Give clear descriptions of what this problem is trying to teach/assess, what design pattern, what problem solving trick/technique.

Let’s break this down slowly, simply, and intuitively, without jumping into code first.

🧩 What is the problem saying (in plain English)?

You are given a chessboard (a grid) where each cell has a number.

You want to place one rook on the board.

A rook:

Can attack all cells in the same row
Can attack all cells in the same column
❌ Cannot attack the cell it is placed on

Your goal is to:

Choose the cell where placing the rook gives the maximum total sum of attacked cells.

If multiple positions give the same maximum sum:

Choose the smallest row index x
If still tied, choose the smallest column index y

🧠 What does the rook “collect”?

If you place the rook at position (x, y):

It collects all values in row x
Plus all values in column y
Minus A[x][y] (because it cannot attack its own cell)

So effectively:


score(x, y) = rowSum[x] + colSum[y] - A[x][y]

🧪 Sample intuition

Input:


4 1
3 1

Grid:


4  1
3  1

At position (1,2):

Row 1 sum = 4 + 1 = 5
Column 2 sum = 1 + 1 = 2
Subtract cell (1,2) = 1

Final score = 5 + 2 - 1 = 6

This is the maximum possible → answer is (1,2)

🚀 The naïve (slow) way — and why it fails

A beginner might think:

For each cell, scan its entire row and column
Add values

That would cost:

mathematica
O(N + M) per cell
Total = O(N * M * (N + M)) ❌

This is too slow for large grids (up to 10⁶ cells).

💡 The key insight (problem-solving trick)

Instead of recalculating row and column sums again and again, we can:

Step 1: Precompute

The sum of every row → rowSum[]
The sum of every column → colSum[]

This takes only:

scss
O(N * M)

Step 2: For every cell `(x, y)`

Compute the score in constant time:

css
rowSum[x] + colSum[y] - A[x][y]

🎯 What this problem is really testing

1️⃣ Precomputation / Caching

Don’t repeat work
Compute row and column sums once
Reuse them

2️⃣ Optimization mindset

Replace nested loops with smart preprocessing
Turn an expensive operation into O(1)

3️⃣ Grid / Matrix reasoning

Understanding how rows and columns interact
Applying formulas on 2D data

4️⃣ Tie-breaking logic

Careful comparison logic
Attention to problem constraints

🧠 Design pattern used

✅ Precomputation + Enumeration

This is a very common competitive-programming pattern:

Precompute useful aggregates (row sums, column sums)
Enumerate all candidates efficiently
Track the best result with tie-breaking rules

📌 Why subtract `A[x][y]`?

Because:

The rook cannot attack the cell it is placed on
That cell is included once in the row sum
And once in the column sum
So we subtract it once

🧠 One-sentence intuition

“For each cell, imagine the rook collects everything in its row and column — so we just need fast access to row and column totals.”

🏁 Final takeaway

This problem teaches you:

How to optimize brute-force ideas
How to think in terms of precomputation
How to handle 2D data efficiently
How to apply clean mathematical reasoning to grids

If you want next:

Full Python code
Dry-run with a larger example
How this idea appears in other problems
Space/time complexity discussion

Just tell me 😊

Full Python code

Here is the full, correct, and efficient Python solution, followed by a clear explanation of how it works.

✅ Full Python Code

python
def solve():
    import sys
    input = sys.stdin.readline

    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    # Step 1: Compute row sums and column sums
    row_sum = [0] * N
    col_sum = [0] * M

    for i in range(N):
        for j in range(M):
            row_sum[i] += A[i][j]
            col_sum[j] += A[i][j]

    # Step 2: Find the best position
    max_score = -1
    best_x = 1
    best_y = 1

    for i in range(N):
        for j in range(M):
            score = row_sum[i] + col_sum[j] - A[i][j]

            if (score > max_score or
               (score == max_score and (i + 1 < best_x or
               (i + 1 == best_x and j + 1 < best_y)))):
                max_score = score
                best_x = i + 1   # convert to 1-based indexing
                best_y = j + 1

    print(best_x, best_y)

🧠 Explanation in Simple Terms

What are we doing?

We want to place a rook on a chessboard-like grid so that the sum of values it can attack (same row + same column) is as large as possible.

The rook:

Attacks everything in its row
Attacks everything in its column
❌ Does NOT attack the cell it sits on

So for any cell (i, j):

ini
score = rowSum[i] + colSum[j] - A[i][j]

Step-by-step logic

🔹 Step 1: Precompute row and column sums

Instead of re-adding rows and columns repeatedly (which would be slow), we compute:

Sum of each row
Sum of each column

This makes later calculations very fast.

🔹 Step 2: Try placing the rook at every cell

For every position (i, j):

Compute the attack sum using the formula above
Keep track of the maximum score found
If scores tie:
- Pick the smaller row index
- If still tied, pick the smaller column index

⏱️ Time & Space Complexity

Metric	Complexity
Time	O(N × M)
Space	O(N + M)

This is optimal for a grid with up to 1 million cells.

🧩 What this problem teaches

Precomputation optimization (don’t repeat work)
2D grid reasoning
Greedy comparison with tie-breaking
Turning brute force into efficient code

🏁 Final intuition (one line)

“Precompute row and column totals, then test every cell using a constant-time formula.”

If you want:

A dry-run example
A version using less memory
Similar problems to practice
Visualization

Just say the word 🙂

I am super excited to see GPT 5.2 make mistakes and hallucinate... so capturing a couple of screenshots below:

survival8

Pages

Tuesday, February 3, 2026

Rook Attack (Easy) - Find the position where we should place the rook, where Rook has maximum impact

BEFORE I GIVE YOU CHATGPT'S THOUGHT: I WOULD LIKE TO TELL YOU THAT CHATGPT MADE A MISTAKE -- SAME MISTAKE REPEATEDLY WHEN TALKING ON A POINT ON MULTIPLE OCCASIONS

ChatGPT's Thoughts

Explain the solution to this problem in layman terms. Give clear descriptions of what this problem is trying to teach/assess, what design pattern, what problem solving trick/technique.

🧩 What is the problem saying (in plain English)?

🧠 What does the rook “collect”?

🧪 Sample intuition

🚀 The naïve (slow) way — and why it fails

💡 The key insight (problem-solving trick)

Step 1: Precompute

Step 2: For every cell `(x, y)`

🎯 What this problem is really testing

1️⃣ Precomputation / Caching

2️⃣ Optimization mindset

3️⃣ Grid / Matrix reasoning

4️⃣ Tie-breaking logic

🧠 Design pattern used

✅ Precomputation + Enumeration

📌 Why subtract `A[x][y]`?

🧠 One-sentence intuition

🏁 Final takeaway

Full Python code

✅ Full Python Code

🧠 Explanation in Simple Terms

What are we doing?

Step-by-step logic

🔹 Step 1: Precompute row and column sums

🔹 Step 2: Try placing the rook at every cell

⏱️ Time & Space Complexity

🧩 What this problem teaches

🏁 Final intuition (one line)

I am super excited to see GPT 5.2 make mistakes and hallucinate... so capturing a couple of screenshots below:

No comments:

Post a Comment

Pages

Tuesday, February 3, 2026

Rook Attack (Easy) - Find the position where we should place the rook, where Rook has maximum impact

BEFORE I GIVE YOU CHATGPT'S THOUGHT: I WOULD LIKE TO TELL YOU THAT CHATGPT MADE A MISTAKE -- SAME MISTAKE REPEATEDLY WHEN TALKING ON A POINT ON MULTIPLE OCCASIONS

ChatGPT's Thoughts

Explain the solution to this problem in layman terms. Give clear descriptions of what this problem is trying to teach/assess, what design pattern, what problem solving trick/technique.

🧩 What is the problem saying (in plain English)?

🧠 What does the rook “collect”?

🧪 Sample intuition

🚀 The naïve (slow) way — and why it fails

💡 The key insight (problem-solving trick)

Step 1: Precompute

Step 2: For every cell (x, y)

🎯 What this problem is really testing

1️⃣ Precomputation / Caching

2️⃣ Optimization mindset

3️⃣ Grid / Matrix reasoning

4️⃣ Tie-breaking logic

🧠 Design pattern used

✅ Precomputation + Enumeration

📌 Why subtract A[x][y]?

🧠 One-sentence intuition

🏁 Final takeaway

Full Python code

✅ Full Python Code

🧠 Explanation in Simple Terms

What are we doing?

Step-by-step logic

🔹 Step 1: Precompute row and column sums

🔹 Step 2: Try placing the rook at every cell

⏱️ Time & Space Complexity

🧩 What this problem teaches

🏁 Final intuition (one line)

I am super excited to see GPT 5.2 make mistakes and hallucinate... so capturing a couple of screenshots below:

No comments:

Post a Comment

Step 2: For every cell `(x, y)`

📌 Why subtract `A[x][y]`?