DWITE Round #2 Question #5

[A.J]

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

[jli1]

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

[Revolution]

Can you post the data file for Question 5?

[antybash]

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]

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

[d310]

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]

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

[trishume]

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

[antybash]

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]

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