Temotoloraia's blog

IOI 2019
By Temotoloraia, history, 5 years ago, In English

Hi guys. Let's discuss IOI 2019 practice problems. How to solve second problem "Job Scheduling" ?

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

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Where are they? I can't find them on the IOI website and haven't got any email.

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

    Strange, I got an email(as team leader) 13 days ago to this link, though you will need credential from the same email to login.

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

      From what I understand, credentials got sent to all contestants and leaders (unsure for deputy leaders). I've asked host if it's possible to put the tasks publicly on the website.

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

        Thanks for the information, I asked my students and they have received the message (the leaders haven't for some reason, maybe spam filter).

        I would suggest that such messages would also be sent to the person in charge of each country. I don't attend IOI every year, but I would like to follow what is happening at IOI.

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

          I understand that these e-mails were intended as usernames/passwords, which is why they were only sent individually. Although I agree, that the announcement of practice session launch should have been sent to ioi-announce.

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

Let $$$r[x]=\frac{u[x]}{d[x]}.$$$ While there exists $$$x$$$ such that $$$r[x] > r[p[x]],$$$ there exists a schedule of minimum cost such that $$$x$$$ directly follows $$$p[x].$$$ While this condition holds for at least one $$$x,$$$ merge $$$x$$$ with its parent, set $$$u'[x]=u[x]+u[p[x]], d'[x]=d[x]+d[p[x]],$$$ and update the answer appropriately. When no such $$$x$$$ exists, you should take each node in decreasing order of $$$r[x]$$$.

EDIT: This is not correct, see below.

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

    p = {-1, 0, 0, 2, 2} u = {0, 100, 0, 1000, 10} d = {1, 1, 1, 1, 1} to get optimal answer the following permutation is needed: 0, 2, 3, 1, 4. no other permutation gives this answer. With your observation r[4] > r[2] = r[p[4]] but there doesn't exist a schedule of minimum cost such that 4 directly follows 2.

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

      Yeah, this isn't correct. I think it works if you iterate over the tree from bottom to top and repeatedly merge $$$x$$$ with its child $$$c$$$ such that $$$r[c]$$$ is the maximum possible over all children of $$$x$$$ and $$$r[x]<r[c].$$$

      Alternatively, I think that over all $$$x$$$ such that $$$r[p[x]]<r[x]$$$ you can merge the $$$x$$$ with maximum $$$r[x]$$$ with its parent.

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

Similar idea to Benq: find the node with maximum? $$$\frac{u[x]}{d[x]}$$$, and merge it with its parent, if such node is a root add $$$d[i]$$$ to time and add $$$u[i] * time$$$ to the answer. Small to large is needed to obtain $$$O(nlogn)$$$ complexity.

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

    Here is the proof:

    proof
    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Practice tasks are now available online.

→ Reply