Resultant formula for summation:
sum = k-1 + p*k-(p*(p+1)/2) *n + p*(p-1)/2
where p = floor(k-1)/(n-1)
You need to take care of modulus at every multiplication.
I know what the WA is for.
It’s an overflow.
Same thing was happening with me earlier, but it got fixed when I used modulo as many times as I could.
Turns out.It was an error with integer division in python.
// vs /
For the people who try this solution in C++, this line is the culprit for the 2nd test case not passing in second sub task. Both K and N are integer type variables so their division will also be int.
If we write
n = ceil (((double) k - 1) /((double)(N - 1) )
It still is not going to work because when we convert the value to double, we lose precision. N and K would be 64 bit integers but double has 52 bits for precision while 11 bits for exponent and 1 for sign. So we lose the least significant 12 bits. This causes the value of n to be calculated wrong.
A straightforward solution to this problem that I used is calculating n in the following way
n = (K-1)/(N-1)
if( (K-1)%(N-1) > 0)
n++;
This problem gave me a bad time.
2 Likes
Yeah my mistake even though I used n = (k+n-3)/(n-1) in my own program i forgot about that here, thanks.
The concept was that for given range [i,j] (i=n and j=n+k-1)
the numbers which are
between i*(p+1) and j*p (if any, both exclusive and p>=0)
can’t be generated and this fact, for different values of P gives an arithmetic progression !
From this I derived a simple formula,
- a = k-1
- b = n-1
- c = a%b
ans = ( a^2 + ab + bc - c^2)/(2*b)
P.S. n and k are from input.
same happened with me 
Why did you multiply 5000000004 in the ans variable’s expression?
Dude that’s modulo inverse of 2 w.r.t 1e9+7 , when using modulus, instead of dividing a number by some number, say x, we multiply it by inverse modulo of x.
so let me say what i think…because modulo divison doesn’t exist,we multiply by the inverse?
Hello !
I am getting WA on TASK#1 (sub task 2).Can someone tell me where i am wrong ?
Solution Link : - CodeChef: Practical coding for everyone
a small trick for division with small numbers Trick for modular division ( (x1 * x2 .... xn) / b ) mod (m) - GeeksforGeeks
can you please specify what variable indicates.
Can you please include the derivation for the “Ans” formula. It will be extremely helpful
Your approach is wrong if you take n>>k let’s say n=1000 k=5 then it will not work also you also have to take first k-1 numbers it will work fine if n=2 then no became k,k+1
Derivation for final formula Added.
Check out my answer . All the variables I used are easy to understand the solution.
Even I was stuck on it before I performed Modulo by separating into two brackets.
I edited the comment.
good explanation man