0x4F5F6F's blog

By 0x4F5F6F, history, 4 weeks ago, In English

Hello, Codeforces!

I have curated a Solo Practice Contest in the gym, Coding Challenge Alpha VI — by Algorave. The level of questions is medium. This is for anyone who loves giving contests and solving problems. This contest will be of most interest upto Expert rated coders, but I would also like to invite Div. 1 coders to participate as well. For anyone who wants to practice or just wants to go through the problems can register for our contest here. Hope you will enjoy solving the problems!

I would like to thank:

Contest Details:

  • Date/Time: [contest_time:105120]
  • Problems: 6
  • Duration: 2 hours 15 minutes
  • Contest Invite: Invitation Link

We hope that this contest, regardless of your background, rating and result, will increase your exposure to competitive programming and make you better than you were yesterday. Have fun!

Note: You can also register for the contest while it is going on. You may want to check out our group for past contests.

UPD: The registration has started!

UPD2: The contest begins in 1 hour, all the best to all participants!

UPD3: Contest is made private, you can access the contest with this link.

UPD4: Congratulations to the winning contestants!

  1. liympanda
  2. coderdhanraj
  3. MeetBrahmbhatt
  4. Airths
  5. Ryuga_

Congratulations to first solves as well!

UPD5: Editorial for the contest is out, check it out here

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

»
4 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

As a problem setter, I highly recommend participating in this contest...

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

    Thik Hai, Samajh Gya! xD

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

    Thanks for recommendation, Hoping for an amazing contest.

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

    jaldi jaldi flex krdeta hun ki maine problem banayi hai :')

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

    pupils are green, experts are blue, is contest mein part, aakhir kyun main lu?

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

      Pupils are green, experts are blue, we all have different reasons to practice. Find your reason too! xD

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +29 Vote: I do not like it

      Specialists are cyan, masters are yellow, contest hi toh hai, practice ke liye dedow

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

    Hoping for an amazing contest

»
4 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

As a problem tester, I really liked the problems and highly recommend everyone to participate in the contest !

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

i will give this contest .

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

Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).

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

Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).

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

Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).

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

Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).

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

Can someone please give an editorial on C?

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

    First, divide all elements by $$$2$$$ so instead of $$$L_1, L_2, \dots, L_x$$$, we'll only consider $$$L_0, L_1, \dots, L_{x-1}$$$, which imo is more natural.

    We will only consider the lowest $$$x$$$ bits of each number, and thus we can just compress a $$$10^6$$$ element array into an array of frequencies for $$$2^x$$$ elements.

    Now, we can brute force all sets of keys to check if a set can unlock all. It's an $$$\mathcal{O}(2^{2x})$$$ approach, which is totally viable at $$$x \le 10$$$.

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

      Great Explanation :) Thanks Alottt!!!

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

      If you have time, can you please give such editorials for D and E aswell, pleaase? Would really appreciate it.

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

        $$$MEX(p_l, p_{l + 1}, .... p_r) = MIN(p_1, p_2, .... p_{l - 1}, p_{r + 1}, p_{r + 2}, .... p_n)$$$ for $$$\textbf{permutations only}$$$

        so, you can maintain a segment tree that supports point update and range min.

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

          Heck, I was stupid not realizing this. That, and the fact that I tried a bit too hard investing in F made me bail out early kek.

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

        I'd be brief on D as I used quite some mathematical intuition.

        First, it's obvious that you should take $$$k$$$ working days in "succession", i.e. there are no more working days between the $$$k$$$ days you chose.

        Second — the intuition part — is that it's always optimal to pick the median of those $$$k$$$ days as the day you do work, so that the total distances are minimized.

        Sliding window may do the trick to check all series of $$$k$$$ consecutive workdays. Some initial precalculation might be needed for the first series, so that transition would be smoother.

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

      for B what was the main key idea for reducing the time complexity ? and for E too

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

        For B, I used segment tree to calculate prefix and suffix gcd and max Pi, Prefix and suffix arrays could be used aswell.

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

          without segment tree is it not possible? i think thats very much overkill for a B problem , share your code if possible smil3x_r3turns

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

            Segment tree is indeed overkill. Prefix/suffix arrays for both max and gcd are enough.

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

Can someone please tell how to solve D?

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

Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).