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? asked 06 Dec '14, 17:24

Covering can be solved with a greedy approach where for every interval you check whether there is any number that is already picked in some earlier chosen interval such that it lies between the current interval and if not you always add the rightmost number of the interval to the set of picked numbers. Complexity: O(n^2) P.S Sort the intervals in increasing order of its rightmost number. answered 07 Dec '14, 18:29

guys this was my code for covering .i got 100 points (till now) dont now future .I can explain my code if theres a problem . please tell me if any case is coming wrong answered 08 Dec '14, 15:20

I had the option to choose between the morning and the afternoon session. I chose the afternoon session. And now I absolutely regret it. T_T I spent the whole three hours sending numerous solutions modifying minute things and tweaking but nothing worked. :( And the morning session problems do seem a lot easier. At least that's what I feel after reading the problem statements. answered 06 Dec '14, 23:26

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. answered 06 Dec '14, 17:38
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.
(06 Dec '14, 18:41)
@OrganicShilling How did you go about rectangles? I couldn't think of a good algo :(
(06 Dec '14, 18:48)
@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.52 hrs. Although I would have attempted this one before Covering. What algorithm did you use for covering ?
(06 Dec '14, 19:08)
1
your solution would take O(n^2) time.
(06 Dec '14, 19:15)
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?
(06 Dec '14, 19:19)
I gave the morning session. Yeah, there are no unnecessary points I Misread the question. Put my solution as an answer @sandy999
(06 Dec '14, 20:59)
showing 5 of 6
show all

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... answered 06 Dec '14, 19:54

@OrganicShilling: 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 :D EDIT: Sorry I forgot to state that I sat for the dreaded afternoon test and I was asking the solution for the problem rectangle. answered 06 Dec '14, 20:19

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. answered 06 Dec '14, 20:50
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.
(06 Dec '14, 22:05)
Don't you think that this would give TLE?
(09 Dec '14, 00:03)
I did the same thing but I made a really strong test case and it didn't pass it.
(09 Dec '14, 00:03)
No, he has got perfect score. His algorithm is O(N) after sorting which is the best you can do I think.
(09 Dec '14, 00:42)
No I am talking about the other link that he has given. Try this test case: 65000 1000 1 1 1 ....and 64997 1's
(09 Dec '14, 11:24)
This would take 64999*65000/2 steps.
(09 Dec '14, 11:24)
showing 5 of 6
show all

Solution to rectangles. Disclaimer: I gave the morning session so I am not 100% sure answered 06 Dec '14, 21:18
Do you have any ideas about COVERING?
(06 Dec '14, 21:46)
@sampritipanda None Whatsoever!
(06 Dec '14, 22:43)

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)) answered 06 Dec '14, 21:38

It seems I am doing something wrong here. I meant the area which you get from bottom top approach answered 06 Dec '14, 22:19

The morning session was way easier. One was a DP and the other was really also easy. Afternoon the covering was a greedy. But the rectangles one .... Ugh it was so bad. I unfortunately gave the afternoon session and got only 1. Wish I'd given the morning one. I really I hope I get through :/ answered 06 Dec '14, 23:19

I did the cover question very easy algorithm . got it in just last minutes . was doing a very bad bad error.12 attempts to reach a 100 Shit man seriosly should have given the morning question . Altough i was happy afternoon session had an adhoc problem . answered 07 Dec '14, 00:57

Dont you think that the problems that appeared in the second session were many times more difficult than that of the first half. I think there ought to be more fairness in the evaluation procedure. Infact I think we ought to file a petetion against this. Please mail all your grievances to ico@iarcs.org.in also, we should get together and do something about it. All those who are like minded please email me: soumadeep.saha97@gmail.com Thank you A victim of ZCO afternoon session answered 07 Dec '14, 02:28

The cutoffs won't be different for afternoon and morning sessions right? answered 07 Dec '14, 10:00
They will be different. Probably 200 for us and 40 for you.
(07 Dec '14, 10:14)
200 is too much I think.
(07 Dec '14, 10:47)
Nah! Our questions were really easy. But, I surely think your and my cutoffs will be different.
(07 Dec '14, 10:56)
Haha I took the morning session actually! Got 100/200.
(07 Dec '14, 11:04)
1
I don't think 40 is a fair cut off. I solved both the questions of the morning session today with a stopwatch on, and it took me one hour and twenty minutes for both of them, with no extra help whatsoever. Which is when DP isn't really my bailiwick. IMHO, getting a perfect score on the morning session was significantly easier than getting a nonzero one in the afternoon session.
(07 Dec '14, 18:19)
The 40 point subtask for rectangle was just brute force, and it's arguably easier than the first problem of the morning session. However the psychological factor is not to be underestimated  if I had done the afternoon session I would certainly not be aiming to get 40, so I might have tried to get 200 and failed to get anything at all. But seen on its own the 40 point subtask was easier than getting 200 in the morning session.
(16 Dec '14, 16:42)
showing 5 of 6
show all

I gave the afternoon session .... @OrganicShilling For Rectangles, I tried exactly the same method that you posted but it gave me correct in only two subtestcases so my total score was zero. I was pretty sure I got covering right, but here, my solution must have been far too long as I got TLE in all except one, which was the very first one which gave correct. answered 07 Dec '14, 17:47
Was your solution for covering bruteforce?
(07 Dec '14, 18:06)
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.
(07 Dec '14, 18:12)

Does anyone know when the results are going to be out? answered 07 Dec '14, 20:29

This is my code for variation . It fetched me 100 pts in the grader but i want to know whether its full efficient or not .( PLEASE COMMENT ) include<iostream>include<algorithm>using namespace std; int main() { ios::sync_with_stdio(0); int n,k; cin>>n>>k; int a[n]; for(int i=0;i<n;++i) cin>>a[i]; int c=0; sort(a,a+n); for(int i=n1;i>=1;i) { for(int j=i1;j>=0;j) { if(a[i]a[j]>=k) { c=c+j+1; break; } } } cout<<c; return 0; } answered 07 Dec '14, 23:09

I think the cutoff for both morning and afternoon would be 100/200 . answered 08 Dec '14, 17:15

Yay! I got an email saying I had qualified! I got 100. answered 13 Dec '14, 10:30

@potatio Can you please confirm if you took part in the morning session or the afternoon one? I had a full score in the morning session, but haven't received anything yet. answered 13 Dec '14, 21:59
Yeah, I got full as well and got an email, so I can confirm that the cutoff is not more than 200 :P
(13 Dec '14, 22:43)

Took part in the morning session. You will definitely receive one then. answered 13 Dec '14, 22:23
