hmehta's blog

Topcoder SRM 784
By hmehta, history, 5 years ago, In English

Hey All!

Topcoder SRM 784 is scheduled to start at 11:00 UTC -4, April 24, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to Witaliy, lazy_fox and misof for writing the problem set and coordinating the round. Also thanks to a.poorakhavan for writing the editorials.

This is the second SRM of Stage 3 of TCO20 Algorithm Tournament.

Stage 3 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

Some Important Links
Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)

Good luck to everyone!

  • Vote: I like it
  • +47
  • Vote: I do not like it

Comments Comments (31)
| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

what happened to the practice rooms of srms before 780 ?

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

    Hey, we had some issues recently with the applet and web arena — thus we are trying to keep the load less till the time we resolve it. I think after today's SRM we should be able to bring them back.

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

      Hey, they were not up after today's SRM so I was wondering when we can expect them to be back?

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

When I open some code to challenge it, it pops up in a tiny window on my second monitor. Any idea how to fix it? See this moment https://www.youtube.com/watch?v=LAWlaoLoLQI&t=43m28s

I use applet arena on Ubuntu with two 1080p monitors.

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

    Not a solution, you can disable second monitor and use only one

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

Could not compile or submit in the last 10 minutes of contest... Any updates on when the arena will be updated?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    Very sorry for that — Oh I saw the issue you had. Are you using web arena? or the Java Applet.

    The new arena will take time — new databases, architectural design etc

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

      My clock said I still had 5 minutes (Firefox) and 2 minutes left (when I tried later in Chrome). Even if I had somehow gotten out of sync, there was no error message or anything. This happened in both Firefox and Chrome.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it -16 Vote: I do not like it

        Please use Java Applet until we come out with the new arena. Web arena has known bugs which we are not concentrating on.

        topcodr.co/SRMGuide — to help you setup the applet.

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

          This is news to me! Was there an announcement somewhere? Are there notifications on the web arena about this that I missed?

          → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Editorials: https://www.topcoder.com/single-round-match-784-editorials/

Thanks to Arpa

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

    Why the hell are you waiting $$$O(720 ^ 3)$$$ operations on double in problem B ?:(

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

      It is easy to fit in 2s. But I don't know before implementing :)

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it -10 Vote: I do not like it

        Complexity should not intimidate participants with such high constraints

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

          On a previous round I calculated the determinant of a $$$1000\times 1000$$$ matrix so there was no question that this would suffice. :)

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

Obviously the strategy error is on me, but feel like today's 500 should be 550 ish given the amount of implementation it took (and it's quite clear not many people got 500 anyway).

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

    Yes, I agree. In retrospect, the medium problem should have been worth more.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In the 500 problem how to get the probability of getting one permutation from another after we calculated probabilities of getting identity permutation from each permutation?

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

    Probability of getting $$$q$$$ from $$$p$$$ is equal to probability of getting $$$p^{-1}q$$$ from identity. This is genius!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      I think it's genius...

      EDIT: I didn't notice too.

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

        I seriously think it's genius, because I didn't notice it during contest. I used the naive solution in $$$O((n!)^2n^2 numSwaps)$$$, but stopped after $$$80$$$ iterations.

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

    (The same thing aid said but more verbosely:)

    Imagine starting with N objects of different colors in a row, e.g., (red,green,blue). You can now use DP to simulate all possible swaps at the same time. After each swap, you have a collection of information of the type "the probability that now I have the order (red,blue,green) is 0.15".

    The main observation of the whole problem is that you just need to do this once, and not once for each starting permutation. This is because if you know that the final probability of going from (red,green,blue) to (red,blue,green) is 0.23, then for any starting permutation P=(p0,p1,p2) the probability of going from (p0,p1,p2) to (p0,p2,p1) is 0.23.

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

    Actually, there was enough time to run first part starting from every permutation separately, after doing numSwaps = min(numSwaps, 100).

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

      True. If you make the observation that a lot of swaps = close enough to the uniform distribution, you can do that :)

      (IIRC, in general you need roughly Theta(n log n) such random swaps to shuffle an array well enough, but I don't remember the exact math behind that at the moment. One should still use the Fisher-Yates shuffle, obviously, but it is fun to know that random swapping can actually converge to the correct distribution rather quickly. Of course, you need to allow swaps that do nothing, otherwise each swap toggles the parity of your permutation.)

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

In 500 I don't understand the editorial, which just mentions Gauss. I got to the following problem. I would like to calculate an E[state] = p1*E[state1]+..+pn*E[staten]. The problem is that E[statei] depends on E[state] — the recursion is cyclic. How can I break that using Gauss?

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

    There will be $$$n$$$ equations one for each $$$state$$$. You can write them as $$$AX=B$$$ where $$$A$$$ is $$$n*n$$$ probability matrix and $$$X$$$ is $$$n*1$$$ vector of expected values.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +41 Vote: I do not like it

I want to complain about a 500-pointer. The mentioned observation is cool and I guess I understand it intuitively. The issue is that it had nothing to do with the problem and the solution — those were sadly quite standard/boring. And $$$O(720^3)$$$ seemed scary.

Also, I guessed a solution to the last problem from the sample output. I just moved one row and one column, then the pattern was obvious.

EDIT: I agree with misof's comment below that it was my fault to be scared of $$$O(720^3)$$$ from Gauss. The constant factor is small.

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

    Gaussian elimination has a small constant in its time complexity. Solving n equations requires something like n^3/3 multiplications and n^3/3 additions, if I recall correctly. (This is because you are processing smaller and smaller squares of the matrix, and sum(i^2) is roughly n^3/3.) That is something like 125M of each which shouldn't look that scary. Plus, it's cache-friendly.

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

      So 125M is the new standard for 2 seconds, smh

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

        I'd say it's the standard for 1 second if not less.

        → Reply