I appeared for the afternoon session. I’m pretty sure I’m scoring a big old zero. I ended up wasting too much time on Rectangles, and had very little time left for the Covering. I submitted what I think was the correct solution at the very last moment, but the server shut down while it was compiling. I don’t think it’ll get evaluated.
Here’s are links to the problems:-
Can someone share the problems from the morning session?
I was able to think up a brute force algorithm for Covering, but I don’t think it would’ve finished running within the lifetime of the known universe.
Its definitely very hard. I wouldn’t have been able to complete it. Although Rectangles is pretty easy. Would have done that in 30 minutes. Better Luck next time unless you get selected via ZIO.
@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.
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?
Hey people,
I appeared in the morning session of ZCO. It was good, I won’t say that it was very tough, but yah it was difficult enough. Much more of the problem was posed by their servers which kept getting Critical errors time and again.
Here are the two problems:
BREAKUP(this one is the tougher of the two problems)
VARIATION(I was able to solve this one)
I tried solving the “BREAKUP” problem and came up with an apt algorithm but that failed many test cases in which the palindromic sequence started from the middle or after that. I would love if someone could provide a valid solution. For that problem.
And about the Afternoon session, to me, it looks a lot tougher than the morning one, and the Rectangle problem is like, really difficult…
The RECTANGLE problem is much easier than COVERING.
@Organic-Shilling: Can you explain it a little more… Also note there can be cases like
1> The largest area rectangle lies between two points
2> DP doesn’t seen to be a valid choice since optimal substructure can change due to new points
3> Greedy is also invalid
4> Graphs and trees seem irrelevant
If I have missed a point please correct 
EDIT: Sorry I forgot to state that I sat for the dreaded afternoon test and I was asking the solution for the problem rectangle.
Solutions to Morning session : BREAKUP http://pastebin.com/ea2Dncp4 .VARIATION http://pastebin.com/pDd7dQER . 1st Problem required DP and the second could be solved easily. I have secured 100% so the solution should mostly be correct. Ask me if you have any doubt.
I sat for the morning exam… I think the morning session was a tad easier than the afternoon session. Apparently I got 200, but they say the code will be provided with additional test data later, so I’m not really sure. Has anyone seen getting his scores decreased after the code was fed by the additional input? Anyways, here are my solutions, which hopefully work.
1: This is a nice DP exercise. I made an array ans[n+1], where ans[n]= 0 and ans[i] is the answer for the sequence {a[i], a[i+1], …, a[n-1]}. Now, it’s easy to see that ans[n-1]=1 and ans[i]= min(ans[j]: j varying over all integers >=i such that the sequence {a[i], a[i+1], …, a[j]} is a palindrome)+1. We can thus compute a[i] for all i<=n-1 recursively, and our answer is ans[0]. Overall complexity: O(n^3).
2: This is just trivial binary search. First, sort the sequence. Then, for all 1<=i<=n-1, compute the smallest index j satisfying a[j]>=a[i]+k using binary search, and add n-j to the answer. Overall complexity: O(n log n).
Also, the server slowing down was a real big problem. >_< Did anyone else experience it too?
I gave the morning session. Yeah, there are no unnecessary points I Misread the question. Put my solution as an answer @sandy999
Solution to rectangles. Disclaimer: I gave the morning session so I am not 100% sure
1.Sort all coordinates by y- coordinate
2.Pick the one with the lowest y coordinate.
3.The area covered by this rectangle is y*width, width = 10000 for 1st case.
4. Add its x coordinate to a fresh list.
5.Now we have two subproblems, One right to the marked x-coordinate and One left to the marked coordinate
6.Repeat the procedure from 2 till here, keeping in mind that the limits have changed for the width. Also if there are two coordinates with same y add both of their x coordinates to the maintained list.
Has anybody got 100% in this question ? I want to see their code badly. This was a very good question I wish it was in the morning. Our session was boring. I was doing it half minded.
Well there is a catch here… The vertices can lie on the edge of the rectangle. Moreover if you add point one by one in a order, you may not count a newly created area that you assume you have. So DP seems out of question
(I initially thought that we redistribute the area disturbed by new points (added by ascending y coordinate) but failed))
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.
It seems I am doing something wrong here. I meant the area which you get from bottom top approach
