Editorial for OTHS Coding Competition 3 (Mock CCC) S5 - World Tree

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Ivan_Li

Subtask 1

This subtask is meant to reward brute-force solutions. One possible approach would be recursively transferring information to a node's children if its capacity is exceeded. This approach will be \mathcal{O}(N) for updates and \mathcal{O}(1) for queries.

Subtask 2

The brute-force solution will be too slow here. Instead, we use the fact that the tree is guaranteed to be a complete binary tree. Thus, it will have a depth of at most \lceil \log(N) \rceil. We create a lazy tag for each node and use the same ideas as lazy propagation on a segment tree.

For updates, add v_i information to the node's lazy tag, taking \mathcal{O}(1).

For queries, we propagate the lazy tag on every ancestor of x_i, from top to bottom, taking \mathcal{O}(\log{n}). Then, we can access the information at node x_i.

Subtask 3

The idea is the same as in subtask 2, but since the tree can now be extremely tall, we cannot propagate the lazy tag on every ancestor of x_i. Instead, notice that since each node has 0 or 2 children, the additional information will either be deleted or halved each time. After halving around \log_2{\frac{5\times10^5\times10^9}{10^{-5}}} \approx 66 times, the remaining information becomes negligible, since the problem allows for an absolute or relative error of 10^{-5}. Thus, we only need to propagate 66 nodes directly above x_i.

Comments


  • 1
    incubus  commented on May 28, 2025, 4:58 a.m.

    36 times aren't enough. Consider the following testcase:

    97 500000
1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1000000000
1 1 1000000000  <-  Repeat this line 499998 times
1 97 1
2 97

    Or you may use this Java code to generate it:

    import java.util.Arrays;

public class TestInput {
    final int[] parent;
    final int[] capacity;
    final int[][] operations;

    TestInput(int height, int opCount) {
        int n = 2 * height + 1;
        parent = new int[n - 1];
        for (int i = 0; i < n - 1; i++)
            parent[i] = i | 1;
        capacity = new int[n];
        Arrays.fill(capacity, 1);
        capacity[n - 1] = (int) 1e9;
        operations = new int[opCount][];
        for (int i = 0; i < opCount - 2; i++)
            operations[i] = new int[] { 1, 1, (int) 1e9 };
        operations[opCount - 2] = new int[] { 1, n, 1 };
        operations[opCount - 1] = new int[] { 2, n };
    }

    private static void outArray(StringBuilder sb, int[] arr) {
        sb.append(arr[0]);
        for (int i = 1, n = arr.length; i < n; i++)
            sb.append(' ').append(arr[i]);
        sb.append('\n');
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(capacity.length).append(' ').append(operations.length).append('\n');
        outArray(sb, parent);
        outArray(sb, capacity);
        for (int[] op : operations)
            outArray(sb, op);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(new TestInput(48, (int) 5e5));
    }
}

    The correct answer is 1.7763497339728964, not 1.


    • 1
      Ivan_Li  commented on May 31, 2025, 1:13 a.m.

      Yeah... you're right. I forgot to include the \times10^9 term in my expression. This should hopefully be fixed now.