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

Help with a tree-related problem
Автор AnotherRound, история, 8 лет назад, По-английски

I encountered the following problem (from last years' zhautikov olympiad). You're given a rooted tree, representing a structure of volunteers. There are Q queries. Each query is the following: you are given a node and a number Ai of tasks. If the node(a volunteer) has no subordinates(children in the tree) then he does the tasks. If he has K subordinates, then there are two cases: if K divides Ai, then the Ai tasks are distributed evenly across all the children, e.g each subordinate receives Ai/K tasks. If K doesn't divide Ai, then the tasks are discarded. The question is, given the tree and the Q queries, consisting of which volunteer receives tasks first, and how many tasks he receives, print the number of discarded tasks for each query. Constraints: Number of nodes in the tree and number of queries is <= 100,000, number of tasks for each query is max. 1,000,000. Can anyone give me a solution to this problem? I've been thinking awhile and I feel stuck.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

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

link to problem please??? or at least some samples???

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

    I found a link to the problem.

    The problem is a simple brute force, at every node, as long as the number of tasks is divided by the number of children then you should visit your children, and if not then the current number of tasks for this node will be ignored.

    the time complexity for each query is log(number of tasks) because every time you visit a new child, the number of tasks is divided by something.

    the only thing to consider, is when the number of tasks for a node reaches 1 then you should check if this node leads by a straight chain to any leaf.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      the time complexity for each query is log(number of tasks) because every time you visit a new child, the number of tasks is divided by something.

      But you don't visit only one child for each node, do you?

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

        the more children each node has, the less nnumber of tasks will be passed to each child, and the less depth I will go through the tree, so I guess this aproch should be enough to pass the problem, if only this problem was available to submit in some judge, then we might get sure about it.

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

          Your solution is clearly O(N * Q). Consider a full binary tree and each query as the root and 2^17 tasks.

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

            that's right, I didn't consider that case :/

            do you have any ideas for a better solution :D ???

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

Is there any online judge with this task up?

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

    I'd also like to know if there is an online judge with the problems from recent IZHO, but I couldn't find any.

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

For each node compute following dp — A[j] is the answer, if we give j tasks for each of its children, 1 <= j <= 1000. Also for each node A remeber the highest node in A's subtree that has >1 children(A itself if A has >1 children), i'll call such node A's superchild below.

So to answer the query u just simulate the process, but if for some node we are going to give its children <=1000 tasks we already know the answer. If some node has 1 child, go to its superchild directly, skipping everything on the way — these nodes are meanignless to consider obviously.

Thus precalc works in O(N * 1000), where N is number of nodes in tree, query works in O(1000), cause we will not consider more then 1000 nodes(cause we dont give <=1000 tasks for some node's children — we already know then answer then, thus we only consider nodes that have to work with >1000 tasks, thus there wont be >10^6/1000=1000 such nodes).

Correct me if i am wrong

Edit: typo

→ Ответить