AnotherRound's blog

Help with a tree-related problem
By AnotherRound, history, 8 years ago, In English

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.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

      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?

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

        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.

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

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

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

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

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

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

Is there any online judge with this task up?

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

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

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

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

    Thank you, your idea seems correct. Sadly there isn't an online judge where I can test it :(

    → Reply