_Ash__'s blog

An interesting Problem on tree
By _Ash__, history, 6 years ago, In English

There is a problem from phuket regional 2015 that i have been trying to solve.

Here is the problem link : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=690&page=show_problem&problem=5321

The problem transforms into something like this , there is a tree ( at most 10^5 nodes) where each node has two values(let them call a,b). Now there are some (at most 10^5) queries of form : U V x y .

You have to find all the nodes on path U to V for which a*x + b*y is minimum. Note that if this minimum occurs for several nodes , you have to find them all. It is guaranteed that you don't have to print more than 3*10^5 nodes' id.

  • Vote: I like it
  • +40
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

You have to be able to solve the following problem:
Given pairs of integers (ai, bi), for a pair (x, y) find the minimal value of ai*x+bi*y.

You can note that a*x+b*y is a dot product of vectors (a,b) and (x,y). So you have to find a vector i such that (ai, bi) * (x, y) is minimal (* — is dot product). It's a standard problem which can be solved by constructing the convex hull of points (ai, bi).

Now you add HLD and get an O(n*log(n)^2) solution

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you add some details on how to solve that standard problem (minimal dot product query)?

    UPD: nvm, it's just finding the closet point of the convex hull to point (-x * inf, -y * inf), where inf ~= MAX_CORD.

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

      Unfortunately in some cases inf should be much bigger than MAX_CORD. Anyway, while finding the closest point you do binary search over such array: /\/ (increasing, decreasing, increasing) or vice-versa. Array val[i] = (ai,bi) * (x,y) is of the same form, so you can do binary search over it.

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

        What does the increasing, decreasing array contain?

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

          If we have a convex hull and the i-th point is (ai,bi) then val[i] = (ai,bi) * (x,y) — the dot product of vector (x,y) and radius-vector to point (ai,bi).

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

    I need some help on the details , how do you query in log^2(n) using HLD. Even if we have the convex hull created , we must at least binary search in each node of the segment tree.

    → Reply