adaptatron's blog

[Video Editorial + Practice Contest] : Bitmask DP ft. 1955H: The Most Reckless Defense
By adaptatron, 8 months ago, In English

I created video editorial for H. The Most Reckless Defense from last Div 3 Round (CF Round 938). It talks about Bitmask DP, exponentials, and how to approach problems with long description.

Youtube Link : https://youtu.be/bBTW58NEoJ4?si=zItmAtlyEGBiNMG_

Here's a practice contest on bitmask and bitmask DP

If you need any help or hints for the practice problem, you can ask on my Discord Server or on the Twitter thread. In case you are interested, you can also checkout my youtube channel

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

bro can u also add editorial for G? I like your explanations a lot

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

    G was a "by the books" problem. There was nothing new apart from one small observation, so I don't really have any innovative insight to present there. If you are struggling to understand the core idea, it means that you are not well versed with the 3 problems that I mentioned as a prerequisite for a recent Div 3 problem : H. GCD is Greater. They are:

    • Find the maximum pairwise gcd in an array.
    • Find the number of pairs with gcd $$$g$$$.
    • Find the sum of gcd of all pairs of an array.

    If you can answer the algorithms for these 3 without a sweat, and you are still struggling with G, than you're probably stuck with that time limit issue due to reallocation of vectors. Not a big deal. You learn something new, and you move on. Life is short. Just remember to not reallocate large vectors in future.

    But if you don't know how to solve these 3 problems, I would suggest you to do some research on this topic. The trick of computing the answer for multiples of $$$g$$$ and then iterating in reverse order is fairly standard. Let me know if you have any queries.

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

      is tc of mx*log(mx) intended?
      (if I'm polluting the blog comments, tell me I'll stop)

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

        Yes, so the constraints could be like $$$n \leq 10^5$$$ and $$$a_i \leq 10^6$$$. With these constraints, whatever you think would fit within time limit.

        → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Hi, why have you removed the tutorials/resources from your website ? I am seeing only Codeforces and Atcoder in the navigation section.

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

    They are not deleted, you can still access them from homepage ==> More. I just removed it from the navigation panel since I don't think a lot of people really use it, and instead rely on the direct link that I share in the blogs.

    If you want me to add specific items back to the navigation panel, let me know which ones.

    → Reply