hmehta's blog

TCO18 Algorithm Round 3B and Parallel Rated SRM
By hmehta, history, 6 years ago, In English

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)
  • Vote: I like it
  • +87
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Remainder: Contest starts in less than 1 hour.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for Competing :)

    Here are the Editorials: https://www.topcoder.com/blog/2018-tco-algorithm-round-3b-editorials/

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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...)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Anyone with positive score either in Round 3A or 3B will get a T-shirt, right?

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

The medium problem can be solved without dynamic programming.

  1. 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.

  2. The maximum which we are asked for can be represented via subset minimums using the inclusion-exclusion principle.

Here is an example implementation.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +28 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, the resulting summands are the same, but the ideas used are more elementary. Thanks!

      → Reply