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.

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 ?

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?

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)

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…

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?

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))