CHFING-Concept used

What concept was used to do CHFING?
I read the solutions but did not understand.

CHFING used some Basic Mathematical Observations along with Summing an Arithematic Progression

Yes,understood that.But what ap were you summing?
I used a different approach I think.

My approach works for every TC I can think of,but 1 TC in subtask 2 is always WA.

It is related to a concept called Frobenius number, which is the maximum number that you can’t make with given numbers. A variant of that problem is used here which deals with cardinality of set of numbers that you can’t make with given set of numbers. This is actually an NP hard problem but can be done in constant time if given numbers are in an arithmetic progression

3 Likes

Yes.
That is what I used.
From (K-1)K , all numbers are reachable.
Below that.I count numbers occuring between block so multiples.
Ex: K+N-1 to 2K,then 2K+2N-2 to 3K and so on.untill (K-2)
(K+N-1) to (K-1)*K
And notice when an overlap happens for the first time.
So summation from 1 to that overlap.

Is this what you used?
If not would you mind elaborating your solution?

1 Like

Can you give the resulting formula of you summation?

https://code.hackerearth.com/3ccf22h

You can see the code here along with the formula used

I will try to explain my approach as best as I can.
let l = k and r = k + N - 1, Now what is the lowest number you can make by adding any two numbers in [ l , r] ?
Clearly the lowest you can make is 2*l and highest you can make would be 2*r, and as we have all numbers available b/w l and r we can make every number b/w 2*l to 2*r. ( l + l + 1 , l + l + 2 , ..... , r + r - 1)
So far we can obtain numbers in range [ l , r ] and [ 2*l , 2*r ] .
Now using these numbers the lowest we can make is 3l and highest is 3r.
Hence we obtain another discoverable range [ 3*l , 3*r ].
Similarly we see that its possible to obtain numbers corresponding to the ranges :-
[ l , r ] , [ 2*l , 2*r ] ,[ 3*l , 3*r ] ....... [ n*l , n*r ] where n belongs to the set of natural numbers.
As the value of n increases the distance of different b/w (n-1)*r ans n*l deceases,
and at one point they will start to overlap, from there on all the consequent ranges will overlap too, hence there will be no more discoverable numbers there after.

To determine the point where they start to overlap we can use a simple inequality :-

(n + 1) * l - 1 <= n * r

In case the ranges n and n+1 doesn’t overlap but are consecutive i.e r*n+1 == (n+1)*l
in this case surely n+1 and n+2 will overlap and the ranges n and n+1 do not leave out any numbers in between, hence the = sign.
Above inequality reduces to n >= ( l - 1 ) / (r - l ) , substituting values of r ( = k+N-1 ) and
l ( = k ) we get, n >= ( k - 1) / (N -1)

= => n = ceil ( (k - 1) / (N - 1) )
Note : As N and k are both int, the answer to (k-1)/(n-1) will be int as well, hence ceil
function will not have any effect. As pointed out by people, even type casting
them will not help as double has a precision of only 52 bits, where as we are
dealing with 64 bit numbers.
An effective way to calculate ceil without all this is , for a/b ciel(a/b) = (a+b-1)/b

Hence we shall use n = ( k + N - 3 ) / (N - 1 ) here.

Now all we need to do is count the number of number that were unreachable up to n*l ,
as we saw these were the numbers in between the ranges we derived.
Hence the answer would be

( l - 0 - 1) + ( 2r - l -1 ) + ( 3r - l -1 ) + … + ( n * l - ( n-1 ) * r -1 ).

This forms an AP, upon finding the sum of AP and substituting values of l and r we get

EDIT: Here’s the derivation :-


our final answer :-

Ans = n * k + ( ( n-1 ) * ( n-2 ) ) / 2 - ( ( n-1 ) * n * N ) / 2 - 1

And Of course keep the mod 1e9 +7 in mind!

link to my solution :- https://www.codechef.com/viewsolution/24696823

11 Likes

Yep.that’s what I used.
Don’t know why that 1 TC is still WA though :frowning:

and don’t use ceil function to find ceil
use a/b + (a%b==0)
for ceil of a/b
My 1 WA turned into AC after that

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.

Code with WA on 2nd subtask Case 2

AC Code

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 :cry::cry:

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?