### pretending's blog

By pretending, history, 11 days ago,

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.

• 0

 » 11 days ago, # |   +15 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))$
•  » » 11 days ago, # ^ |   -6 "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.
•  » » » 11 days ago, # ^ |   +17 i think you misread the problem. the cost of the group is the maximum sum you 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.
•  » » » » 11 days ago, # ^ |   0 Thank you, understood it now. Again much thanks.
 » 11 days ago, # | ← Rev. 2 →   0 These look pretty simple. It's just two coloring and binary search with prefix sums.
 » 11 days ago, # |   0 Is copy and paste allowed in the online editor ?
•  » » 11 days ago, # ^ |   +6 Nope, You can only copy-paste the part of the code that is already written in the editor.