Question-ADDSQURE Problem - CodeChef
Solution - CodeChef: Practical coding for everyone
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.