We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Cube Summation
  2. Discussions

Cube Summation

Sort by

recency

|

14 Discussions

|

  • dehaka
     + 0 comments

    get ur hands dirty with 3D fenwick tree

    very long algo but this doesnt care about the number of queries, the standard approach that scans the queries so far will time out if the number of queries is too large, but this wall of text 3D fenwick tree method wont

    void update(vector<vector<vector<long>>>& fenwick, int x, int y, int z, long value) {
    while (x < fenwick.size()) {
        int tempY = y;
        while (tempY < fenwick.size()) {
            int tempZ = z;
            while (tempZ < fenwick.size()) {
                fenwick[x][tempY][tempZ] = fenwick[x][tempY][tempZ] + value;
                tempZ = tempZ + (tempZ & -tempZ);
            }
            tempY = tempY + (tempY & -tempY);
        }
        x = x + (x & -x);
    }
}

long access(const vector<vector<vector<long>>>& fenwick, int x, int y, int z) {
    long sum = 0;
    while (x > 0) {
        int tempY = y;
        while (tempY > 0) {
            int tempZ = z;
            while (tempZ > 0) {
                sum = sum + fenwick[x][tempY][tempZ];
                tempZ = tempZ - (tempZ & -tempZ);
            }
            tempY = tempY - (tempY & -tempY);
        }
        x = x - (x & -x);
    }
    return sum;
}

int main()
{
    int T, n, m, x, y, z, x1, y1, z1, x2, y2, z2;
    long W;
    string s;
    cin >> T;
    for (int i=1; i <= T; ++i) {
        cin >> n >> m;
        vector<vector<vector<long>>> block(n+1, vector<vector<long>>(n+1, vector<long>(n+1)));
        vector<vector<vector<long>>> fenwick(n+1, vector<vector<long>>(n+1, vector<long>(n+1)));
        for (int j=1; j <= m; ++j) {
            cin >> s;
            if (s == "UPDATE") {
                cin >> x >> y >> z >> W;
                update(fenwick, x, y, z, W - block[x][y][z]);
                block[x][y][z] = W;
            }
            else if (s == "QUERY") {
                cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
                long long A = access(fenwick, x1-1, y2, z2) + access(fenwick, x2, y1-1, z2) + access(fenwick, x2, y2, z1-1);
                long long B = access(fenwick, x1-1, y1-1, z2) + access(fenwick, x1-1, y2, z1-1) + access(fenwick, x2, y1-1, z1-1);
                cout << access(fenwick, x2, y2, z2) - A + B - access(fenwick, x1-1, y1-1, z1-1) << '\n';
            }
        }
    }
}

  • rebel_again1
     + 0 comments

    Java 8:

        public static List<Long> cubeSum(int n, List<String> operations) {
        long[][][] a = new long[n][n][n];
        
        List<Long> res = new ArrayList<>();
        for(String s: operations) {
            String[] v = s.split(" ");
            if(s.contains("UPDATE")) {
                a[Integer.valueOf(v[1]) - 1][Integer.valueOf(v[2]) - 1][Integer.valueOf(v[3]) - 1] = Long.valueOf(v[4]);
            } else {
                int x1 = Integer.valueOf(v[1]) - 1;
                int y1 = Integer.valueOf(v[2]) - 1;
                int z1 = Integer.valueOf(v[3]) - 1;
                int x2 = Integer.valueOf(v[4]) - 1;
                int y2 = Integer.valueOf(v[5]) - 1;
                int z2 = Integer.valueOf(v[6]) - 1;
                long sum = 0;
                for (int i = x1; i <= x2; i++) {
                    for (int j = y1; j <= y2; j++) {
                        for (int k = z1; k <= z2; k++) {
                            sum += a[i][j][k];
                        }
                    }
                }
                res.add(sum);
            }
        }
        return res;

    }

  • callison_adam
     + 1 comment

    Python 3 Just maintains a sparse representation through a dict, and iterates over entries checking they are within the bounds for each QUERY. Seems like this is only one conceptual step above the naive solution. Why is this in week 13? Is it harder in some languages?

    def cubeSum(n, operations):
    matrix = {}
    results = []
    for op in operations:
        oplist = op.strip().split()
        optype, data = oplist[0], tuple(int(x) for x in oplist[1:])
        
        if (optype == 'UPDATE') and (not data[-1] == 0):
            matrix[data[:-1]] = data[-1]
        else:
            result = 0
            x1, y1, z1, x2, y2, z2 = data
            for coord, value in matrix.items():
                x, y, z = coord
                if (x >= x1) and (x <= x2) and (y >= y1) and (y <= y2) and (z >= z1) and (z <= z2):
                    result += value
            results.append(result)
    return results

  • lhhu286
     + 0 comments

    Java converts to long for sum. Unncessary to use DP to pass test cases.

  • fukinscud
     + 0 comments
    def cubeSum(n, operations):
    matrix = {}
    
    block_sums = []
    for operation in operations:
        split_result = operation.split(' ')
        op = split_result[0]

        if op == 'UPDATE':
            x, y, z, w = split_result[1:]
            x, y, z, w = map(int, [x, y, z, w])
            matrix[(x, y, z)] = w
        else:
            x1, y1, z1, x2, y2, z2 = split_result[1:]
            x1, y1, z1, x2, y2, z2 = map(int, [x1, y1, z1, x2, y2, z2])
            block_sum = 0
            for (x, y, z), w in matrix.items():
                if x1 <= x <= x2 and y1 <= y <= y2 and z1 <= z <= z2:
                    block_sum += w
            block_sums.append(block_sum)
    return block_sums