Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 DWITE Round #2 Question #5
Index -> CompSci.ca, Contests -> DWITE
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
A.J




PostPosted: 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
Sponsor
sponsor
jli1




PostPosted: 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




PostPosted: 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




PostPosted: Wed Nov 30, 2011 8:40 pm   Post subject: Re: DWITE Round #2 Question #5

Hmm.. so I don't want to steal AJ's thunder in the analysis of the solution.
Although if you want a sneak peek, this site has a superb explanation!

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure
Revolution




PostPosted: 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




PostPosted: 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




PostPosted: 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.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
trishume




PostPosted: 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 non-compiling 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 Sad
antybash




PostPosted: 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




PostPosted: 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).
Display posts from previous:   
   Index -> CompSci.ca, Contests -> DWITE
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 10 Posts ]
Jump to:   


Style:  
Search: