ZCO 2015 Discussion

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 .

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

@deepcoder18: You are right!

The cutoffs won’t be different for afternoon and morning sessions right?

I gave the afternoon session … @Organic-Shilling 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.

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.

3 Likes

Does anyone know when the results are going to be out?

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

#include

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=n-1;i>=1;i–)
{

for(int j=i-1;j>=0;j–)

{

if(a[i]-a[j]>=k)

{

c=c+j+1;

break;

}

}

}

cout<<c;

return 0;

}

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

2 Likes

I think the cutoff for both morning and afternoon would be 100/200 .

I took the morning session and got 100 in Variation.
I ran out of time for Breakup.
Let’s see whether 100 would be enough to qualify.

Yay! I got an email saying I had qualified! I got 100.

@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.

Took part in the morning session. You will definitely receive one then.

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.

@Organic-Shilling How did you go about rectangles? I couldn’t think of a good algo :frowning:

@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