@Organic-Shilling How did you go about rectangles? I couldn’t think of a good algo 
@sandy999 First eliminate Unnecessary points, for eg, if (1,1) exists then (2,2) has no purpose, Now a valid rectangle can be made if we join the base to any point. Now try extending each of these rectangles to as far as they can go, Until another point obstructs us. You’ll have to sort points once by x coordinate and once by y coordinate. Keep an account of the maximum area. It is a lengthy question. With debugging it would have taken 1.5-2 hrs. Although I would have attempted this one before Covering. What algorithm did you use for covering ?
your solution would take O(n^2) time.
1 Like
I am sorry, I didn’t get the unnecessary points part, which points do you consider as unnecessary points? Yeah, I tried sorting once by x coordinate and once by y coordinate but I found difficulty in keeping track of the maximum area. It was frighteningly lengthy. I didn’t get a proper algorithm for Covering either. I tried maintaining a border1 and border2 to keep track of the ranges which should fit in the other sets but never mind, it was wrong and useless (as the sets can overlap in any way). Basically, I am getting a big ZERO.
So did you get an AC for Rectangles? What’s your score?
The RECTANGLE problem is much easier than COVERING.
I gave the morning session. Yeah, there are no unnecessary points I Misread the question. Put my solution as an answer @sandy999
Yes, everyone was experiencing the server problem. Also a morning session was a much easier I would say.
Do you have any ideas about COVERING?
What is the “assumed I have” area ?
Note that VARIATION can be done without binary search as well:
It’s also easier to implement this if you didn’t know about upper_bound.
Have you solved covering?
Can you share your solution for covering?
They will be different. Probably 200 for us and 40 for you.
200 is too much I think.
Nah! Our questions were really easy. But, I surely think your and my cutoffs will be different.
Haha I took the morning session actually! Got 100/200.
Was your solution for covering bruteforce?
More or less. What I did was, start with any range, not covered, find the number in this range which covers max no. of other ranges, mark them as selected, repeat until all are selected. Maybe it’s not a correct solution, but this is all I could think of.