Блог пользователя pretending

How to solve these problems from Google Online challenge?
Автор pretending, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +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))$$$

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -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.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is copy and paste allowed in the online editor ?

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

    → Ответить