Author 
Message 
A.J

Posted: Wed Nov 30, 2011 5:58 pm Post subject: DWITE Round #2 Question #5 


Turns out there is an error on of the the testcases for #5. So the maximum possible testcases one can get right is 4/5.
Once again, sorry about this,
AJ






Sponsor Sponsor



jli1

Posted: Wed Nov 30, 2011 7:28 pm Post subject: RE:DWITE Round #2 Question #5 


Yet no one gets above 2/5... What was the correct solution for this one?






Revolution

Posted: Wed Nov 30, 2011 8:03 pm Post subject: RE:DWITE Round #2 Question #5 


Can you post the data file for Question 5?






antybash





Revolution

Posted: Wed Nov 30, 2011 8:55 pm Post subject: RE:DWITE Round #2 Question #5 


I was going to do that ^
but i forgot to include one line of code and got 0 /5
T.T






d310

Posted: Wed Nov 30, 2011 9:01 pm Post subject: Re: DWITE Round #2 Question #5 


I recognised that it was a disjoint data structure...
I guess I got TLE because I used an array indexes instead of pointers, and forgot to use the rank optimisation.
Just wondering what were the values on N for each test case?






Tony

Posted: Wed Nov 30, 2011 9:05 pm Post subject: RE:DWITE Round #2 Question #5 


something crazy large. Knowing AJ, he'd try to hit the specified 100000. I'll let him post the details.

Tony's programming blog. DWITE  a programming contest. 




trishume

Posted: Wed Nov 30, 2011 9:45 pm Post subject: Re: DWITE Round #2 Question #5 


We (ttm, others, and I) solved this using lists of sets and merging and adding to the sets. Kind of dynamic programming like.
But we were in the final 15 minutes and ended up submitting a noncompiling solution with bugs, twice.
Tony (the ttm one) wrote a better version which finished compiling 1m too late. But without the test data we don't know if it works






antybash

Posted: Wed Nov 30, 2011 10:16 pm Post subject: Re: DWITE Round #2 Question #5 


Yeah .. I'm in favour of seeing the testcase. I thought I coded up the disjoint sets and thought I should have received a few points but didn't get any. :\
Would be possible to post on say google docs or some place like this?






A.J

Posted: Thu Dec 01, 2011 12:28 am Post subject: RE:DWITE Round #2 Question #5 


I'll be posting solutions over this weekend. I am super busy with assignments and exams. I will say that the intended solution for this problem was Union Find. The link antybash provided is a good read. I'll explain the details in the solutions (and release the testdata).






