Hello, Codeforces!
We would like to invite you all to participate in the Exun 2021-22 Competitive Programming contest this Wednesday, 12th January 2022 from 8 PM to 11 PM IST.
The contest is rated for both division 2 and 3. Participants of division 1 are also encouraged to participate unofficially to get a chance for prizes. The contest, authored by me and halemon123, will feature 7 problems in all divisions.
I would like to thank:
- Our contest admin, nishant403, for providing invaluable feedback on the problem set.
- knightron00 for helping with preparation.
- iscsi for testing.
- aujasvit_datta, vedantsingh1, DumbbAlgo and halemon123 for helping with testing and writing the editorials.
- Kuroni for verifying the statements.
- CodeChef team for support throughout the preparation.
Participants have to be registered here to be eligible for the following:
- From the Division 1 & 2 combined rank list:
- Top 3 school students will receive cash & sponsor prizes.
- Top 25 school students will be awarded certificates.
- Top 8 Indian school students will qualify for Lockout.
- Top 16 Indian school students will qualify for Challenge Programming.
- Top 25 school students from the Division 3 rank list will be awarded certificates.
The event is a part of our annual tech symposium Exun 2021-22. If you're interested in participating in other technical events, such as Machine Learning and Hackathons, please check out our invite!
We hope you enjoy solving the problems, good luck!
UPD: The editorials are available here.
nice yaar
Feels good to see Indian school fests consisiting of CP events. I wish it was a thing when I was in high-school. Anyways, good luck guys :D
Thank you :) We hope to see you there!
Great problems! Thank you for the contest!
Thank you :)
Nice problems. I really liked MAKEODD.
Thank you!
How to solve GOODBINTREE ?
Thanks for the contest! CIRCLEGAME and MAKEODD are some of the best problems I've seen in recent ERCs and Starters.
GRIDXOR — Cute troll cakewalk. I actually re-read the statement multiple times double and triple checking that just printing 1 everywhere would work.
SUMPARITY — Fairly easy but nice problem, pretty good for the position.
CIRCLEGAME — Brilliant problem. I had zero intuition that the answer for $$$i$$$ people could be obtained from the answer for $$$i - 1$$$ people when I first saw it, but it was really cool when it finally struck me.
RAINDROPS — Fairly obvious that the answer is going to be based purely on the number of leaves at each depth, but nice problem anyway.
GOODBINTREE — Fairly direct subtree dp + prefix sums, but fine for a rated for Div2 + Div3 ERC I guess.
MAKEODD — At first I thought this problem was just boring subarray dp where the answer for a subarray was the number of different non-zero trailing bits in it. Looking at the number of WAs in Div1 I suspect many others made the same mistake. I broke my head trying all sorts of ways to calculate the min cost for a mask doing all sorts of weird stuff that I couldn't prove the complexity of, before realizing I was being an idiot and the answer was trivially computable from smaller masks using some simple bitwise operations.
PRIMESETMUL — Ran out of time and couldn't make any inroads into the problem, so no comments here.
Thank you for the feedback, really appreciate this!
I really liked the problem CIRCLEGAME as well.
I couldn't debug MAKEODD even after spending almost 2 hours on it.Does anyone have a testcase on which this submission doesn't work?.I made a total of 14 submissions in contest .Solution idea is correct though.
Your code fails on this case:
My code prints 19, yours prints 20. Should be fairly easy to manually check the subarrays for this and see which one you're solving suboptimally.
Thanks a lot for this test case. I was literally scratching my head for 2 hours. I was only considering set bits for operations.
You don't have to consider only set bits to perform operation on mask
https://www.codechef.com/viewsolution/56343428 (replaced ss[k] with k from 0 to nn — 1)
Oh yeah, I didn't realize he wasn't doing that, here is a simple case for anyone who wants.
$$$[2^1, 2^3, 2^8, 2^{10}]$$$
Choose $$$Y = 2^7$$$.
$$$[2^1, 2^3, 2^1, 2^3]$$$
Choose $$$Y = 2^1$$$.
$$$[2^0, 2^3, 2^0, 2^3]$$$
Choose $$$Y = 2^3$$$.
$$$[2^0, 2^0, 2^0, 2^0]$$$.
Thanks a lot for pointing out the bug
The problems were nice. But the statement of GOODBINTREE was ambiguous : \
I initially interpreted "Nodes at even levels have values strictly more than their parents' values" as even level nodes requiring greater values than the all parents' values in the previous level. I'd still consider this as a valid interpretation; the statement should have been something like:
'For each node on even levels, its value should be strictly more than its parent'.
The sad part is, both interpretations also conform the the single sample provided. I spent most of the contest trying to debug my code.
Either providing more than 1 sample or a single larger sample would have worked, even with the statement issue : (
Otherwise a nice set.
I agree the statement could have been written better. Thanks for participating!
Thanks for the contest!
I managed to win the division 2 contest, solving all problems except MAKEODD (somehow I was able to get the only div2 solve of PRIMESETMUL)!
I've uploaded my solutions at https://www.youtube.com/watch?v=pLXLvKNAm_U , including the intuition I used to derive my solutions!
I especially liked the problem PRIMESETMUL. Initially, I (incorrectly) guessed that the answer wouldn't be that big, and wrote a brute-force backtracking program which worked for $$$N = 10$$$. Then, applying meet in the middle was obvious. Beautiful problem!
MAKEODD was great! btw, does "school students" imply high school students, not university ones?
It implies high school students, we apologize for the ambiguity.
The editorials are out now!
The smooth troll in GRIDXOR xD. Was a well-balanced contest. :D
It's interesting that two of my unsuccessful RAINDROPS attempts got TLE failures on different sets of testcases:
This in principle allowed a combined "frankensteiner" solution (two different code paths and a simple heuristics to make a choice between these two code paths, in such a way that TLE problems can be dodged). This is ugly, but provides a chance to score additional points if people manage to take advantage of it.
For comparison, Codeforces does not provide detailed information about failed testcases and I think that this is a good decision. Moreover, passing pretests during Codeforces contests does not guarantee anything. System tests are always a threat and this discourages implementing shoddy half-baked solutions. The existence of 12 hours hacking after educational rounds is another great Codeforces feature.