Mysterious109's blog

Help with a problem
By Mysterious109, history, 17 months ago, In English

Hi, I made a graph problem that I couldn't solve and I was wondering if it's solvable at all, so I'd appreciate if someone solved it (doesn't have to be solvable in the given constraints just any solution).

given a rooted weighted tree made of $$$n$$$ nodes you start from the root and go to any adjacent node you are given $$$m$$$ resturants each one will be on a node you are required to print the minimum cost to visit $$$k$$$ different resturants (you can visit an edge more than once)

$$$1\le n \le 10^5$$$, $$$m \le n$$$, $$$k \le m$$$, $$$1 \le cost \le 10^9$$$

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

»
17 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Do we need to return to the root after visiting $$$k$$$ restaurants?

→ Reply
»
17 months ago, # |
  Vote: I like it +2 Vote: I do not like it

الراجل ده بيتكلم صح

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

Probably unsolvable, but for starters, you can solve for small $$$k$$$ using bitmask dp.

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

So we have a tree with $$$m$$$ black nodes are your goal is to go through $$$k$$$ black nodes.

Consider two kinds of strategies:

  1. Go to a black vertex and start moving to an adjacent non-black node back and forth until you arrive at $$$k$$$ black nodes visited.
  2. Go to a black vertex and start moving to an adjacent black node back and forth until you arrive at $$$k$$$ black nodes visited.

The path follows one of these strategies, I leave the proof to the reader but it's a simple contradiction.

For each node precompute its distance to the root and the number of black nodes in this path with a simple DP. Now, for each black node try strategy 1 with its lower-weighted adjacent non-black node and strategy 2 with its lower-weighted adjacent black node.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    You have to visit k different black nodes can't be the same node and visit it k number of times.

    → Reply
    • »
      »
      »
      17 months ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Ok, I misunderstood it, although the statement does not say anything about it.

      → Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I guess that you meant that the rooted-tree is weighted-edge, i.e. each edge has a weight associated with walking through it one time. Is that right?

→ Reply
»
17 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I was thinking $$$dp[v][k][f] =$$$ min cost if you have to pick $$$k$$$ vertices from the subtree of $$$v$$$, and $$$f$$$ is 1 if you have to go all the way back to the root $$$v$$$ after getting the $$$k$$$ specials and $$$0$$$ if not.

Then we could solve this with a convolution on tree (similar to this problem): $$$dp[v][a + b][0] = min(dp[v][a][0] + dp[to][b][0])$$$ and $$$dp[v][a+b][1] = min(dp[v][a][1] + dp[to][b][0], dp[v][a][0] + dp[to][b][1])$$$.

This seems to be like a (min,+) convolution, which can be solved faster in this case since the $$$dp$$$ is convex, similary to this other problem, by mainting the difference $$$dp[v][a] - dp[v][a-1]$$$ and using small to large to merge this difference arrays.

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

    so k is the number of restaurants that I will pick in the subtree right?

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

    Actually, not sure if this is convex... It still should solve in $$$O(N^2)$$$...

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

is this the same as this problem? group link. it's was copied from some OI competitions.

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

    It is similar but this one is rooted so you have to visit some edges multiple times to achieve an answer

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

      unrooted seems to be harder than rooted, and also in that problem you can pass through an edge multiple times

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

        It's not about which is the harder version it's a totally different solution, the problem was solved in a comment above if you want to see the solution

        → Reply