These problems were asked in Google Online Challenge a few weeks ago. For first one, I tried to put alternating levels into separate groups (forming only two groups) but that didn't worked for me :(. For second one, I have no idea. I will greatly appreciate any help. Thanks in advance.

both are really simple. The first one is just that there is only one way to divide a tree (a bipartite graph): just 2-color them. Then for each group we sort all the elements them and pair $$$A[1]$$$ with $$$A[M]$$$, $$$A[2]$$$ with $$$A[M-1]$$$ and so on for each group. You can prove this works by greedy exchange argument.

The second one is just binary search. First sort the array by costs. Note that $$$k \leq 10$$$. For each query we binary search the maximum index we can buy upto using $$$C$$$ rubles. The checker function, with prefix sum precalculation, is $$$O(k)$$$. So works in $$$O(n+Qk log(n))$$$

"Then for each group we sort all the elements them and pair A[1] with A[M], A[2] with A[M−1] and so on for each group."

Why we need to pair? Can't we just find the minimum and maximum in each group? Put cost of a group equal to (maximum-minimum)?

Thanks for your help.

i think you misread the problem. the cost of the group is the

maximum sumyou can achieve by pairing up the nodes. and the cost of each pair is given by the absolute difference of their values.By the way I think the statement of this problem is not that good. It took me a while to get what the hell they are trying to say.

Thank you, understood it now.

Again much thanks.

These look pretty simple. It's just two coloring and binary search with prefix sums.

Is copy and paste allowed in the online editor ?

Nope, You can only copy-paste the part of the code that is already written in the editor.