Greetings everyone!
I am excited to invite you all to take part in #include<techweed.h>.
The contest is organised by BITS Pilani-Goa Campus’ Centre for Technical Education in collaboration with Department of Computer Science and Algomaniax-the Coding Club.
The contest will be hosted on CodeChef.
Contest Link: Contest Link
Registration Link: Registration Link (Only for students of BITS)
You will be given 3 hours to solve 8 problems.
Date: March 29th,2020 (Sunday)
Time: 21:00-00:00(IST) 15:30-18:30(UTC)
There are prizes worth INR 10,000 for top participants from BITS, all 3 campuses (separate prizes for first year students). Although the prizes are for students for BITS, everyone is invited to take part.
I would like to thank CodeChef for providing us the platform to host our contest. The problems have been created by me SarthakAjmera, bhatnagar.mradul, ManavJ07, mac, vishisht_2 and patelaman The problems have been tested by rushabh7, arsh99, better_days_will_come and _Aaryan_.
UPD: Editorial is up!
You should've held it on April 20th.
Since the contest is public I assume Codechef must be giving laddus to the winners (Top 3), are they?
As of now, no.
however, we are in conversation with them.
I will let you know asap.
Why they must do that? Because you decided so? :)
On a more serious note, as I know, CodeChef only have rule to give laddus for the winners of the External Rated Contests besides their own monthly contests (Challenge, Cook-Off, Lunchtime). For the contests which they aren't host as "External Rated Contest", they definitely not must to provide laddus. They can do that at their discretion but it isn't necessarily. Correct me if I am wrong.
I was just asking btw, and I have given a contest in which I received laddus but it wasn't mentioned in the prize. These days they generally distribute laddus for almost every public contest. Edit: Even when our college organized a public contest on CodeChef they gave laddus and anyways the organizers can always ask for more rewards so consider it as a humble suggestion.
Can someone please provide a hint for NUMWAY
The two samples were enough to find it in oeis, so I didn't solve it and just used the formula.
But it can also be solved using FFT.
how exactly did you find the formula. i tried searching myself but could not find it
Just google OEIS 10 670. First link had the formula Link
You can notice you need to find number of ways of each of the person to get c. Let's denote it by $$$F(c)$$$, then the answer is $$$\sum{F(c)^2}$$$ over all c.
Now, $$$F(c)$$$ is just the coefficient of $$$x^c$$$ in $$$(x^0 + x^1 + ... x^9) ^ \frac{n}{2}$$$ , which can be calculated easily by NTT.
All possible ways to get a particular sum(say s) of chocolates after $$$n/2$$$ days is the coefficient of $$$x^s$$$ in polynomial (1+$$$x$$$+$$$x^2$$$....$$$x^9$$$) multiplied n/2 times. So, the final answer is sum of square of coefficients. We can use NTT and multiplicative exponentiation to efficiently multiply the polynomials.
How to solve LOLO AND CHOCLATES??
Assume $$$p(x)=a_0+a_1 x+a_2 x^2.....a_n x^n$$$ Then,
Also, let N=M+1 and notice that N is greater than all the coefficients(all coefficients being non negative)
We get
and so on.... This helps in finding the unique polynomial required : )
what is complexity of code ?
as we have to move until we dont get 0 in numerator.
In the end you just need to convert K in base (M+1) so the coomplexity is log(base M+1)K
In problem MORALE99, the output of following test case should be 2.
7 3 4
1 1 0 0 1 1 2
but this accepted submission gives 1 as output.
I went through the submission.It is wrong.Test cases are weak.Don't worry correct solutions will work fine.Sorry for the weak test cases.
How to Solve MBIDOL
I have applied Binary Search on answer, but am getting WA.
link to my Code
Please help me out
Thanks!!
how to solve : MORALE99
this will help you !!
Editorial???
Coming up shortly.
can u explain the question MORALE99 . On seeing solution i think i misunderstand the question. Thanks.