Hi guys. Let's discuss IOI 2019 practice problems. How to solve second problem "Job Scheduling" ?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 23:34:21 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Where are they? I can't find them on the IOI website and haven't got any email.
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.
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.
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.
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.
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.
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.
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.
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.
Here is the proof:
Replace tree with rooted forest. If maximum $$$\frac{u[x]}{d[x]}$$$ is in one of its roots we can use it because of exchange argument. Otherwise, let's say the contrary: that we don't use the maximum immediately after using its parent, however after using its parent we have rooted forest there that vertex is optimal — contradiction.
Practice tasks are now available online.