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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 194 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 174 |

5 | tourist | 166 |

6 | Um_nik | 164 |

6 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 162 |

10 | 300iq | 156 |

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

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2020 16:19:16 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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:

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.