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!
what happened to the practice rooms of srms before 780 ?
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.
Hey, they were not up after today's SRM so I was wondering when we can expect them to be back?
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.
Not a solution, you can disable second monitor and use only one
Could not compile or submit in the last 10 minutes of contest... Any updates on when the arena will be updated?
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
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.
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.
This is news to me! Was there an announcement somewhere? Are there notifications on the web arena about this that I missed?
Editorials: https://www.topcoder.com/single-round-match-784-editorials/
Thanks to Arpa
Why
the hellare you waiting $$$O(720 ^ 3)$$$ operations on double in problem B ?:(It is easy to fit in 2s. But I don't know before implementing :)
Complexity should not intimidate participants with such high constraints
On a previous round I calculated the determinant of a $$$1000\times 1000$$$ matrix so there was no question that this would suffice. :)
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).
Yes, I agree. In retrospect, the medium problem should have been worth more.
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?
Probability of getting $$$q$$$ from $$$p$$$ is equal to probability of getting $$$p^{-1}q$$$ from identity. This is genius!
I think it's genius...
EDIT: I didn't notice too.
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.
(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.
Actually, there was enough time to run first part starting from every permutation separately, after doing
numSwaps = min(numSwaps, 100).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.)
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?
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.
Thanks
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.
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.
So 125M is the new standard for 2 seconds, smh
I'd say it's the standard for 1 second if not less.