We invite you to participate in CodeChef’s Starters 84, this Wednesday, 5th April.
Time: 8:00 PM — 10:00 PM IST
Note that the duration is 2 hours. Read about the recent CodeChef changes here.
Joining us on the problem setting panel are:
Setters: Ram grayhathacker Gopal Pandey, Arun Arun_bro1 Sharma, Deep ZetaFunction Raval, Hitesh lazy_iterator Jindal, Shanu ShanuSingroha Singroha, Shaurya Shaurya_Bhalla Bhalla
Testers: Abhishek abhidot Jain
- Statement Verifier: Kanhaiya notsoloud1 Mohan
- Video Editorialists:Sundar K Letscode_sundar, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc , Rohit ezo_tihor Oze
- Text Editorialists: Nishank IceKnight1093 Suresh
- Contest Admins: Yash yash_daga Daga
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
I'm Sorry for the big gap b/w SUM_OR and MEX_SEQUENCES, still I hope you'll learn a cool combinatorics trick from the editorial of MEX_SEQUENCES and lots of cool ways to modify equations to handle overflows from the last problem.
One polite suggestion from my side would be please don't put googlable subproblems of a problem like many coders just go to oeis and copy-paste the formula/solution whereas those who solve the question by themselves get lower rank :(
An example: SUM OR has a formula on oeis (I got to know after the contest ended I did this problem using dp with maths submission).
Can you explain your DP approach briefly?
Sure!
Here dp defines, $$${dp[bit\space number][carry][flag] = no\space of\space ways}$$$.
Here $$$flag$$$ was just to ensure $$$X$$$, $$$Y$$$, and $$$Z$$$ are all non-zero.
I just tried all $$$8$$$ possible combinations for each bit till $$$61$$$.
To fulfill the condition $$${X + Y + Z = N \space and\space X\space |\space Y\space |\space Z\space = N}$$$.
I checked at each bit the resultant parity is the same as of $$$N$$$ or not.
i tried implementing the same thing but this approach is giving me TLE.
please see,
Use fastio (if not using) and remove endl with '\n' and don't do res %= mod always (as it cost much time) better to use that only when an addition is happening. or you may try replacing some long long to int again (except N).
i was doing mod too many times thanks
you're welcome :)
But wouldn't such a person have to realize that the answer only depends on the number of set bits in N? Like you I tried the DP approach and I only realized a more efficient approach is possible when my solution TLE'd, so I feel like that's a non-trivial observation and if a person realized the answer only depends on the number of set bits and guessed the pattern that's basically like solving the problem fully.
Did you mean solving a problem by just looking at the output and finding a pattern at oeis is better than solving problems logically? (No offense to anyone)
I would be agree with you if the problem would have been Div1 $$$A$$$ or $$$B$$$ but putting at Div1 $$$D$$$ isn't good I think. We can't expect to just find the pattern for a Div1 $$$D$$$ problem.
I solve without dp . It logically makes sense that the bits which are set in n corresponding to that one of x,y, and z have their corresponding bit set to satisfy all the conditions. Let x be the number of set bits. Then, We have to find the number of Ways to distribute these x different bit positions among 3 values. Which is a combinatorics problem.
for SUM OR problem
The equation proposed in editorial is 3^k — 3*2^k + 3
During contest, I came up with the equation 3^k — 3*( 2^k — 1)
Both the equations are same but I was getting wrong answer during the contest
Can someone clarify??( I think it may be because of modulo that both the equations aren't same)
My submission
Change
__builtin_popcountto__builtin_popcountllfor obvious reasons.Time to die
Was it the only reason to set the constraints to 2^60 ?
Perhaps :)
I faced the same issue man. But somehow figured it out in the end!!!
How many of you liked the new change in the contest duration? I like it a lot coz I think it'll reduce the no. of cheaters as many of them cheat in the last mins of contest.
How will it change now?
I like the shorter duration. Apart from the reduced cheaters, it's also sufficient for most participants I believe. I rarely do anything in the last hour, and it was only in place to give more time to lower divisions (3/4), and they didn't want to end the contest at different times for different divisions. I don't know why they only made this change now. But much appreciated. For a slightly harder contest, 2.5 hours duration might be better, just like they did for Starters 83 (which was rated for all).