SarthakAjmera's blog

Invitation to #include<techweed.h>
By SarthakAjmera, history, 5 years ago, In English

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!

  • Vote: I like it
  • +23
  • Vote: I do not like it

Comments Comments (23)
| Write comment?
»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

You should've held it on April 20th.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the contest is public I assume Codechef must be giving laddus to the winners (Top 3), are they?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    As of now, no.

    however, we are in conversation with them.

    I will let you know asap.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +12 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Can someone please provide a hint for NUMWAY

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how exactly did you find the formula. i tried searching myself but could not find it

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Just google OEIS 10 670. First link had the formula Link

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve LOLO AND CHOCLATES??

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 : )

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      what is complexity of code ?
      as we have to move until we dont get 0 in numerator.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +12 Vote: I do not like it

        In the end you just need to convert K in base (M+1) so the coomplexity is log(base M+1)K

        → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve MBIDOL

I have applied Binary Search on answer, but am getting WA.

link to my Code

Please help me out

Thanks!!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve : MORALE99

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Editorial???

→ Reply