Question-https://www.codechef.com/problems/ADDSQURE

Solution - https://www.codechef.com/viewsolution/38915117

P.S.- Found this in one of the submissions, now cant find the real author

Question-https://www.codechef.com/problems/ADDSQURE

Solution - https://www.codechef.com/viewsolution/38915117

P.S.- Found this in one of the submissions, now cant find the real author

In this solution at first you are sorting the lines on both axis. Now in this problem **ADDSQURE**

it’s given that you are only allowed to add one line of form `y = bi where 0<=bi<=h`

so lines on X axis remains unchanged now if you want to make squares than it can only be the size of the all difference( > 0 obviously) possible between lines on X axis.

So after sorting you are looping through the all possible difference which is `1 to W`

, now let’s say your current difference is `diff`

, now we’ve to check if there exist pair of lines in **X axis** whose difference is `diff`

. So how will you check it? you can do that using **binary search**, as all X are sorted.

```
> bool find(int x, vector<int> &arr)
> {
> int i = 0, j = 1;
> while (i < arr.size())
> {
> if (binary_search(arr.begin() + i + 1, arr.end(), arr[i] + x))
> return true;
> i++;
> }
>
> return false;
> }
```

In this `find()`

function you are looping through each `X = a[i]`

given into the input and checking if `a[i] + x`

where `x`

is **current difference** `diff`

. if it exist which means that we’ve difference of `diff`

on X-axis now you are checking that if the same `diff`

exist in Y-axis using same `find()`

function **if yes** then you’ve square with `side = diff`

so `total_no_of_square++`

which is `ans`

in your code. **else** you’ve to **exactly one** line into Y-axis such that the new line added makes difference `diff`

to any of the lines already present in Y-axis. let say the current line is `y = b[i]`

then you’re adding line `(y-diff)`

and `(y+diff)`

if lies in range of `[0, H]`

. You’re adding this Line by doing insert operation on each multisite of lines. now whichever lines you’ve added create **maximum different difference (maximum square with different area)** is your answer. so final answer will be `no_of_square_already_exist`

(which is answer in your code) plus the size of the the maximum multiset (i.e the newly added line which creates the maximum squares).

I hope you got it. I am not good at explaining but this is really good solution I found for this problem. thanks.