CK87QUER - editorial

Problem Link:

Practice
Contest

Author: Mohammad Shahhoud & Said Sryhini
Tester: Hasan Jadouh
Editorialist: Mohammad Shahhoud

Difficulty:

Simple

Prerequisites :

Two Pointers, Simple Math

Problem:

Given Q queries, find the number of solutions for A^2 + B \le Y, A is any positive integer and 1 \le B \le 700 and 1 \le Y \le 10^{10}.

Explanation:

For each Y value, you can loop through all B values from 1 to 700 then :

A^2 + B \le Y ==> A^2 \le Y - B

So now we have to find the number of A values that makes the previous equation true:

A \le \sqrt{Y - B}

So find the square root of Y - B and add its value to the answer.

Complexity: O(Q * 700)

Two pointer solution:

We can notice here that A value cannot exceed 10^5 becuase Y maximum value is 10^{10}, so depending on that we can solve all queries together. First let’s sort all queries by their Y values, now we can loop on all values for A and B, let a be the iterator on A values and b be the iterator on B values.

Another thing to notice, if all queries are sorted, then for query i, if a^2 + b \leq Y_i is true for some values for a and b, then for all queries j such that i \le j \le Q the same holds, so we can create a helper array, let’s call it arr, where arr[i] will hold the result for the query i in the sorted array.

How to add (+1) value for all queries i \le j \le Q ?

This can be done by adding (+1) in arr[i], where i is the first query that make the equation true in the sorted array, then in the end we can this:

arr[i] += arr[i - 1]

Becuase each correct solution for query i is also a correct solution for query i + 1.

How to find the first query such that a^2 + b \leq Y_i is true for some values for a and b ?

This can be done using binary search but it will not fit in the time limit, so the other option is to use two-pointer method.

Let first fix the b value and let i and j be the indices of the queries that we need to find for those two equations:

a_1^2 + b \le Y_i and a_2^2 + b \le Y_j and a_2 \gt a_1 then Y_i \le Y_j

And if all Y values are sorted, then i \le j, so as long as a value is increasing, the index of the needed query is also increasing, so we can move a pointer as long as the equation is not true for the current query, and when we find the query that its Y value holds for the equation, we can add (+1) value to the arr[k] array, where k is the index for the needed query.

Time Complexity: O(\sqrt{Y} . B)

Check setter and tester solutions for the implementation.

Solution 1
Solution 2