### hmehta's blog

By hmehta, history, 3 months ago, ,

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.

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)

•
• +87
•

 » 3 months ago, # |   0 Remainder: Contest starts in less than 1 hour.
•  » » 3 months ago, # ^ |   +8 Thanks for Competing :)Here are the Editorials: https://www.topcoder.com/blog/2018-tco-algorithm-round-3b-editorials/
•  » » » 3 months ago, # ^ |   +3 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...)
•  » » » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   +24 Anyone with positive score either in Round 3A or 3B will get a T-shirt, right?
•  » » 3 months ago, # ^ |   +27 Yes.
 » 3 months ago, # |   +19 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.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +28 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.
•  » » » 3 months ago, # ^ |   0 Yeah, the resulting summands are the same, but the ideas used are more elementary. Thanks!