SEALCM by INCLUSION EXCLUSION PRINCIPLE

general
, ,
1

Hi,

I was trying to solve SEALCM of JAN long challenge-15.

problem link: problem link

this question can be solved by inclusion exclusion principle.

I have seen code of rajat1603

solution link: soln link

But I am unable to understand working of f[i][j] (line 84-100) and also some part of s1,s2,s3,s4,s5 and final.

It would be nice if someone can mention working of f[i][j] or provide his own way to solve this question by

inclusion-exclusion principle.

For newbies like us It would be great if such explanations will be given…

2

I don’t know the solution, but your handle is amazing :stuck_out_tongue:

8 Likes
3

My khopri is also amazing :slight_smile: :slight_smile:

Believe me,I am acquainted to you :stuck_out_tongue:

2 Likes
4

Read this : [http://discuss.codechef.com/questions/62442/explaination-of-sealcm][1]

Well rather than looking at the code you should focus on understanding the concept first.

As i have said we have to calculate y = n(NOT(A) U NOT(B) U NOT© U NOT(D))

Take a = not(A), b = not(B), c = not©, d = not(D).

y = n(a U b U c U d).

Now first expand it using Inclusion-Exclusion Principle. Then , if you really understand Set Theory , you will be able to see that to calculate the answer you will also require deMorgan’s Law.

First do it on paper and then move to coding it i.e before coding fully expand y and write it somewhere then you would be able to grasp the real solution.

And first study the concepts mentioned in Bold characters.
[1]: http://discuss.codechef.com/questions/62442/explaination-of-sealcm

1 Like
5

You are not newbie :frowning: :frowning: :frowning:
That’s 9th problem of the contest :slight_smile: :slight_smile:

1 Like
6

Hi @thechamp103,

I am not able to understand your uni function :frowning: as well as lines 77-88.
I know inclusion exclusion principle and set generation but still I am not able tto get those part :frowning:
Clearly,I have not implemented inclusion exclusion principle yet.

Could you please guide me?? :slight_smile: :slight_smile:

7

Hi @thechamp103,

You are the real champ!! I got it!

Still I want to confirm this::

Y = power(m-m/p,n)+power(m-m/q,n)+power(m-m/r,n)+power(m-m/s,n)-

    power(m-m/p-m/q+m/(p*q),n)- power(m-m/p-m/r+m/(p*r),n)-power(m-m/r-m/q+m/(r*q),n)-
    power(m-m/p-m/s+m/(p*s),n)-power(m-m/s-m/r+m/(s*r),n)-power(m-m/s-m/q+m/(s*q),n)+

    power(m- m/p -m/q -m/r +m/(p*q)+ m/(q*r)+m/(p*r) - m/(p*q*r),n)+ 
    power(m-m/p-m/q-m/s+m/(p*q)+m/(p*s)+m/(q*s)-m/(p*q*s),n)+
    power(m-m/s-m/q-m/r+m/(s*q)+m/(s*r)+m/(q*r)-m/(s*q*r),n)+
    power(m-m/p-m/r-m/s+m/(p*r)+m/(p*s)+m/(r*s)-m/(p*r*s),n)-

    power(m-m/p-m/q-m/r-m/s+m/(p*q)+m/(q*r)+m/(p*r)+m/(r*s)+m/(p*s)+m/(q*s)
   - m/(p*q*r)-m/(q*r*s) - m/(p*q*s) - m/(p*r*s) + m/(p*q*r*s),n)

where p,q,r,s are A,B,C,D.
Is this your Y??

1 Like
8

Yup that looks about right.