959D: Mahmoud and Ehab and another array construction task

hard problem for me!!!

961D: Pair Of Lines

take 3 points, if they are on the same line, keep scanning, and exclude all other points => they should be on the smae line

Otherwise, try one of the 3 possible lines, as the first line

960D: Full Binary Tree Queries

  1. order of operations doesn’t matter

  2. so we can just, keep track of shifts of two ways at each level

  3. every level we move up, we need to calculate current shift - parent level shift, which, happens to be continous, means we can different apply delta as shift, and apply mod ops

962D: Merge Equals

  1. Keep track of each number’s occurances

  2. from min # to max #, get occurances, sort by the index, and populate the 2 * X, entry with the right value

  3. scan through the elements agent and populate the remaining elemnets

Each operation reduces the size of the array by 1, so it is O(nlogn)

963B: Destruction of a Tree

If |V| is even, then it is impossible to win, because |E| = |V| - 1 is odd, and we take out only even # of edges at each step.

Claim: if V is odd, then we can always do it.

Proof: By induction, on the size of the tree

  1. By induction, we can delete all subtrees with EVEN # of child nodes, and the oddity of the # of nodes with current tree is preserved

  2. Current root must have an even degree, because in the non-true root key case, the remaining subtrees each has ODD # of noeds, so the total nodes must be even

  3. Now we delete the root, and can induct on the full tree with ODD # of nodes case