### Temotoloraia's blog

By Temotoloraia, history, 14 months ago, Hi guys. Let's discuss IOI 2019 practice problems. How to solve second problem "Job Scheduling" ? Comments (11)
 » 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.
 » 14 months ago, # | ← Rev. 3 →   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 > r = r[p] but there doesn't exist a schedule of minimum cost such that 4 directly follows 2.
•  » » » 14 months ago, # ^ | ← Rev. 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]  » 14 months ago, # | ← Rev. 3 → 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. •  » » 14 months ago, # ^ | ← Rev. 3 → Here is the proof: proofReplace 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.