NWAYS - Editorial

editorial
, , ,
3

@siehpe your code gives WA for case 1000 1000 as while calculating the matrix you are not taking modulus which may cause overflow and especially the sum calculation part, take modulo there also and it will be fine

1 Like
4

@apptica thanks that worked!

1 Like
5

What is wrong with my solution @saurabh060792 ? CodeChef: Practical coding for everyone

1 Like
6

If I had wrote it in the form of double summation… Life would have been easier

3 Likes
7

how is this no (2000006) achieved in many solutions to solve ?
j-i can be @ max 10^6-1 and k can be max 10^6 so that makes 2*10^6-1 ?

Thanks

1 Like
8

This question may be good for other contests like Long Challenge or Cook-offs but they certainly aren’t supposed to be given for Lunchtimes . I have explained this in this post.

3 Likes
9

hi,
please check my code
what wrong with this??
http://www.codechef.com/viewsolution/7065805

1 Like
10

@deepak100 here is AC of your code http://www.codechef.com/viewsolution/7070722. Your statement sum = (2*sum%m - n)%m; has problem because modular operations of (a%m-b)%m is not valid always as a%m < b also basically what you have to do is add m to it and calculate modulo

2 Likes
11

what is the formula to get 2nd last line from 3rd last line in your explaination??
∑i=1n(n−i+k+1k+1) Hockey Stick Identity
=∑i=k+1n+k(ik+1)

1 Like
12

thank u @apptica
i was confused with expression
sum=(2sum%m - n+m)%m; and sum=(2sum%m - n)%m; because if we add any no. m to a no. n and take mod with m then it must resultant 0 …ie. (n+m)%m==n

1 Like
13

I think he has used the identity C(n+r,r) for range of r . I read this from https://proofwiki.org/wiki/Sum_of_r%2Bk_Choose_k_up_to_n

14

is there a need to evaluate inverse factorial

can’t we evaluate nCr(n, r) as (fact[n]/(fact[r]*fact[n-r])) % mod ???

15

@mohitbindal644 you cant do this because to store factorial of large numbers without mod will overflow the size of the defined variable whether it is even long double. Now in fact[] array you will store fact[i] as mod so you need to use inverse modulo

16

I do not get how did you changed the mod to that formula with -n at the end… Can someone stepwise and split and derive please?

17

Hi i still couldn’t understand how is it ∑i=1 n(n−i+k+1 k+1) = ∑i=k+1 n+k(i k+1)
It will be good help if someone breaks down them into sub steps?
I went through link posted by amitkpandeykgp

18

links to solutions are not working!

19

generally people just approximate the max usage of memory. I think this must be the reason.I used 2000005

20

Exactly. !

21

Please see it in reference to the theorem: Art of Problem Solving

1 Like
22

I could not understand how ∑i=k+1n+k(ik+1) came from ∑i=k+1n+k(ik+1). Could you please elaborate?