May Long 2019 Solutions Sketches

editorial
18

Brother let me know if u get that formula derived “n+1! - 1” i m eagerly curious to know this.

19

There is no derivation of this formula. It is very easy question, you should not think much about it. Whenever , I’ve to get a formula, I just do observation for n=1,2,3…etc.
Thats it. My friend who solved this problem,she reached the same formula just by observing and not by derivation. :slight_smile:

1 Like
20

Its simple…
I have two proofs :

1)

The output value was…
ans = (1 + 2 + 3 + 4+...n)+( (1*2 + 1*3+ ...) + (2*3 + 2*4 + ... ) + ...) + … + (1*2*3*...*n )
Nc1 + Nc2 + ...+ NcN terms…
Now see expansion of
(a+1)*( b+1) = 1 + a +b + a*b
=>(a+1)*( b+1) - 1 = a +b + a*b
(a+1)*( b+1)*(c+1) =1+ a +b + c + a*b + b*c + a*c + a*b*c
=>(a+1)*( b+1)*(c+1) -1 = a +b + c + a*b + b*c + a*c + a*b*c
hence similarly,
ans = ( ( (1+1)*(2+1)*(3+1)*(4+1)*...*(n+1) ) -1 ) = (n+1)! -1

2)

for n=1 => ans=f(n)=f(1)=1
now, f(2) = f(1) + 2 + f(1)*2 = 1+2+2
similarly, f(n) = f(n-1) + n + f(n-1)*n
putting f(n) = (n+1)! -1
f(1) = 1
f(n-1) + n + f(n-1)*n = (n!-1) + n + (n!-1)*n = n! + n!*n +n -n -1 = (n+1)! -1 = f(n)

3 Likes
21

Would really derive this while solving this problem in a contest?:joy::joy::joy::joy:

1 Like
22

Not at all… I would have found it after writing brute Force solution :slight_smile:

3 Likes
23

!!!Math-God _/\_

1 Like
24

:joy: u r joking …

25

Seriously brother math god!! @l_returns

3 Likes
26

thanks but I’m far away from being math god… :slight_smile:

2 Likes
27

How to be good in maths in competitive programming?

28

I really don’t know… I love maths since 8th standard… I just did maths from 8th to 10th… :joy:

2 Likes
29

Same quetstion. :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue: :stuck_out_tongue:

1 Like
30

I_sees… !!! _/_

31

And there is usually a good deal of difference between CF and CC editorials.

1 Like
32

what ??
…

33

Sir in question when to build roads, is it allow to build restaurant on the road

34

Just thought of this and thought it explains the formula pretty well.
a + b + a * b = (a + 1) * (b + 1) - 1.
Now, for ((a, b) , c) , we can substitute the above result as ((a + 1) * (b + 1) - 1, c)
Expanding this we get (a + 1) * (b + 1) * (c + 1) - 1. Hence, no matter how many operations you do and in what order you do, you will get (a + 1) * (b + 1) * (c + 1) * … - 1. Since the numbers here go from 1 to N, our answer become (1 + 1) * ( 2 + 1) * (3 + 1) * … * (N + 1) - 1. This is essentially (N + 1)! - 1.

Hope this helps.

2 Likes
35

How u have expanded (a+1)*(b+1)-1 ,c ?? @gameface_123

1 Like
36

Let (a + 1) * (b + 1) - 1 = d
Then, (d, c) = (d + 1) * ( c + 1) - 1
But d = ( a + 1 ) * ( b + 1) - 1 .
Hence, (d + 1) = ( a + 1) * ( b + 1)
Hence, (d, c) = (a + 1) * (b + 1) * (c + 1) - 1

1 Like
37

Please provide the link for your editorials.

2 Likes