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

IOI 2019
Автор Temotoloraia, история, 5 лет назад, По-английски

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

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

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

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

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

    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.

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

      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.

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

        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.

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

          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.

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

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.

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

    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.

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

      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.

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

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.

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

    Here is the proof:

    proof
    → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Practice tasks are now available online.

→ Ответить