703D: Mishka and Interesting sum (!!!)

Insights

1. answer to query = XOR of all elements XOR distinct elements

2. To answer XOR of distinct elements => we need to solve "find # of distinct values in a segment", need to help of Fenwicks Tree

3. Need to process queries in sorted by ending index way, so that we update each entry in the segment tree only once

4. Final runtime is O(nlogn)

144D: Missile Silos

A modification of dijkstra’s algorithm, try adding to the answer when we are expanding

679B: Bear and Tower of Cubes(!!!)

Consider the upper bound m, the higher upper bound the better result is

Assume the first block we pick is max a s.t. a^3 <= m

Then answer is 1 + num(m - a^3)

If the first block we pick is (a-1), the then answer is 1 + num(a^3 - 1 - (a-1)^3)

by the same logic, we can see the only possible choice that yield the best solution is either block with side a or a-1, because if we pick a-2, the answer will be 1 + num((a-1)^3 - (a -2)^3), which can not be better do the greedy propety of the upper bound m

During implementation, when we are calcuate n-1 cases, we need to take the cube too, because otherwise, the two branch will remain on the same magnitute => linear solution!!!After taking the max-1 cube in the same step, the second branch shrinks quickly and will not pose problem to us