Answers to: ZCO 2015 Discussionhttps://discuss.codechef.com/questions/57517/zco-2015-discussion<p>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. </p>
<p>Here's are links to the problems:- </p>
<p><a href="http://www.filedropper.com/rectangleen">Rectangle</a></p>
<p><a href="http://www.filedropper.com/coveringen">Covering</a></p>
<p>Can someone share the problems from the morning session?</p>enSat, 13 Dec 2014 22:23:35 +0530Answer by potatiohttps://discuss.codechef.com/questions/57517/zco-2015-discussion/58213<p>Took part in the morning session. You will definitely receive one then.</p>potatioSat, 13 Dec 2014 22:23:35 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/58213Answer by hackperthttps://discuss.codechef.com/questions/57517/zco-2015-discussion/58209<p><a href="/users/81655/potatio">@potatio</a> 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.</p>hackpertSat, 13 Dec 2014 21:59:02 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/58209Answer by potatiohttps://discuss.codechef.com/questions/57517/zco-2015-discussion/58163<p>Yay! I got an email saying I had qualified! I got 100.</p>potatioSat, 13 Dec 2014 10:30:17 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/58163Answer by animesh_fhttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57719<p>I think the cutoff for both morning and afternoon would be 100/200 .<br>
I took the morning session and got 100 in Variation. <br>I ran out of time for Breakup.<br> Let's see whether 100 would be enough to qualify.</p>animesh_fMon, 08 Dec 2014 17:15:47 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57719Answer by adityakhanna1999https://discuss.codechef.com/questions/57517/zco-2015-discussion/57714<p><a href="http://pastebin.com/2NYz9hsn">http://pastebin.com/2NYz9hsn</a></p>
<p>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</p>adityakhanna1999Mon, 08 Dec 2014 15:20:42 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57714Answer by a1a99_3https://discuss.codechef.com/questions/57517/zco-2015-discussion/57671<p>This is my code for variation . It fetched me 100 pts in the grader but i want to know whether its </p>
<p>full efficient or not .( PLEASE COMMENT )</p>
<h1>include<iostream></h1>
<h1>include<algorithm></h1>
<p>using namespace std;</p>
<p>int main()</p>
<p>{</p>
<p>ios::sync_with_stdio(0);</p>
<p>int n,k;</p>
<p>cin>>n>>k;</p>
<p>int a[n];</p>
<p>for(int i=0;i<n;++i)</p>
<p>cin>>a[i];</p>
<p>int c=0;</p>
<p>sort(a,a+n);</p>
<p>for(int i=n-1;i>=1;i--)
{</p>
<p>for(int j=i-1;j>=0;j--)</p>
<p>{</p>
<p>if(a[i]-a[j]>=k)</p>
<p>{</p>
<p>c=c+j+1;</p>
<p>break;</p>
<p>}</p>
<p>}</p>
<p>}</p>
<p>cout<<c;</p>
<p>return 0;</p>
<p>}</p>a1a99_3Sun, 07 Dec 2014 23:09:07 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57671Answer by batcrazthttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57662<p>Does anyone know when the results are going to be out?</p>batcraztSun, 07 Dec 2014 20:29:00 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57662Answer by gvishalhttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57659<p>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>
<p>P.S Sort the intervals in increasing order of its rightmost number.</p>gvishalSun, 07 Dec 2014 18:29:54 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57659Answer by c1_6https://discuss.codechef.com/questions/57517/zco-2015-discussion/57653<p>I gave the afternoon session .... <a href="/users/76608/organic-shilling">@Organic-Shilling</a> For Rectangles, I tried exactly the same method that you posted but it gave me correct in only two sub-test-cases 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.</p>c1_6Sun, 07 Dec 2014 17:47:44 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57653Answer by potatiohttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57622<p>The cutoffs won't be different for afternoon and morning sessions right?</p>potatioSun, 07 Dec 2014 10:00:13 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57622Answer by sidmohlahttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57621<p><a href="/users/46797/deepcoder18">@deepcoder18</a>: You are right!</p>sidmohlaSun, 07 Dec 2014 09:58:17 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57621Answer by deepcoder18https://discuss.codechef.com/questions/57517/zco-2015-discussion/57612<p>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@<a href="http://iarcs.org.in">iarcs.org.in</a> also, we should get together and do something about it. All those who are like minded please email me: soumadeep.saha97@<a href="http://gmail.com">gmail.com</a>
Thank you
A victim of ZCO afternoon session</p>deepcoder18Sun, 07 Dec 2014 02:28:55 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57612Answer by adityakhanna1999https://discuss.codechef.com/questions/57517/zco-2015-discussion/57605<p>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 . </p>adityakhanna1999Sun, 07 Dec 2014 00:57:38 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57605Answer by ritikhttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57590<p>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.</p>ritikSat, 06 Dec 2014 23:26:57 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57590Answer by a1b413https://discuss.codechef.com/questions/57517/zco-2015-discussion/57588<p>The morning session was way easier.
One was a DP and the other was really also easy. </p>
<p>Afternoon the covering was a greedy. </p>
<p>But the rectangles one
.... Ugh it was so bad.
I unfortunately gave the afternoon session and got only 1. </p>
<p>Wish I'd given the morning one.
I really I hope I get through :/ </p>a1b413Sat, 06 Dec 2014 23:19:04 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57588Answer by sidmohlahttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57578<p>It seems I am doing something wrong here. I meant the area which you get from bottom top approach</p>sidmohlaSat, 06 Dec 2014 22:19:45 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57578Answer by sidmohlahttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57567<p>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))</p>sidmohlaSat, 06 Dec 2014 21:38:03 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57567Answer by Organic-Shillinghttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57563<p>Solution to rectangles. Disclaimer: I gave the morning session so I am not 100% sure <br> 1.Sort all coordinates by y- coordinate <br> 2.Pick the one with the lowest y coordinate. <br> 3.The area covered by this rectangle is y*width, width = 10000 for 1st case. <br> 4. Add its x coordinate to a fresh list. <br> 5.Now we have two subproblems, One right to the marked x-coordinate and One left to the marked coordinate <br> 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. <br> 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.</p>Organic-ShillingSat, 06 Dec 2014 21:18:42 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57563Answer by AnonymousBunnyhttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57560<p>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.</p>
<p>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).</p>
<p>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).</p>
<p>Also, the server slowing down was a real big problem. >_< Did anyone else experience it too? </p>AnonymousBunnySat, 06 Dec 2014 20:57:43 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57560Answer by Organic-Shillinghttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57558<p>Solutions to Morning session : BREAKUP <a href="http://pastebin.com/ea2Dncp4">http://pastebin.com/ea2Dncp4</a> .VARIATION <a href="http://pastebin.com/pDd7dQER">http://pastebin.com/pDd7dQER</a> . 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.</p>Organic-ShillingSat, 06 Dec 2014 20:50:29 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57558Answer by sidmohlahttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57553<p><a href="/users/76608/organic-shilling"><a href="/users/76608/organic-shilling">@Organic-Shilling</a></a>: Can you explain it a little more... Also note there can be cases like</p>
<p>1> The largest area rectangle lies between two points</p>
<p>2> DP doesn't seen to be a valid choice since optimal substructure can change due to new points</p>
<p>3> Greedy is also invalid</p>
<p>4> Graphs and trees seem irrelevant</p>
<p>If I have missed a point please correct :-D</p>
<p>EDIT: Sorry I forgot to state that I sat for the dreaded afternoon test and I was asking the solution for the problem rectangle.</p>sidmohlaSat, 06 Dec 2014 20:19:45 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57553Answer by nibnalinhttps://discuss.codechef.com/questions/57517/zco-2015-discussion/57546<p>Hey people,</p>
<p>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.</p>
<p>Here are the two problems:</p>
<p><a href="http://www.dropbox.com/s/5ok2pnk4yyjk1kz/BREAKUP%28EN%29.pdf?dl=0">BREAKUP</a>(this one is the tougher of the two problems)</p>
<p><a href="http://www.dropbox.com/s/ysz2lf8dyw80pe3/VARIATION%28EN%29.pdf?dl=0">VARIATION</a>(I was able to solve this one)</p>
<p>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.</p>
<p>And about the Afternoon session, to me, it looks a lot tougher than the morning one, and the Rectangle problem is like, really difficult...</p>nibnalinSat, 06 Dec 2014 19:54:23 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57546Answer by achintya75https://discuss.codechef.com/questions/57517/zco-2015-discussion/57519<p>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.</p>achintya75Sat, 06 Dec 2014 17:38:29 +0530https://discuss.codechef.com/questions/57517/zco-2015-discussion/57519