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:
our problem setters JainWinn, vanshdhawan60, ankush.tyagi.07 and myself.
our problem testers tanmaytaneja2, vrintle, _bLIC_, JainWinn, vanshdhawan60, ankush.tyagi.07, BitWizz and myself.
JainWinn for the amazing poster design.
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!
Congratulations to first solves as well!
UPD5: Editorial for the contest is out, check it out here
As a problem setter, I highly recommend participating in this contest...
Thik Hai, Samajh Gya! xD
Thanks for recommendation, Hoping for an amazing contest.
jaldi jaldi flex krdeta hun ki maine problem banayi hai :')
pupils are green, experts are blue, is contest mein part, aakhir kyun main lu?
Pupils are green, experts are blue, we all have different reasons to practice. Find your reason too! xD
Specialists are cyan, masters are yellow, contest hi toh hai, practice ke liye dedow
Hoping for an amazing contest
As a problem tester, I really liked the problems and highly recommend everyone to participate in the contest !
i will give this contest .
Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).
Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).
Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).
Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).
Can someone please give an editorial on C?
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$$$.
Great Explanation :) Thanks Alottt!!!
If you have time, can you please give such editorials for D and E aswell, pleaase? Would really appreciate 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.
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.
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.
for B what was the main key idea for reducing the time complexity ? and for E too
For B, I used segment tree to calculate prefix and suffix gcd and max Pi, Prefix and suffix arrays could be used aswell.
without segment tree is it not possible? i think thats very much overkill for a B problem , share your code if possible smil3x_r3turns
Segment tree is indeed overkill. Prefix/suffix arrays for both max and gcd are enough.
Can someone please tell how to solve D?
use two pointers
Auto comment: topic has been updated by 0x4F5F6F (previous revision, new revision, compare).