hmehta's blog

Topcoder SRM 802
By hmehta, 4 years ago, In English

Topcoder SRM 802 is scheduled to start at 07:00 UTC-5 on March 19, 2021. 

Match Forum

Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-5. The coding phase will start at 07:05 UTC-5, so make sure that you are all ready to go. Click here to what time it starts in your area

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
  • +42
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Gentle Reminder: Round begins in 15 mins :)

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

    man go and fix your website first .Arena never works and today applet is not opening and saying "cannot verify ....." .

    I mean what is problem in having simple website on which we can read the problem and submit instead of getting thrash hacker like feeling in applet ?

    Quality of problems are already lowest among all CP websites (don't know about today though) and probably interface too .

    → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it
  • When your soln took 2*TL for n=30 and worked for all other testcases.
  • You open solns for hacking and find people using bitsets.
  • Felt cheated man.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Wow, you did not realize you can count edges with bit operations and still went with coding that bruteforce? You have some great balls man

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

      This was the last brute force code I compiled during the contest. I was just waiting for the contest to get added to the practice room before commenting again. I'm happy that changing it to bitmasks and __builtin_popcount still gets a TLE. Probably I need that precalculated popcount. I'm sure I would have never thought about this last optimisation on my own even if I would have used bitmasks.

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

Editorial draft

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

Medium is such a trash problem it is not even funny. Very fun just optimizing trivial bruteforce. I haven't managed to squeeze it sufficiently and I don't see anything that can be easily optimized in my code

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

    You could try to precalculate bitcounts for integers from $$$0$$$ to $$$2^{16}$$$, and then use sum of $$$precalc[x\ and\ (2^{16}-1)]$$$ and $$$precalc[x\ shr\ 16]$$$ instead of __builtin_popcount(x).

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

      Yes, that makes it ~40% faster, but duh :|... Key observation in this problem ]:->

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

    For me, the thing that helped is #pragmas which enable the POPCNT instruction.

    Can't really show them though, as the old site showing the solutions doesn't work for me.
    And we learned the hard way that complaining about the site doesn't help.

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

      Your accepted soln link.
      Also clist.by hosts all submissions. (One needs a clist.by account.)

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

        Yeah, thanks, I see it now. The #pragma GCC target("popcnt") part might be enough.

        To experience the bites of UI though, try logging off TopCoder and proceeding with the link. Note that you can't log in from there. Also, you can't log in coming from where I did, when there's the "login" button in the corner. Fun, right?

        That said, the clist.by solution viewer is new to me, so, thanks!

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

hmehta why SRM 802 is not in the practice room?

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

hmehta

Please open the practice room of SRM802.

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

recursive dp solution for div2 hard: https://shadekcse.wordpress.com/2021/03/20/srm-802-div2-hard-by-dp/

wasn't able to run systest though as practice room is not up. But this solution passes all sample tests.

→ Reply