Atcoder Typical 90 - Cross Sum (★2)

Wed Feb 11

To practice coding problems I figured might as well try out competitive programming. So this is the journey of trying out all 90 typical coding problems from Atcoder (https://atcoder.jp/contests/typical90). Feel free to join me on this journey!

Before anything, let’s preface this first post with I haven’t touched coding problems in a while. So I’m probably pretty rusty with all the DSA and Algo needed to solve these types of problems, but that’s not an issue. I’ll just have to remember them one-by-one from the back of my brain.

What do we do?

The Cross Sum problem asks us to return a matrix of integers (INT) where each cell contains the sum of its row and column integers. If we had a simple 3x3 matrix input:

Then the output should be a 3x3 matrix:

With that being said, for any coding problem it’s best to keep things going in minimal number of loops or runs. What that means is we don’t want to be repeating checks on elements if we can avoid the steps.

So an unlikely solution to this would be to store the matrix values of each cell, then add more loops to add the value of every other cell in its corresponding rows and columns. This would add too many checks per cell, when that could be avoided.

A more likely method would be to store the INT for each cell in one matrix and simultaneously add the values to a list of row sums and column sums. This way, we can store the sums of elements in each row and column in a single run. Then on our second run of checking each cell, we can add the row sum and column sum, then take away the repeated cell value output_cell[i][j] = sum_of_row[j] + sum_of_column[i] - cell[i][j].

My solution…

1
H, W = map(int, input().split())
2
rowSum = [0] * H
3
colSum = [0] * W
4
intMap = [[0] * W for _ in range(H)]
5

6
for i in range(H):
7
    s = input().split()
8
    for j, c in enumerate(s):
9
        rowSum[i] += int(c)
10
        colSum[j] += int(c)
11
        intMap[i][j] = int(c)
12

13
for i in range(H):
14
    row = [str(rowSum[i] + colSum[j] - intMap[i][j]) for j in range(W)]
15
    print(' '.join(row))

This solution has a time AND space complexity of O(H *W), which isn’t that bad. It only takes two full runs of checking each value before it spits out an answer.

Setting up

For the purpose of testing the Atcoder solutions, I created a simple python script that you can use to test your solution with test cases.

1
# Python 3.11
2
import sys
3
import importlib.util
4
from io import StringIO
5

6

7
def run_tests(module_path):
8
    spec = importlib.util.spec_from_file_location("solution", module_path)
9
    module = importlib.util.module_from_spec(spec)
10
    spec.loader.exec_module(module)
11

12
    if not hasattr(module, 'TEST_CASES'):
13
        print(f"Error: {module_path} does not have TEST_CASES defined")
14
        return
15
    if not hasattr(module, 'solve'):
16
        print(f"Error: {module_path} does not have solve() defined")
17
        return
18

19
    passed = 0
20
    failed = 0
21

22
    for i, (inp, expected) in enumerate(module.TEST_CASES, 1):
23
        sys.stdin = StringIO(inp)
24
        sys.stdout = StringIO()
25
        module.solve()
26
        result = sys.stdout.getvalue().strip()
27
        sys.stdin = sys.__stdin__
28
        sys.stdout = sys.__stdout__
29

30
        if result == expected.strip():
31
            print(f"Test case {i}: PASSED")
32
            passed += 1
33
        else:
34
            print(f"Test case {i}: FAILED")
35
            print(f"  Expected:\n{expected}")
36
            print(f"  Got:\n{result}")
37
            failed += 1
38

39
    print(f"\nResults: {passed} passed, {failed} failed")
40

41

42
if __name__ == "__main__":
43
    if len(sys.argv) != 2:
44
        print("Usage: python3 test.py <solution_file.py>")
45
        sys.exit(1)
46

47
    run_tests(sys.argv[1])

In the actual solution file, I’ve added a TEST_CASES list of sets that contains the example inputs and outputs to check if my solution works with those. In most cases, if the code works on those, it should work for other inputs, but who knows…