Chef and Weird Queries

Codechef Problem Code: CK87QUER (October 2017 Cook Off Challenge)
Problem Statement Link: https://goo.gl/2ZYGZs

In the problem statement we are asked to print total number of pairs (A, B) that can be formed for a given number Y, such that A²+B <= Y and B must be less than or equal to 700.

Given Constraints:

1<=Y<=10000000000
1<=B<=700

Before coming up with an algorithm, let's solve an example for a smaller Y value, let's say Y=20.
For Y=20, we have the pairs:

Let's begin with A=1,
1² + 19 <= 20    (1, 19),
1² + 18 <= 20    (1, 18),
1² + 17 <= 20    (1, 17),
1² + 16 <= 20    (1, 16),
1² + 15 <= 20    (1, 15),
1² + 14 <= 20,   (1, 14),
and so on till 1² + 1 <= 20   (1, 1)

For A=1, we observed that, B can range from 1 to 19, thus giving us total 19 pairs (A, B) as listed above.

Now for A=2, B will start at 16 (since 2² + 16 = 20) and anything greater than 16 will add up to more than 20,
2² + 16 <= 20   (2, 16),
2² + 15 <= 20   (2, 15),
2² + 14 <= 20   (2, 14),
2² + 13 <= 20   (2, 13),
2² + 12 <= 20   (2, 12),
and so on, till  2² + 1 <= 20   (2, 1).

For A=2, we observed that, B can range from 1 to 16, thus giving us total 16 pairs (A, B) as listed above.

In both the above cases, one thing to observe is that for the very first pair generated in both cases, the value B holds is the number of pairs that will be generated for a given value of A.

For A=1,

First Pair: 1² + 19 <= 20, where B=19 and here we observed that we got 19 pairs for A=1.

For A=2,

First Pair: 2² + 16 <= 20, where B=16 and here we observed that we got 16 pairs for A=2.

So, whatever the value we get for B in the very first equation for any given A is actually the number of pairs which will be generated for that given value of A.

Solving for Y=20 has now become easier for us. We increment the value of A by 1 in every iteration and calculate respective B which will denote number of pairs for the current A value and which also add to our solution.

But, what will be the maximum value of A?

We have, A²+B <= Y, where B can have minimum value as 1.

Substituting B=1, 

A² + 1 <= Y, 

i.e. A² <= Y - 1, 

i.e. A <= √Y - 1

Hence, maximum value of A can be √Y - 1 and then we stop and print our result.

For Y=20, A <= √20 - 1 i.e. A <= √19 i.e. A <= 4 (since A is an integer and not a float value).

Y=20 can be solved as below:

For A=1, B=19,

For A=2, B=16,

For A=3, B=11,

For A=4, B=4

Hence, answer = 19+16+11+4 = 50.

Here is the twist...

One constraint to consider is 1<=B<=700. B cannot exceed 700. For B>700, we can consider B=700 by putting a simple if statement. But for larger values of Y, there will be lot of looping and your code will end up with time-out error.

To avoid this, we have to calculate number of values of A for which B>700. Let n be number of values of A for which B>700. We calculate n by calculating value of A such that for that value of A B<=700.

A²+700 <= Y

A <= √Y - 700 

n=A

For all such A in which B>700, total pairs will be 700, and hence we add to our answer n*700 and start next iteration with next value of A (i.e. A=n+1) (skipping all n values of A).

Final Algorithm:

for A² = 1 to Y-1 do

      B = Y - (A * A)

      if B > 700 then

            n = √Y - 700 

            ans += (n * 700)

            A = n

      else

            ans += B

      A++

print ans