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. Prepare
  2. Data Structures
  3. Advanced
  4. Cube Summation
  5. Discussions

Cube Summation

Sort by

recency

|

81 Discussions

|

  • finnallen028
     + 0 comments

    Great post

  • gfostick
     + 0 comments
    def cubeSum(n, operations):
    s = {}
    res=[]
    for op in operations:
        op = op.rstrip().split()
        if op[0] == 'UPDATE':
            x, y, z, w = map(int, op[1:])
            s[(x, y, z)] = w
        else:
            x1, y1, z1, x2, y2, z2 = map(int, op[1:])
            csum = sum(s[(x, y, z)] for x, y, z in s if x1 <= x <= x2 and y1 <= y <= y2 and z1 <= z <= z2)
            res.append(csum)
    return res

  • justin_gries
     + 0 comments

    Absolutely OO overkilled this in Java, but I had a fun time doing it. Note: The sums generated exceed what a 32-bit int can handle. You will need to alter the code provided to use Longs instead of Integers if you notice your results rolling around due to overrun.

    All tests passed. Not sure about efficiency; Rolled my own data-nodes. Tried to use TreeSets to do "just in time" node creation and to skip over empty slots during summation.

    class Result {

    public static List<Long> cubeSum(int n, List<String> operations) {
        Cube cube = new Cube();
        List<Long> outputs = new LinkedList<>();
        for (String operation : operations) {
            OperationType.doOperation(operation.split(" "), cube, outputs);
        }
        return outputs;
    }
}
    
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int T = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, T).forEach(TItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int matSize = Integer.parseInt(firstMultipleInput[0]);

                int m = Integer.parseInt(firstMultipleInput[1]);

                List<String> ops = IntStream.range(0, m).mapToObj(i -> {
                    try {
                        return bufferedReader.readLine();
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                })
                    .collect(toList());

                List<Long> res = Result.cubeSum(matSize, ops);

                bufferedWriter.write(
                    res.stream()
                        .map(Object::toString)
                        .collect(joining("\n"))
                    + "\n"
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

class Cube extends NodeSet<Plane> {

    public Cube() {
        super(new TreeSet<>());
    }

    public void setValue(int x, int y, int z, int value) {
        IndexedNode<Plane> planeNode;
        planeNode = super.getNode(x);
        planeNode.getData().setValue(y, z, value);
    }

    public long sumValues(int x1, int y1, int z1, int x2, int y2, int z2) {
        long sum = 0L;
        for (IndexedNode<Plane> planeNode : getSubset(x1, x2)) {
            sum += planeNode.getData().sumValues(y1, z1, y2, z2);
        }
        return sum;
    }

    @Override
    public IndexedNode<Plane> setNewNode(int position) {
        Plane newPlane = new Plane();
        IndexedNode<Plane> newNode = new IndexedNode<>(position, newPlane);
        getNodeSet().add(newNode);
        return newNode;
    }
}

interface HasIndex {
    public int getIndex();
}

class Indexed implements HasIndex, Comparable<HasIndex> {
    private final int index;

    public Indexed(int index) {
        this.index = index;
    }

    @Override
    public int getIndex() {
        return this.index;
    }

    @Override
    public int compareTo(HasIndex o) {
        return Integer.compare(getIndex(), o.getIndex());
    }
}

class IndexedNode<T> extends Indexed {
    private T data;

    public IndexedNode(int index, T data) {
        super(index);
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }
}

class Line extends NodeSet<Integer> {

    Line() {
        super(new TreeSet<>());
    }

    public long sumValues(int z1, int z2) {
        long sum = 0L;
        for (IndexedNode<Integer> valueNode : getSubset(z1, z2)) {
            sum += valueNode.getData();
        }
        return sum;
    }

    @Override
    public IndexedNode<Integer> setNewNode(int position) {
        IndexedNode<Integer> newNode = new IndexedNode<>(position, 0);
        getNodeSet().add(newNode);
        return newNode;
    }

    public void setValue(int z, int value) {
        IndexedNode<Integer> node = super.getNode(z);
        node.setData(value);
    }
}

abstract class NodeSet<T> {

    private final TreeSet<IndexedNode<T>> nodes;

    NodeSet(TreeSet<IndexedNode<T>> nodes) {
        assert nodes != null;
        this.nodes = nodes;
    }

    public TreeSet<IndexedNode<T>> getNodeSet() {
        return this.nodes;
    }

    public SortedSet<IndexedNode<T>> getSubset(int start, int end) {
        IndexedNode<T> startNode = new IndexedNode<>(start, null);
        IndexedNode<T> endNode = new IndexedNode<>(end + 1, null);
        return getNodeSet().subSet(startNode, endNode);
    }

    public IndexedNode<T> getNode(int position) {
        IndexedNode<T> node = new IndexedNode<>(position, null);

        if (!getNodeSet().contains(node)) {
            node = setNewNode(position);
        } else {
            node = getSubset(position, position + 1).first();
        }
        return node;
    }

    public abstract IndexedNode<T> setNewNode(int position);
}

enum OperationType {

    QUERY("QUERY") {
        @Override
        protected void evaluate(String[] inputs, Cube cube, List<Long> outputs) {

            int x1 = Integer.parseInt(inputs[1]);
            int y1 = Integer.parseInt(inputs[2]);
            int z1 = Integer.parseInt(inputs[3]);
            int x2 = Integer.parseInt(inputs[4]);
            int y2 = Integer.parseInt(inputs[5]);
            int z2 = Integer.parseInt(inputs[6]);
            outputs.add(cube.sumValues(x1, y1, z1, x2, y2, z2));
        }
    },

    UPDATE("UPDATE") {
        @Override
        protected void evaluate(String[] inputs, Cube cube, List<Long> outputs) {
            int x = Integer.parseInt(inputs[1]);
            int y = Integer.parseInt(inputs[2]);
            int z = Integer.parseInt(inputs[3]);
            int value = Integer.parseInt(inputs[4]);
            cube.setValue(x, y, z, value);
        }
    };

    private final String text;

    OperationType(String text) {
        this.text = text;
    }

    public static void doOperation(String[] inputs, Cube cube, List<Long> outputs) {
        String type = inputs[0];
        for (OperationType t : OperationType.values()) {
            if (type.toUpperCase().equals(t.text)) {
                t.evaluate(inputs, cube, outputs);
                return;
            }
        }
        throw new RuntimeException("Operation \"" + type + "\" not found");
    }

    protected abstract void evaluate(String[] inputs, Cube cube, List<Long> outputs);
}

class Plane extends NodeSet<Line> {
    public Plane() {
        super(new TreeSet<>());
    }

    public long sumValues(int y1, int z1, int y2, int z2) {
        long sum = 0L;
        for (IndexedNode<Line> planeNode : getSubset(y1, y2)) {
            sum += planeNode.getData().sumValues(z1, z2);
        }
        return sum;
    }

    public void setValue(int y, int z, int value) {
        Line line = super.getNode(y).getData();
        line.setValue(z, value);
    }

    @Override
    public IndexedNode<Line> setNewNode(int position) {
        Line line = new Line();
        IndexedNode<Line> newNode = new IndexedNode<>(position, line);
        this.getNodeSet().add(newNode);
        return newNode;
    }
}

  • deadlious
     + 0 comments

    Considering some python specifics, this is quite easy:

    def cubeSum(n, operations):
    result = []
    memory = {}

    for operation in operations:
        match operation.split():
            case ['UPDATE', *coords, value]:
                x, y, z = map(int, coords)
                memory[(x, y, z)] = int(value)
                
            case ['QUERY', *coords]:
                x1, y1, z1, x2, y2, z2 = map(int, coords)
                s = 0
                
                for key, value in memory.items():
                    if x1 <= key[0] <= x2 and y1 <= key[1] <= y2 and z1 <= key[2] <= z2:
                        s += value
                result.append(s)
    return result

  • dehaka
     + 1 comment
    vector<long long> cubeSum(int n, vector<string> o) {
    map<tuple<int, int, int>, int> M;
    vector<long long> answer;
    for (int i=0; i < o.size(); i++) {
        stringstream ss(o[i]);
        string word;
        vector<int> t;
        while (ss >> word) {
            if (isdigit(word[0])) t.push_back(stoi(word));
        }
        if (o[i][0] == 'U') M[make_tuple(t[0]-1, t[1]-1, t[2]-1)] = t[3];
        else {
            long long temp = 0;
            for (auto p : M) {
                int x = get<0>(p.first);
                int y = get<1>(p.first);
                int z = get<2>(p.first);
                if (t[0]-1 <= x and x < t[3] and t[1]-1 <= y and y < t[4] and t[2]-1 <= z and z < t[5]) {
                    temp = temp + p.second;
                }
            }
            answer.push_back(temp);
        }
    }
    return answer;
}