### sarthakk_26's blog

By sarthakk_26, history, 2 months ago, ,

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.

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 sarthakk_26, 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!

• +23

 » 2 months ago, # |   +21 You should've held it on April 20th.
 » 2 months ago, # |   0 Since the contest is public I assume Codechef must be giving laddus to the winners (Top 3), are they?
•  » » 2 months ago, # ^ |   +5 As of now, no.however, we are in conversation with them.I will let you know asap.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +12 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.
 » 2 months ago, # |   +8 Can someone please provide a hint for NUMWAY
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 how exactly did you find the formula. i tried searching myself but could not find it
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Just google OEIS 10 670. First link had the formula Link
•  » » » » 2 months ago, # ^ |   +6 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.
•  » » 2 months ago, # ^ |   +15 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.
 » 2 months ago, # |   +1 How to solve LOLO AND CHOCLATES??
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 Assume $p(x)=a_0+a_1 x+a_2 x^2.....a_n x^n$ Then, $p(1)=a_0+a_1+a_2.....a_n=M$Also, let N=M+1 and notice that N is greater than all the coefficients(all coefficients being non negative) $p(N)=a_0+a_1 N+a_2 N^2.....a_n N^n=K$We get $a_0 = ( p(N) \mod N ) = ( K \mod N )$ $a_1 = (K-a_0)/N \mod N$and so on.... This helps in finding the unique polynomial required : )
•  » » » 2 months ago, # ^ |   +4 what is complexity of code ?as we have to move until we dont get 0 in numerator.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +12 In the end you just need to convert K in base (M+1) so the coomplexity is log(base M+1)K
 » 2 months ago, # |   +4 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.
•  » » 2 months ago, # ^ |   +5 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.
•  » » 2 months ago, # ^ |   0 Yes I also used binary search but it was giving wrong answer.link to submission
 » 2 months ago, # |   0 how to solve : MORALE99
•  » » 2 months ago, # ^ |   +1
 » 2 months ago, # |   +1 Editorial???
•  » » 2 months ago, # ^ |   0 Coming up shortly.
•  » » » 2 months ago, # ^ |   +3 can u explain the question MORALE99 . On seeing solution i think i misunderstand the question. Thanks.