TCO18 Algorithm Round 3B and Parallel Rated SRM
TCO18 Algorithm Round 3B and Parallel Rated SRM are scheduled to start at 21:00 UTC -4 on July 19, 2018. You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.
Click here to see what time it starts in your area.
If you are participating from web arena — You can switch to the parallel rated fun round in the mentioned way:
You can compete using:
- Topcoder Web Arena(Beta) - Please watch this video for step by step guide.
- Topcoder Java Applet - You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide here)
Remainder: Contest starts in less than 1 hour.
Thanks for Competing :)
Here are the Editorials: https://www.topcoder.com/blog/2018-tco-algorithm-round-3b-editorials/
The dijkstra in hard can be replaced by 01-bfs (by the way, does the sample code really work? 1004 edges with a log factor in python...)
The dijkstra I used doesn't have a log factor (since it's a dense graph). But actually, it looks like python doesn't pass, I had uploaded the solution before all test data was added and looks like it times out on some of them. I'll ask to update to put the Java solution there instead.
Anyone with positive score either in Round 3A or 3B will get a T-shirt, right?
Yes.
The medium problem can be solved without dynamic programming.
The minimum of two geometric distributions with parameters p and q is a geometric distribution itself with parameter p + q - pq. We can repeatedly apply this to find the minimum of a set of geometric distributions.
The maximum which we are asked for can be represented via subset minimums using the inclusion-exclusion principle.
Here is an example implementation.
Even easier. Let ti = 1 - pi / qi. Then the answer is
You can prove this by computing that at time k, the probability Bob must still be there is
Now, you sum over all $k$ to get his expected staying time. Evaluating each inner quantity as a geometric series gives the formula.
EDIT: After thinking a little harder, this is pretty much the same as above.
Yeah, the resulting summands are the same, but the ideas used are more elementary. Thanks!