Single Round Match 798
Topcoder SRM 798 is scheduled to start at 12:00 UTC-5 on Jan 23, 2021.
Registration is now open for the SRM in the Arena or Applet and closes at 11:55 UTC-5. The coding phase will start at 12:05 UTC-5, so make sure that you are all ready to go.
This SRM will award points towards Stage 3 of TCO21 and also the qualifications for TCO21 Regional Events
Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),
Best of luck!
- the Topcoder Team
500: Instead of counting number of inversion which is much harder but oeis-able, we use minimum number of swaps.
250: https://atcoder.jp/contests/abc169/tasks/abc169_f
But the time limits were much stricter in srm bcz of which I got TLE in only 1 case :(
900 was basically a simplified version of this: https://acm.timus.ru/problem.aspx?space=1&num=1519
500 was also google-able: https://math.stackexchange.com/questions/589356/derangements-of-permutations
If I'm not mistaken, for 500 that stackexchange resource proposes an $$$O(n^3)$$$ solution. How do you improve it to run in $$$O(n^2)$$$?
It's not O(N^3) because you don't need to compute that formula for all N. Basically we iterate over the number of cycles K and then apply the formula to find each d(N, K) for the fixed N and K.
Actually, we can do away with O(n^3) as well, precompute our answers and put them in the code.
That's actually exactly what I did during the contest LOL. I'm trying to upsolve it in $$$O(n^2)$$$ as an excercise.
D — Urban Planning has a subproblem which counts expected no of cycles in a permutation.
There isn't much difference between soln for permutation and derangements.
I guess it's time to start downvoting blog for having bad problems?
The website was causing problem during the contest and even now!!!
I didn't notice any during contest. Which one did you experience?
The page was not loading, there was connection problem from topcoder side
Is there a time when TopCoder website doesn't have problems?
Are you guys able to access topcoder arena? For me, it throws 404 error.
I wasn't able to open the arena, the java applet wasn't working, I am facing this problem a lot of time nowadays, it gets stuck in downloading and never opens, sometimes using a VPN works else it's just a pain.
Why is that so hmehta?