Блог пользователя hmehta

Автор hmehta, история, 6 лет назад, По-английски

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)
  • Проголосовать: нравится
  • +87
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Remainder: Contest starts in less than 1 hour.

»
6 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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.

  • »
    »
    6 лет назад, # ^ |
    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.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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