rishup132's blog

Invitation to RECode 12.0 (Rated for All)
By rishup132, 5 years ago, In English

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.

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

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

$$$!!Reminder!!$$$

The contest starts in 10 minutes.

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

How to solve Chef and Subsequences?

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

    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

    $$$\sum_{i=0}^{\min(X-k, Y)} \binom{X}{i+K} \binom{Y}{i} = \sum_i \binom{X}{X-i-k} \binom{Y}{i} = \binom{X+Y}{X-k}. $$$
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you come with the final conclusion ?

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

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

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

    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.

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

![ ]()

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

cool probs. thanks.

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

Can someone help me debug my solution to chef and subsequences? The basic idea is:

  • We can ignore 0s and for each way to get sum K, we can choose any subset of 0s and the sum will still remain K, so we for each resultant value, just multiply it with 2^(count[0]) at the end.
  • If we create a polynomial for each number as (1+x^(a[i])) and multiply the N polynomials thus created, the number of ways to get sum K will be the coefficient of x^k in the product of the above created polynomials.
  • There are only 2 types of polynomials (1+x) and (1+x^-1), so we can rewrite the above expression as product of (1+x)^n and (1+x^-1).
  • Expand each term using binomial theorem and multiply them using FFT.

Here's the code (https://www.codechef.com/viewsolution/32359341)

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

    Some of your coefficients are negative. This is probably one of the issues, there are more I think.

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

      Can you elaborate? where did you find the negative coefficients?

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

        I ran on some random inputs, the coefficients were negative. N was roughly around 100.

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

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?

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

    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.

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

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.

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

    It is changed before the contest started. As we think that would be harsh for "Chef And Or" and "Chef and Rotation".

    → Reply