pretending's blog

How to solve these problems from Google Online challenge?
By pretending, history, 3 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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))$$$

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    "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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is copy and paste allowed in the online editor ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply