hmehta's blog

By hmehta, 5 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • -27
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

500: Instead of counting number of inversion which is much harder but oeis-able, we use minimum number of swaps.

»
5 weeks ago, # |
  Vote: I like it +44 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    But the time limits were much stricter in srm bcz of which I got TLE in only 1 case :(

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)$$$?

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

      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.

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

        Actually, we can do away with O(n^3) as well, precompute our answers and put them in the code.

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

          That's actually exactly what I did during the contest LOL. I'm trying to upsolve it in $$$O(n^2)$$$ as an excercise.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

I guess it's time to start downvoting blog for having bad problems?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The website was causing problem during the contest and even now!!!

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Are you guys able to access topcoder arena? For me, it throws 404 error.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

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

    Hey! I am not sure what the issues were, will look into the logs and make sure these are resolved before next match. I will reach out to you on email to know some morr details.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hmehta Can share link editorial of the last SRM?