### Temotoloraia's blog

By Temotoloraia, history, 10 months ago, ,

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

• +17

 » 10 months ago, # |   +14 Where are they? I can't find them on the IOI website and haven't got any email.
•  » » 10 months ago, # ^ |   +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.
•  » » » 10 months ago, # ^ |   +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.
•  » » » » 10 months ago, # ^ |   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.
•  » » » » » 10 months ago, # ^ |   +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.
 » 10 months ago, # | ← 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.
•  » » 10 months ago, # ^ |   +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.
•  » » » 10 months ago, # ^ | ← 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]  » 10 months ago, # | ← 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. •  » » 10 months ago, # ^ | ← Rev. 3 → +8 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.
 » 10 months ago, # |   +1 Practice tasks are now available online.