Greeting Codeforces Community
RECursion, the coding community of NIT Durgapur, is glad to invite you to RECode 12.0 which will be held on 27 April at 21:00 IST. The contest will be rated for both divisions.
The problems are prepared by me rishup_nitdgp. There will be 7 problems for both the divisions and 2.5 hours to solve them.
Thanks to Sachin Yadav, Taranpreet Singh and Jatin Yadav for testing the problems and their valuable suggestions to enhance the test cases. We also present our special thanks to the CodeChef Community to help us to prepare the contest and for the astonishing platform.
Prizes:
For Indian participants:
- Top 10 from the rank list will receive 300 laddus.
For Global participants:
- Top 10 from the rank list will receive 300 laddus.
For combined participants:
- Random Laddus to any 5 users: 200 laddus.
- First to solve each problem individually: 100 laddus.
- Country-wise participation: Top 10, 20, and 30 will get 30, 40, and 50 laddus as per participation.
- Country-wise performance: 200, 250, 300 laddus as per performance.
So buckle up to increase your ratings and raise on the Leaderboard. Amidst this chaos when everything is under lockdown, let us not waste this time, rather keep the spirit of coding within us alive.
Stay Home, Stay Safe, and Keep Coding.
UPD: The editorials can be found here.
$$$!!Reminder!!$$$
The contest starts in 10 minutes.
How to solve Chef and Subsequences?
We just need to find how many ways we can select +1s and -1s in a way that we select k more +1s than -1s. Suppose there are X +1s and Y -1s. The number we want is
How did you come with the final conclusion ?
The middle of the equation and the right-hand side are both counting the number of ways to choose X-k items from a set of X+Y items (we have cases for how many of the items come from the first X, and how many come from the last Y).
For each sum $$$i$$$ from -n to +n you have to find coefficient of $$$x^{i}$$$ in $$$\prod_{j=1}^{n}(1+x^{a[j]})$$$.
If you simplify the above expression, you will see that for sum = $$$i$$$ you have to find coefficient of $$$x^{i+cnt(-1)}$$$ in $$$2^{cnt(0)}(1+x)^{cnt(-1)+cnt(1)}$$$, where cnt($$$val$$$) = number of times $$$val$$$ occurs in the given array.
Since, we are not allowed to consider empty subsequences, subtract 1 from answer corresponding to sum = $$$0$$$.
And we know coefficient of $$$x^{r}$$$ in $$$(1+x)^{n}$$$ is $$$C(n,r)$$$. Calculate factorials and inverse factorials of the required numbers. Inverse factorials exist as the given modulo is a prime number.
)
cool probs. thanks.
Can someone help me debug my solution to chef and subsequences? The basic idea is:
Here's the code (https://www.codechef.com/viewsolution/32359341)
Some of your coefficients are negative. This is probably one of the issues, there are more I think.
Can you elaborate? where did you find the negative coefficients?
I ran on some random inputs, the coefficients were negative. N was roughly around 100.
In the problem Chef and Rotations my code was giving TLE link to the tle code but when i submitted the same code after the contest it is giving AC link to the accepted code.
Can someone tell me why this has happend?
After looking at your codes, I think your accepted code ran just in limit time. For the unaccepted one, you were doing unnecessary calculations. That may have led to tle. I am still not sure, that this small piece of code can make a difference.
Was the penalty for an incorrect submission was changed from 20 minutes to 10 minutes during the contest?
Before the contest, I remember it was 20.
It is changed before the contest started. As we think that would be harsh for "Chef And Or" and "Chef and Rotation".