Problem Link:
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.