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

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

1 | tourist | 3557 |

2 | Radewoosh | 3468 |

3 | Um_nik | 3429 |

4 | Petr | 3354 |

5 | Benq | 3286 |

6 | mnbvmar | 3280 |

7 | LHiC | 3276 |

8 | wxhtxdy | 3258 |

9 | ecnerwala | 3214 |

10 | yutaka1999 | 3190 |

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

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 173 |

4 | antontrygubO_o | 166 |

5 | Vovuh | 165 |

6 | PikMike | 164 |

7 | rng_58 | 160 |

8 | majk | 156 |

9 | Um_nik | 155 |

9 | 300iq | 155 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 10:18:47 (e2).

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.