hmehta's blog

Topcoder Single Round Match 798
By hmehta, 4 years 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

Comments Comments (16)
| Write comment?
»
4 years 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.

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

250: https://atcoder.jp/contests/abc169/tasks/abc169_f

→ Reply
  • »
    »
    4 years 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 :(

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

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

→ Reply
  • »
    »
    4 years 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)$$$?

    → Reply
    • »
      »
      »
      4 years 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.

      → Reply
      • »
        »
        »
        »
        4 years 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.

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
  • »
    »
    4 years 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.

    → Reply
»
4 years 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?

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

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

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

    I didn't notice any during contest. Which one did you experience?

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

      The page was not loading, there was connection problem from topcoder side

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

    Is there a time when TopCoder website doesn't have problems?

    → Reply
»
4 years 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.

→ Reply
»
4 years 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?

→ Reply